Java 集合框架

Map

1. HashMap

   JDK1.8 中 HashMap 由数组、链表 / 红黑树组成。当节点数大于 8 时转换成红黑树，节点数小于 6 时转换成链表。
   红黑树的红黑规则：

   1. 每个节点不是红就是黑。
   2. 根节点总是黑色的。
   3. 如果节点为红色，则它的子节点必须时黑色的，反之则不一定。
   4. 从根节点到叶节点或空子节点的每条路径必须包含相同数目的黑色节点。

   注意：新插入的节点总是红色的，违背规则 3 的可能性比 4 小。可以通过改变节点颜色、左旋和右旋来修正。

1. hashCode 为什么选 31 作为乘子

   选择质数是为了在哈希桶中最佳地分布数据，避免冲突。
   当质数太小时计算出的哈希值数值不会很大，会分布在一个较小的数值区间内，分布性不佳可能导致冲突率上升。
   当质数太大时计算出的哈希值数值太大，因为 int 作为哈希数据类型，最大容量为 2^32，会溢出。

2. 为什么 HashMap 中数组长度总为 2 的 n 次方

   为了让数组分布均匀，会把 hash 码对数组长度取余hashCode % length，但计算机都是二进制操作，取余运算开销还是很大的。
   当length 总是 2 的 n 次方时，hashCode & (length - 1)运算等价于 hashCode % length,& 效率比 % 更高。所以长度是 2 的 n 次方，是速度上的优化。

3. ConcurrentHashMap

   HashMap在高并发下可能出现死循环，扩容是造成死循环的主要原因。JDK1.8 后修复了死循环，但免不了会有数据丢失以及不准确的情况出现。
   ConcurrentHashMap修改时在没有 hash 冲突时，使用 CAS 实现无锁化修改。hash 冲突下，通过 synchronize 同步锁将对应的桶锁定再修改。

   适用于存储数据较小，读取操作频繁，且不要求强一致性的高并发场景。

List

1. ArrayList

   无参构造一个空集合时数组初始长度为 1，第一次添加元素后会创建长度为 10 的数组，每次扩容为 1.5 倍。

2. CopyOnWriteArrayList

   底层使用数组存储数据，在进行写操作时会创建副本操作，再将数据的引用指向新数组。而读操作还是在原来的数组上进行，内部使用独占锁控制并发修改。

3. LinkedList

   注意：LinkedList 的遍历应使用迭代器，而不是 for 循环。