List、Set、Map详解_list set map

什么是集合

集合类存放于java.util包中，主要有list(列表), set(集), map(映射)，集合存放的都是对象的引用而非对象本身，所以我们称集合中的对象就是集合中对象的引用。简而言之，集合就是存放数据对象引用的容器。

List

List集合是有序的，可以对其中每个元素的插入位置进行精确地控制，通过索引来访问元素，遍历元素。常用地主要有ArrayList和LinkedList这两个类。
其中ArrayList底层是通过数组实现，随着元素的增加而动态扩容；而LinkedList底层是通过链表实现，随着元素的增加不断向链表的后端增加节点。

List的特点：

• 1.可以允许重复的对象。
• 2.可以插入多个null元素。
• 3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
• 4.常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

ArrayList

ArrayList是一个数组队列，线程不安全集合，它允许对元素进行快速随机访问，数组的缺点是每个元素之间不能有间隔，当数组大小部门组时需要增加存储能力，就需要将已经有数组的数据复制到新的存储空间中（copyOf），当从ArrayList的中间位置插入或者删除元素时，需要对数组进行赋值、移动，代价比较高，因此，它适合随机查找和遍历，不适合插入和删除。

ArrayList继承自AbstractList，实现了如下接口：

• 1、实现了List，得到了List集合框架的基本功能；
• 2、实现了RandomAccess（这是一个标记接口，没有任何方法），获得了快速随机访问存储元素的功能，？？？如何获得的这个功能
• 3、ArrayList实现了Cloneable，得到clone()方法，可以实现克隆功能；
• 4、实现了Serializable，表示可以被序列化，通过序列化去传输。

它具有如下特点

• 容量不固定，随着容量的增加而动态扩容；
• 有序集合；
• 插入的元素可以是null
• 增删改查效率比LinkedList高
• 线程不安全，只能用在单线程环境下

ArrayList的动态扩容

一 初始化
有三种方式来初始化
1、默认的构造器，以默认的大小初始化内部的数组；public ArrayList();
2、用一个ICollection对象来构造，并将该集合的元素添加到ArrayList：public ArrayList(Collection<?extends E> c);
3、用指定大小来初始化内部的数组：public ArrayList(int initialCapacity);

默认构造器在JDK1.6之前是初始化长度为10，而在JDK1.6之后默认数组长度为0.

二 确保内部容量
使用无参构造初始化时，数组长度为0，通过ArrayList.add()添加数据时，

public boolean add(E e) {
   
 //确保内部容量(通过判断，如果够则不进行操作；容量不够就扩容来确保内部容量)
 ensureCapacityInternal(size + 1); // ①Increments modCount!!
 elementData[size++] = e;//②
 return true;
}
1
2
3
4
5
6
7

ensureCapacityInternal()方法通过将现有的元素个数数组的容量比较，如果需要扩容则扩容，再将要添加的元素放置到相应的数组中。elementData是用来存储实际内容的数组，根据传入的最小容量minCapacity和数组的容量长度对比&#x