2.10 HashMap & ConcurrentHashMap

2.10.1 HashMap

• put()
  • putVal()
    • 无碰撞, 插入操作
    • 碰撞
      • hash & key一致, 覆盖操作
      • p.next找队尾, 插入
      • 判断是否需要扩容, 即如果size大于capacity * LOAD_FACTOR, 即当前大小大于容量*负载因子, 默认是16 * 0.75, 即12

2.10.2 ConcurrentHashpMap

• put()
  • tryLock()获取segment分段锁
  • 无碰撞, 插入操作
  • 碰撞
    • hash & key一致, 覆盖操作
    • 否则插入队尾
  • 扩容: 通过CAS设置sizeCtl和transferIndex, 协调多线程扩容;核心是transfer()调整节点位置

2.10.3 hash冲突解决方式

1. 开放定址法, 出现冲突则再hash, 产生新的hash值, 直到没有冲突, 如ArrayMap, 再hash包含以下三种:
   • 线性探测法再hash, 发生冲突, 顺序查找下一单元, 直到有空单元或遍完全表
   • 二次探测再hash,
   • 伪随机探测再hash
2. 再hash法, 遇冲突使用别的hash算法再hash
3. 链地址法, 出现冲突则放到key对应的链表, 如HashMap
4. 建立公共溢出区, 将hash表分为基本表和溢出区, 冲突一律放到溢出区

2.10.3 HashMap & ConcurrentHashMap & HashTable区别

• HashTable: 数组+链表实现, key & value均不能为null, 线程安全但对整表加锁, 效率低; 扩容: newSize = 2*oldSize+1
• HashMap: 数组+链表实现, 线程不安全; 扩容: newSize = 2*oldSize
• ConcurrentHashMap: 分段数组+链表实现; 线程安全, 分段加锁, 且读无锁