HashMap
底层原理
- 采用数组 + 链表 + 红黑树的数据结构。
- put 时，先对键做 hash 计算，再通过位运算得到它在数组中的位置，通过尾插法添加数据，添加后判断是否红黑树转换以及扩容(resize)。
- get 时，先对键做 hash 计算，再通过寻址算法得到它在数组中的位置，通过键对象的 equals() 方法遍历链表或红黑树得到 value。
put 实现
-
计算键的 hashcode 值（键对象 hashCode 与其高16位做异或运算）
(h = key.hashCode()) ^ (h >>> 16) 如果散列表为空时，调用 resize() 初始化
如果没有发生碰撞，直接添加元素到散列表中去
-
如果发生了碰撞(hashCode 值相同)，进行三种判断
- == & equals 相同，则替换旧值
- 如果是红黑树结构，就调用树的插入方法
- 链表结构，尾插法。插入后判断链表个数是否达到 8，若达到则构建红黑树替换链表；否则遍历替换旧值
如散列表的容量大于阀值，则进行 resize() 扩容(1. 数组长度2倍；2. 调整 key 所属数组位置 )
loadFactor
loadFactor 表示 HashMap 的拥挤程度，影响hash碰撞概率。
- 加载因子越大，扩容的次数越少，但会导致碰撞几率增加，降低查询效率。加载因子越小，扩容次数约多，降低存储效率。
- 如果存储数量已知，通过实际存储数量 ÷ 0.75 来计算出容量，避免扩容。
使用红黑树
- 为什么不一开始使用红黑树：相同数据量下红黑树占用的空间是链表的2倍 , 考虑到时间和空间的权衡 , 只有当链表的长度达到阈值时才会将其转成红黑树
- 为什么转换红黑树阈值为 8：遵循泊松分布, 链表长度达到 8 的概率是 0.00000006, 几乎不可能会使用到红黑树 , 所以使用 8 作为一个分水岭
- 为什么转换链表阈值为 6：当我们有频繁的添加和删除操作时，hash碰撞产生的节点数量一旦在7附件徘徊就会造成红黑树和链表的频繁转换，此时我们大多数的性能就都耗费在了链表 → 红黑树和红黑树 → 链表，所以将长度为7作为一个缓冲地段从而选取了6作为阈值
8 与 7 版本的不同
- hash 算法优化
- 链表头插法 改为 尾插法
- 引入红黑树
如何获取线程安全的集合
Collections提供的方法构造线程安全de 集合
- 装饰器模式，本质是对集合的所有操作前加锁
线程安全的原因
ConcurrentHashMap
ConcurrentHashMap
如何保证线程安全
- volatile 保证可见性
- CAS 乐观锁 + synchronized 细粒度的同步控制
put 过程
如果数组还未初始化，那么进行初始化，这里会通过 CAS 进行初始化
计算 key 的 hash 值并进行位运算得到数组所属位置，如果链表还不存在，那么通过一个 CAS 操作来设置新建的Node元素
如果链表/红黑树存在，但是数组元素的 hash 值是 -1，说明此时正在进行迁移操作，当前线程辅助迁移。
-
非迁移状态时，需要获取该位置数组元素对象的锁，在锁定的情况下执行链表或者红黑树的插入或更新
- 如果数组元素的 hash 值大于0，说明是链表结构，则对链表插入或者更新
- 如果数组元素类型是TreeBin，说明是红黑树结构，则按照红黑树的方式进行插入或者更新
如果是链表结构，需要判断链表中元素的数量是否超过8（默认），一旦超过就要转换红黑树。
ConcurrentHashMap 1.8 较 1.7 的改变
HashTable -> ConcurrentHashMap 1.7 -> ConcurrentHashMap 1.8 的优化路径
