Java集合

HashMap

1. 扩容

• 默认容量是16,默认负载因子：0.75, 扩容阈值：16 * 0.75 = 12,超过 12：触发 resize()。
• 为什么负载因子是0.75-> 时间 + 空间 的平衡,太小->例如0.5,优点是冲突少，缺点是 浪费内存 扩容频繁。太大-> 例如是负载因子是1 优点是节省空间，缺点是冲突严重，链表会变长。0.75属于经验中的最佳值。也是jdk 作者长期验证的结果。
• Java8 的扩容优化: Java7 扩容:重新 hash,性能差。java8中，因为容量始终：2 的幂，扩容后元素位置：

2.hash 冲突

• 什么是hash冲突：不同的key 计算得到同一个数组下标

•   例如 key1 = index = 3, key 2 = index3 这个就是hash冲突
  

• hash冲突如何解决：java8中是链地址法，同一个桶下面挂链表

       table[3]-> Node-> Node-> Node-> Node     

3.红黑树

• 为什么会引入红黑树：

1. java7中 hashmap的数据结构是 数据+链表 存在的问题就是：链表会很长，查询复杂度是O(n),高并发下性能会严重下降。
2. java8中优化 当链表长度：>=8,并且数组容量：>=64, 链表 -> 红黑树 复杂度O(log n)
3. 为什么链表的长度阈值是8，这个是作者经过统计之后的一个折中值。原因：a: 链表长度达到8的概率极低,达到8的时候也意味着hash 分布很差。b:红黑树维护成本高,占内存,旋转,维护颜色,如果太早树化得不偿失。 4.为什么容量要 >= 64 才树化 实际是优先扩容，而不是树化，因为很多冲突只是数组太小。扩容后数据会分散。

ConcurrentHashMap

ArrayList

LinkedList

CopyOnWriteArrayList