FAQ-HashMap & ConcurrentHashMap

HashMap

• 数组+链表

• 非同步，可使用 Collections.synchronizedMap 构造同步 HashMap

• 通过“拉链法”实现的哈希表

• 默认容量 16，必须为 2 的幂

• table ，一个 Entry 数组（Entry 实际为单项链表）

• size，键值对数量

• threshold，阈值 = 容量 × 加载因子，用于判断是否需要调整容量

• loadFactor，加载因子，默认 0.75，时间与空间上的一种折中

  • 哈希冲撞

• modCount -> fail-fast 机制

• hash() 计算 key 的 hash 值，供寻找索引使用

• indexFor() 返回数组索引 hash & (length - 1)

• resize() 重新调整大小，重新将元素添加到新数组

• put 元素放在链表表头

• Entry implements Map.Entry ； key, value, next, hash

• HashIterator implements Iterator

  • current, next
  • expectedModCount
  • hasNext(), nextEntry(), remove()

• keySet, entrySet；Set不包含重复元素

• values 为 Collection，可重复

1.8 中使用了红黑树，在某个桶中链表长度达到 8 时，链表会转化为红黑树，提升查找性能 （O(N) -> O(logn)）

• JDK7与JDK8中HashMap的实现

• ConcurrentHashMap

  • 不允许 key/value 为空
  • 1.7
    • 分段锁 Segment 继承 ReentrantLock，分段只在使用时才会创建
      • 一个分段锁定不影响其他分段的访问，提升高并发环境下的处理能力
      • 每个分段其实也是一个表
    • 默认容量 16，默认并发度 16，默认负载因子 0.75
    • put 时会进行 tryLock 一定次数后，若仍无法获取锁，则通过 lock 申请
      • 获得锁后对链表进行遍历查找，无相同节点则将新的 HashEntry 做为链表头
      • 如果容量达到阈值，则对 Segment 进行 rehash 扩容
    • 弱一致性：get, containsKey 没有使用锁，而是通过 Unsafe 的 getObjectVolatile() 提供原子语义
    • size, containsValue
      • 进行两次操作，如果连续两次所有 Segment 的 modcount 和相等，则说明未发生其他修改，返回获得的值
      • 应避免在多线程情况下使用
  • 1.8
    • 放弃分段锁，使用 CAS + synchronized 头节点
    • 与 HashMap 类似，使用 数组+链表+红黑树 实现
    • Node<K,V> implements Map.Entry<K,V> 用于存储键值对
    • TreeNode<K,V> extends Node<K,V> 用于放入 TreeBin 完成红黑树的转换

  • ConcurrentHashMap总结