一、集合框架基础

（一）单列集合

1. List 集合

• ArrayList：底层原理为数组，扩容机制为当添加元素时每次都会校验数组大小。当初始化一个空的集合时，第一次 add 元素时集合的大小会被初始化为 10。然后随着集合元素不断增加，当第 11 个元素插入时，这个时候集合需要扩容，扩容后的容量就是 10+10>>1=15。扩容完成后，需要将旧集合的元素全部复制到新集合中。特点是有序、可重复、有索引，查找效率高。

• LinkedArrayList：底层是双向链表，特点是有序、可重复、有索引，增删效率高。

• Vector：底层为线性动态数组，扩容机制与 ArrayList 类似，但 Vector 是线程安全的，在多线程环境下使用时可保证数据的一致性，但效率相对较低。

2. Set 集合

• HashSet：底层数据结构在不同版本有所变化。在 JDK8 之前，哈希表由数组 + 链表组成；在 JDK8 之后，哈希表由数组 + 链表 + 红黑树组成。当链表长度大于 8 且数组长度大于等于 64 时，当前链表会自动转成红黑树。特点是不重复、无索引、无序。

• LinkedHashSet：底层结构是通过维护一个双向链表来记录元素的添加顺序。特点是有序、不重复、无索引。

• TreeSet：底层通过红黑树实现排序。特点是可排序、无索引、不重复。

（二）双列集合（Map）

1. HashMap：底层数据结构及解决 Hash 冲突的方法如下：HashMap 基于哈希表实现，它是一个 entry 对象组成的数组，entry 对象又是 key、value 形式的键值对。当程序执行 map.put (String,Object) 方法的时候，系统将调用 String 的 hashCode () 方法得到其 hashCode 值，再通过哈希值来决定该元素的存储位置。如果计算出的索引位置没有元素，则直接插入；如果有元素，调用 equals 比较，如果相同，就覆盖 value，如果不相同，则添加到最后，形成链表。当链表长度超过 8 就变成红黑树。特点是无序、不重复、无索引。

2. LinkedHashMap：底层结构是在 HashMap 的基础上，通过维护一个双向链表来保证元素的有序性。特点是有序、无索引、不重复。

3. TreeMap：底层通过红黑树原理实现排序，特点是可比较、无索引、不重复。

二、集合框架扩展机制

（一）ArrayList 扩容机制

1. 默认初始化及首次添加元素时的扩容。

ArrayList 实现了 List 接口，是一个可调整大小的数组。以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。具体过程如下：首先查看源码部分，ArrayList 的无参构造方法会将内部数组初始化为一个空数组，即this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;，其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个长度为 0 的静态常量数组。当首次添加元素时，会调用ensureCapacityInternal(size + 1);方法来确保内部数组有足够的容量容纳新元素。这个方法会进一步调用calculateCapacity(elementData, minCapacity)方法，在这个方法中，如果内部数组是默认的空数组，会根据传入的最小容量参数和默认容量DEFAULT_CAPACITY（值为 10）进行比较，返回较大的值作为新的容量。如果首次扩容时最小容量小于 10，则新容量为 10；如果最小容量大于等于 10，则新容量为传入的最小容量。最后，会根据新容量创建一个新的数组，并将旧数组中的元素复制到新数组中。

2. 超出容量后的扩容计算方式。

当 ArrayList 中的元素数量超出当前容量时，会进行扩容操作。扩容操作会创建一个新的长度更大的数组，然后将旧数组中的元素复制到新数组中。新数组的长度通常是原数组长度的 1.5 倍（在 JDK1.7 及之前是原数组长度的 1.5 倍，JDK1.8 及之后则变为原数组长度的 1.5 倍再加 1）。具体计算过程如下：当添加元素时，如果当前元素数量等于容量，则会触发扩容操作。首先计算新的容量，即int newCapacity = oldCapacity + (oldCapacity >> 1);，其中oldCapacity是原数组的长度。如果新容量小于传入的最小容量要求，则新容量为最小容量；如果新容量大于最大数组大小MAX_ARRAY_SIZE，则调用hugeCapacity(minCapacity)方法来确定最终的新容量。最后，使用Arrays.copyOf(elementData, newCapacity)方法将旧数组中的元素复制到新数组中，并丢弃旧数组。

（二）HashMap 扩容机制

1. JDK7 中数组 + 链表结构的扩容条件。

在 JDK7 中，HashMap 使用数组 + 链表的结构实现。当添加某个元素后，数组的总的添加元素数大于了数组长度 * 0.75（默认，也可自己设定）时，数组长度扩容为两倍。例如，开始创建 HashMap 集合后，数组长度为 16，临界值为 16 * 0.75 = 12，当加入元素后元素个数超过 12，数组长度扩容为 32，临界值变为 24。具体过程如下：在put方法中，会调用putVal方法来插入元素。如果当前哈希表为空或者长度为 0，则会调用resize方法进行初始化或扩容。在putVal方法中，如果计算出的索引位置为空，则直接插入新节点；如果索引位置已有节点，且节点的哈希值与新节点相同且键相等，则覆盖值；如果不相等且当前节点不是树节点，则遍历链表插入新节点。当链表长度超过一定阈值（默认为 8）时，会将链表转换为红黑树。如果添加元素后，元素总数大于阈值，则会调用resize方法进行扩容。在resize方法中，会根据新的容量创建一个新的数组，并将旧数组中的元素转移到新数组中。转移过程中，会遍历旧数组，对于每个非空的索引位置，重新计算元素在新数组中的索引，并将元素插入到新数组中。

2. JDK8 中数组 + 链表 + 红黑树结构的优化及扩容方式。

在 JDK8 中，HashMap 引入了红黑树结构，当链表长度超过 8 时，会自动转成红黑树；当红黑树的节点数小于 6 时，变回链表。扩容方式与 JDK7 类似，当添加元素后，元素总数大于阈值时会进行扩容。在扩容过程中，会将原数组每个结点的哈希值和原数组长度进行 “与” 操作，结果等于 0 代表该结点位置不变，落在新数组的同样位置，否则该结点在新数组的位置是[j + oldCap]上。原因是：扩容是将数组长度扩大一倍，假如原长度是 16（二进制是 10000，掩码 1111），新长度是 32（二进制是 100000，掩码 11111），那么在计算结点所落的位置时，哈希值原本是低 4 位参与计算，扩容后变成哈希值低 5 位参与计算，这样的话，当参与运算的最高位也就是第五位，是 1 时，必然落在扩容后的新的位置，是 0 时，必然位置不变，因为原数组长度 16 的二进制第五位是 1，所以通过将结点的哈希值和原数组长度进行与操作，就可以知道结点在新数组中是保持相对不变还是落在高一点的位置上。

三、优化自定义集合性能

（一）批量操作

1. 批量新增：使用addAll和putAll方法可以有效地减少扩容次数，从而提高效率。例如，在向一个集合中添加大量元素时，如果使用逐个添加的方式，每次添加都可能触发集合的扩容操作，这会消耗额外的时间和资源。而使用addAll方法，可以一次性将多个元素添加到集合中，这样集合只需要进行一次扩容或者可能不需要扩容，大大提高了添加元素的效率。

2. 批量删除：ArrayList的removeAll方法在特定场景下具有很大的优势。它可以快速地从一个列表中移除包含在指定集合中的所有元素。这个方法的实现原理是通过遍历列表，检查每个元素是否在指定集合中，如果不在，则保留该元素，否则将其移除。在处理需要从一个集合中移除大量特定元素的情况时，removeAll方法比逐个删除元素的效率要高得多。例如，当需要从一个包含大量数据的列表中移除另一个列表中的元素时，使用removeAll方法可以避免多次遍历和逐个删除的繁琐操作，从而提高程序的性能。

（二）集合类避坑

1. 强制实现equals和hashCode方法：当自定义类作为集合元素时，强制实现equals和hashCode方法非常重要。如果不实现这两个方法，集合在判断元素是否重复时可能会出现错误的结果。例如，在HashSet中，判断元素是否重复首先会比较元素的哈希值，如果哈希值相同，再调用equals方法进行比较。如果自定义类没有正确实现这两个方法，可能会导致不同的对象被认为是相同的，或者相同的对象被认为是不同的。参考资料中提到 “当把自定义对象添加到去重集合时，如hashset，hashset会先调用hashcode()方法，判断新对象与已有对象的hashcode值是否相等，相等则继续调用equals判断，相等则是同一个对象，否则相反。”，这清楚地说明了实现这两个方法的重要性。

2. 统一使用迭代器修改集合：在遍历集合的同时修改集合内容时，容易触发ConcurrentModificationException异常。为了避免这个异常，应该统一使用迭代器来修改集合。例如，在遍历一个列表时，如果直接使用for循环并在循环体内删除元素，就可能会触发这个异常。而使用迭代器的remove方法，可以安全地在遍历过程中删除元素。参考资料中给出了多种避免ConcurrentModificationException异常的方法，如使用函数式编程的方式或者通过迭代器进行迭代删除。

3. 数组转集合的坑：Arrays.asList返回的List有一些特点和需要注意的地方。首先，Arrays.asList返回的是java.util.Arrays$ArrayList，这是一个内部类，而不是标准的ArrayList类。它是固定大小的，不支持对元素的增删操作，任何试图修改大小的操作都会导致UnsupportedOperationException。其次，数组元素类型必须是引用类型，如果传递的是基本数据类型的数组，它将被看作是一个对象，而不是数组。此外，因为Arrays.asList返回的List是基于原始数组的，如果对原始数组进行修改，会影响到返回的List，反之亦然。

4. 集合转数组的坑：集合的toArray方法在使用时需要正确使用及注意可能出现的问题。当使用toArray方法将集合转换为数组时，如果传入的数组大小不足以容纳集合中的所有元素，toArray方法会创建一个新的数组，并将集合中的元素复制到新数组中。如果传入的数组大小足够大，toArray方法会将集合中的元素复制到传入的数组中，并返回这个数组。但是，需要注意的是，toArray方法返回的数组是底层集合的视图，如果对这个数组进行修改，可能会影响到原始集合。

（三）其他优化策略

1. 选择合适的集合类型：根据数据访问模式、唯一性要求等选择合适的集合可以提高程序的性能。例如，如果经常需要随机访问元素，应使用ArrayList；如果经常需要插入和删除元素，应使用LinkedList。如果不需要排序，应优先考虑使用HashSet或HashMap；如果需要保持元素的插入顺序，可以使用LinkedHashSet或LinkedHashMap；如果需要对元素进行自动排序，可以使用TreeSet或TreeMap。

2. 设置合适的初始容量和负载因子：在创建集合时，可以根据预期的元素数量设置合适的初始容量和负载因子。如果初始容量设置得太小，集合可能会频繁地进行扩容操作，这会消耗额外的时间和资源。如果负载因子设置得太大，集合可能会在元素数量还不是很多的时候就进行扩容，浪费空间；如果负载因子设置得太小，集合可能会在元素数量还比较少的时候就进行扩容，也会影响性能。

3. 避免自动装箱和拆箱：在使用基本数据类型的包装类时，要注意避免自动装箱和拆箱带来的性能开销。例如，在频繁进行数值运算的场景下，使用基本数据类型比使用包装类更高效。因为自动装箱和拆箱需要进行额外的操作，会消耗一定的时间和资源。

4. 在多线程环境下使用并发集合类：对于需要处理并发访问的集合操作，Java 提供了并发集合类，如ConcurrentHashMap、CopyOnWrite