3.1 接口

常见接口

Map 接口和 Collection 接口是所有集合框架的父接口；

Collection 接口的子接口包括：Set 接口、List 接口和Queue接口；

Map 接口的实现类主要有：HashMap、TreeMap、LinkedHashMap、Hashtable、ConcurrentHashMap 以及 Properties 等；

Set 接口的实现类主要有：HashSet、TreeSet、LinkedHashSet 等；

List 接口的实现类主要有：ArrayList、LinkedList、Stack 、Vector以及CopyOnWriteArrayList 等；

Queue接口的主要实现类有：ArrayDeque、ArrayBlockingQueue、LinkedBlockingQueue、PriorityQueue等；

 

List接口和Set接口的区别

List 元素是有序的，可以重复；Set 元素是无序的，不可以重复。

队列、Set、Map 区别

List 有序列表

Set无序集合

Map键值对的集合

Queue队列FlFO

ArrayList

基于数组实现，无容量的限制。

在执行插入元素时可能要扩容，在删除元素时并不会减小数组的容量，在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。

是非线程安全的。

注意点：

（1)ArrayList随机元素时间复杂度O(1)，插入删除操作需大量移动元素，效率较低

（2)为了节约内存，当新建容器为空时，会共享Object[] EMPTY_ELEMENTDATA = {}和 Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}空数组

（3)容器底层采用数组存储，每次扩容为1.5倍

（4)ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法，其实Arrays.copyof()内部也是调用System.arraycopy()。System.arraycopy()为Native方法

（5)两个ToArray方法

Object[] toArray()方法。该方法有可能会抛出java.lang.ClassCastException异常

<T> T[] toArray(T[] a)方法。该方法可以直接将ArrayList转换得到的Array进行整体向下转型

（6)ArrayList可以存储null值

（7)ArrayList每次修改（增加、删除)容器时，都是修改自身的modCount；在生成迭代器时，迭代器会保存该modCount值，迭代器每次获取元素时，会比较自身的modCount与ArrayList的modCount是否相等，来判断容器是否已经被修改，如果被修改了则抛出异常（fast-fail机制)。

成员变量

/** * 序列号 */ private static final long serialVersionUID = 8683452581122892189L; /** * 默认容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 一个空数组 * 当用户指定该 ArrayList 容量为 0 时，返回该空数组 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 一个空数组实例 * - 当用户没有指定 ArrayList 的容量时(即调用无参构造函数)，返回的是该数组==>刚创建一个 ArrayList 时，其内数据量为 0。 * - 当用户第一次添加元素时，该数组将会扩容，变成默认容量为 10(DEFAULT_CAPACITY) 的一个数组===>通过 ensureCapacityInternal() 实现 * 它与 EMPTY_ELEMENTDATA 的区别就是：该数组是默认返回的，而后者是在用户指定容量为 0 时返回 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * ArrayList基于数组实现，用该数组保存数据, ArrayList 的容量就是该数组的长度 * - 该值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入 ArrayList 中时，数组将扩容值 DEFAULT_CAPACITY(10) */ transient Object[] elementData; // non-private to simplify nested class access /** * ArrayList实际存储的数据数量 */ private int size;

构造方法

/** * 创建一个初试容量的、空的ArrayList * @param initialCapacity 初始容量 * @throws IllegalArgumentException 当初试容量值非法(小于0)时抛出 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

添加 add(e)

/** *增加指定的元素到ArrayList的最后位置 * @param e 要添加的元素 * @return */ public boolean add(E e) { // 确定ArrayList的容量大小---严谨 // 注意：size + 1，保证资源空间不被浪费， // ☆☆☆按当前情况，保证要存多少个元素，就只分配多少空间资源 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

即使初始化时指定大小：小于10个，添加元素时会调整大小，保证capacity不会少于10个。

/** * 私有方法：明确 ArrayList 的容量，提供给本类使用的方法 * - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效 * @param minCapacity 指定的最小容量 */ private void ensureCapacityInternal(int minCapacity) { // 若 elementData == {}，则取 minCapacity 为 默认容量和参数 minCapacity 之间的最大值 // 注：ensureCapacity() 是提供给用户使用的方法，在 ArrayList 的实现中并没有使用 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { /** * - 当用户没有指定 ArrayList 的容量时(即调用无参构造函数)，返回的是该数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ==>刚创建一个ArrayList 时，其内数据量为 0。 * - 当用户第一次添加元素时，该数组将会扩容，变成默认容量为 10(DEFAULT_CAPACITY) 的一个数组 ===>通过 ensureCapacityInternal() 实现 * DEFAULTCAPACITY_EMPTY_ELEMENTDATA与 EMPTY_ELEMENTDATA 的区别就是：该数组是默认返回 的，而后者是在用户指定容量为 0 时返回 */ minCapacity= Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } /** * 私有方法：明确 ArrayList 的容量 * - 用于内部优化，保证空间资源不被浪费：尤其在 add() 方法添加时起效 * @param minCapacity 指定的最小容量 */ private void ensureExplicitCapacity(int minCapacity) { // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的 modCount++; // 防止溢出代码：确保指定的最小容量 > 数组缓冲区当前的长度 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

扩容

/** * 私有方法：扩容，以确保 ArrayList 至少能存储 minCapacity 个元素 * - 扩容计算：newCapacity = oldCapacity + (oldCapacity >> 1); 扩充当前容量的1.5倍 * @param minCapacity 指定的最小容量 */ private void grow(int minCapacity) { // 防止溢出代码 int oldCapacity = elementData.length; // 运算符 >> 是带符号右移. 如 oldCapacity = 10,则 newCapacity = 10 + (10 >> 1) = 10 + 5 = 15 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) // 若 newCapacity 依旧小于 minCapacity newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) // 若 newCapacity 大于最大存储容量，则进行大容量分配 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

Arrays.copyOf底层是System.arrayCopy

添加 add(index,e)

/** * *在这个ArrayList中的指定位置插入指定的元素， * - 在指定位置插入新元素，原先在 index 位置的值往后移动一位 * @param index 指定位置 * @param element 指定元素 * @throws IndexOutOfBoundsException */ public void add(int index, E element) { rangeCheckForAdd(index);//判断角标是否越界 //看上面的，size+1，保证资源空间不浪费，按当前情况，保证要存多少元素，就只分配多少空间资源 ensureCapacityInternal(size + 1); // Increments modCount!! //第一个是要复制的数组，第二个是从要复制的数组的第几个开始， // 第三个是复制到那，四个是复制到的数组第几个开始，最后一个是复制长度 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } /** * 添加时检查索引是否越界 */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

删除 remove(o)

/** * 移除list中指定的第一个元素(符合条件索引最低的) * 如果list中不包含这个元素，这个list不会改变 * 如果包含这个元素，index 之后的所有元素依次左移一位 * @param o 这个list中要被移除的元素 * @return */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /** * 快速删除第 index 个元素 * 和public E remove(int index)相比 * 私有方法，跳过检查，不返回被删除的值 * @param index 要删除的脚标 */ private void fastRemove(int index) { modCount++;//这个地方改变了modCount的值了 int numMoved = size - index - 1;//移动的个数 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //将最后一个元素清除 }

public static void arraycopy(Object src, int srcPos, Object dest, int destPos,int length) 其中：src表示源数组，srcPos表示源数组要复制的起始位置，desc表示目标数组，length表示要复制的长度。

删除 remove(index)

/** * 移除指定位置的元素 * index 之后的所有元素依次左移一位 * @param index 指定位置 * @return 被移除的元素 * @throws IndexOutOfBoundsException */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1;//要移动的长度 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 将最后一个元素置空 elementData[--size] = null; return oldValue; }