ArrayList、LinkedList、HashMap、HashTable、HashSet、TreeSet

集合族谱

在这些集合中，仅有vector和hashtable是线程安全的，其内部方法基本都有synchronized修饰。

ArrayList

底层采用Object数组实现，实现了RandomAccess接口因此支持随机访问。插入删除操作效率慢。

ArrayList需要一份连续的内存空间。

ArrayList扩容机制

ArrayList添加元素时，若达到了内部数组指定的数量上限，会自动进行扩容：

1. 计算新容量，一般是原容量的1.5倍（1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数）
2. 根据新容量创建新数组
3. 把原来的数据拷贝到新数组中
4. 更新ArrayList内部指向原数组的引用，指向新数组

ArrayList哪里不安全 

首先，对arraylist添加一个元素，分为3步

• 判断数组是否需要扩容，如果需要就调用grow方法扩容；

• 将数组的size位置设置值（因为数组的下标是从0开始的）；
• 将当前集合的大小+1

多线程插入删除下，ArrayList会暴露三个问题：

• 出现null值：
  假设arraylist容量为10，线程1检查当前size=4，不需要扩容，于是在index=4进行插入，但是还没有size++，线程2又来进行插入，检查不需要扩容且size=4，于是也在index=4执行插入，然后两个线程同时执行size++，就导致实际size=6，两次插入都在index=4，而index=5的地方并没有插入数据。
• 索引越界异常
  还是上述例子，假设线程1检查size=9，没有到10，无需扩容，于是在index=9的地方插入，但还没有size++，线程2来检查size=9，也在index=9的地方插入，然后两个线程同时++，导致size=11。
• 集合的size()和实际add数量不符
  size++不是原子操作，分为三步，获取size值、size+1、新size覆盖老size，如果两个线程拿到一样的size同时覆盖，那么就导致有一次没加上。

为什么需要DEFAULTCAPACITY_EMPTY_ELEMENTDATA标识未初始化的状态

• 确保第一次添加元素时数组的容量扩展：
  ArrayList 在没有明确指定容量时，会使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来标识该 ArrayList 尚未添加任何元素。这意味着，当创建一个空的 ArrayList 时，它的内部数组并不会立即分配实际的空间，而是会指向一个空的数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）。这节省了内存开销。
  当第一次往这个 ArrayList 中添加元素时，内部数组的大小就需要扩展。因为 ArrayList 的默认初始容量是 10，所以一旦添加元素，数组就会重新分配一个合适的大小（10）来存放这些元素。
• 避免不必要的内存分配：
  如果没有 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这种标识，ArrayList 每次创建时都会为空的实例分配一个固定大小的数组（比如长度为 10）占用内存。
  通过使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，ArrayList 会在初始化时使用一个空数组来表示尚未使用的状态，只有在第一次添加元素时，才会根据需要分配和扩展内部数组。这样可以节省内存开销。
• 区分“空的”实例和“已初始化但无元素”实例：

  DEFAULTCAPACITY_EMPTY_ELEMENTDATA 有一个特别的用途，就是帮助 ArrayList 区分两种不同的状态：

  • 空实例：=ArrayList 没有被初始化为一个非空的数组，只是一个空的实例。ArrayList<Integer> list = new ArrayList<>();

  • 已初始化但无元素：ArrayList 已经分配了一个默认大小的数组，但当前还没有元素。ArrayList<Integer> list = new ArrayList<>(10);

LinkedList

HashMap

• HashMap可以存储null的key和value,但null作为键（key的哈希值为0）只能有一个，null作为值可以有多个。
• JDK1.8之前hashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)，如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。
• JDK1.8后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于等于8并且数组长度大于等于64时，将链表转化为红黑树，以减少搜索时间O（logn），但是在数量较少时，即数量小于6时，会将红黑树变回链表。
• HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。并且HashMap总是使用2的幂作为哈希表的大小。
• 解决哈希冲突的方法：
  • 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
  • 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
  • 再哈希法：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存诸键值对。
  • 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

 

HashMap哪里线程不安全

• JDK1.7 HashMap采用数组+链表的数据结构，多线程背景下，HashMap 使用头插法插入元素，可能出现环形链表造成Entry链死循环，多线程同时执行 put 操作，可能造成前一个 key 被后一个 key 覆盖，存在和数据丢失问题。
• JDK1.8 HashMap采用数组+链表+红黑二叉树的数据结构，优化了1.7中数组扩容的方案，解决了Entry链死循环和数据丢失问题。但是多线程背景下，put方法存在数据覆盖的问题。
  • Entry死循环：扩容时存在在原数组和新数组之间的指针切换，如果没有正确地处理链表节点的 next 指针，就可能导致某些节点指向自己，从而形成死循环。
  • 数据丢失：扩容时HashMap 的元素会被重新散列并放入新的数组桶中。如果在处理过程中存在指针的错误（例如链表 next 指针没有正确地更新），就可能发生丢失元素的情况，某些元素可能无法在新的数组中找到正确的位置，导致这些元素丢失。
• 如果要保证线程安全，可以通过这些方法来保证：
  多线程环境可以使用Collections.synchronizedMap( )同步加锁的方式，但是这种方法是全局锁synchronized，很影响性能，不如使用ConurrentHashMap的分段锁，更适合高并发场景使用。

HashMap的put流程（jdk8）

1. 根据要添加的键的哈希码（hashcode方法）得出在数组中的位置，即找到桶
2. 检查该位置是否为空（即没有键值对存在）
3. 若该位置已经存在其他键值对，检查该位置的键值对的键（equals方法）是否与要添加的键值对相同，若相同则新值覆盖旧值。put结束
4. 若和键值对的键不相同，则再遍历链表或红黑树（遍历桶）来查找是否有相同的键和值，若有，则新值覆盖旧值，若无，则新值加到链表或红黑树中。
5. 检查链表长度是否达到8且HashMap的数组长度是否大于等于64，是则将链表转换为红黑树。
6. 检查负载因子是否超过阈值（默认为0.75），若键值对的数量（size）与数组长度（初始16）的比值大于阈值，则需要进行扩容操作。
7. 扩容操作：创建一个新的两倍大小的数组。将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。更新HashMap的数组引用和阈值参数。

HashMap的get方法哪里不安全

• 空指针异常：在HashMap没有被初始化时如果尝试用null作为键调用get方法会抛出空指针异常。如果HashMap已经初始化，使用null作为键是允许的，因为HashMap支持null键。
• 线程安全：HashMap本身不是线程安全的。例如在一个线程中调用get方法而另一个线程同时增加或删除元素，可能会导致读取操作得到错误的结果或抛出ConcurrentModificationException。如果需要在多线程环境中使用类以HashMap的数据结构，可以考虑使用ConcurrentHashMap。

HashMap为啥用String作为key

String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性。

为什么HashMap要用红黑树而不是平衡二叉树

平衡二叉树追求的是一种“完全平衡”状态：任何结点的左右子树的高度差不会超过1，优势是树的结点是很平均分配的，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
红黑树不追求这种完全平衡状态，而是追求一种“弱平衡”状态：整个树最长路径不会超过最短路径的2倍，不会像平衡二叉树一样频繁左右旋，也就是栖牲了一部分查找的性能效率来换取一部分维持树平衡状态的成本。

HashTable

内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。

HashSet

底层由HashMap实现，key就是hashset的值，所有的key的value相同，是一个名为PRESENT的Object类型常量。

LinkedHashSet

底层由LinkedHashMap实现，继承了HashSet类，使用双向链表维护元素插入顺序。

TreeSet 

底层由TreeMap实现（红黑树），添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序（自然顺序，比如插入1，3，2，输出出来是1，2，3）