dslztx
0%

HashMap和ConcurrentHashMap

发表于 更新于 专题于 ， ， Disqus：

本文介绍JDK 1.8下的HashMap和ConcurrentHashMap实现。

一、HashMap

基本描述：

  • 不用于并发场景的“映射表”
  • “键”允许NULL值，“键值”允许NULL值。因此如果取某一个键的值，当取到NULL键值有两种含义：1）对于该键不存在相应的映射记录；2）对于该键存在相应的映射记录，但是其键值为NULL
  • 底层是“节点数组”，对键作哈希计算（准确来说是“3次哈希计算”），映射到的节点数组中的节点被称为“槽”，不同键同槽碰撞的解决策略是“链地址法”，对应的链可称之为“碰撞冲突链”，为优化过长（超过一定阈值）“碰撞冲突链”的操作性能，将其转换为红黑树结构；后续红黑树如果过短，再退化成普通的链表结构
  • 涉及到两类大小——“映射记录大小”和“节点数组大小”，当满足条件时，会对节点数组大小进行扩容
  • 时间复杂度
    • 增：不碰撞，是O(1)；碰撞，假定碰撞冲突链长度为K，在转换为红黑树之前是O(K)，在转换为红黑树之后是O(logK)
    • 删：不碰撞，是O(1)；碰撞，假定碰撞冲突链长度为K，在转换为红黑树之前是O(K)，在转换为红黑树之后是O(logK)
    • 改：不碰撞，是O(1)；碰撞，假定碰撞冲突链长度为K，在转换为红黑树之前是O(K)，在转换为红黑树之后是O(logK)
    • 查：不碰撞，是O(1)；碰撞，假定碰撞冲突链长度为K，在转换为红黑树之前是O(K)，在转换为红黑树之后是O(logK)

1.1、哈希和碰撞

1、哈希算法

  1. 第一次哈希：键的hashCode()方法值
  2. 第二次哈希：其源代码见“源代码1”，h ^ (h >>> 16)其含义是：计算保留高位比特信息，以利于第三次哈希后均匀散列到槽
  3. 第三次哈希：本次哈希是为了散列到槽，其计算公式为p & (n-1)[假定节点数组大小为n，经过前两次哈希的结果值为p]

源代码1：

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、碰撞解决策略
碰撞可通过“链地址法”解决，对应的链可称之为“碰撞冲突链”，假定链表的长度为K。
当为普通链表时，增删改查的时间复杂度为O(K)，故为优化操作性能，当链表长度>=TREEIFY_THRESHOLD(8)时，将其转换为红黑树，此时增删改查的时间复杂度为O(logK)；另外当红黑树大小满足条件<=UNTREEIFY_THRESHOLD(6)时，红黑树退化为普通链表。

1.2、大小

HashMap涉及到两类大小：映射记录大小和节点数组大小。

1.2.1、映射记录大小

指HashMap中映射记录数量，比如“节点数组大小为8，在且只在第3个节点（槽）有一个长度为4的链表（碰撞冲突链），则映射记录大小为4”：

  • 对应于实例成员变量transient int size
  • 对应于实例成员方法public int size()的返回值（不考虑映射记录大小大于Integer.MAX_VALUE的情形），该方法直接返回成员变量size的值，因此时间复杂度O(1)

1.2.2、节点数组大小

指HashMap中节点数组大小，即成员变量 transient Node<K, V>[] table的大小。

节点数组大小为2的整数次幂，其好处如下：

  • 第三次哈希的计算公式为p & (n - 1)[假定节点数组大小为n，经过前两次哈希的结果值为p]，由于n=2^x，则n-1的低比特位全为1，使得“&”运算能够充分利用p数值相应比特位位置的信息，利于均匀散列到槽
  • 后续可知，节点数组大小为2的整数次幂，加快了扩容过程中的“rehash”操作

接下来介绍“初始化节点数组大小”和“扩容节点数组大小”，在介绍之前首先作以下几点说明：

  • 为简化描述和便于理解，不考虑极值大小的情况，比如节点数组大小>=MAXIMUM_CAPACITY(1 << 30)
  • 成员变量loadFactor的语义是：负载因子，当映射记录大小 > 节点数组大小*loadFactor时扩容节点数组
  • 成员变量threshold的语义是：
    • 当节点数组未初始化时：threshold > 0表示节点数组初始化大小等于threshold；threshold = 0表示节点数组初始化大小等于DEFAULT_INITIAL_CAPACITY(1 << 4)
    • 当节点数组已初始化时：threshold=节点数组大小*loadFactor，即当映射记录大小 > threshold时扩容节点数组
1.2.2.1、初始化

惰性初始化，即“不是一开始就初始化，而是在需要时才初始化”。

1、构造方法
构造方法设置成员变量threshold和loadFactor的值，具体描述如下表。

构造方法\成员变量 threshold loadFactor
HashMap() 等于“实例初始化默认0值” 等于DEFAULT_LOAD_FACTOR(0.75f)
HashMap(int initialCapacity, float loadFactor) 等于tableSizeFor(initialCapacity) 等于传入的loadFactor
HashMap(int initialCapacity) 等于tableSizeFor(initialCapacity) 等于DEFAULT_LOAD_FACTOR(0.75f)
HashMap(Map<? extends K, ? extends V> m) 等于tableSizeFor( m.size() / loadFactor + 1.0f ) 等于DEFAULT_LOAD_FACTOR(0.75f)

有两点说明：

  1. 上述tableSizeFor方法（源代码见“源代码2”）的作用是：返回大于等于输入参数且为最近的“2的整数次幂”的数值，比如“输入10，返回16”
  2. 后续可知，扩容操作十分耗费性能（申请新节点数组内存资源，对原映射记录进行rehash操作），因此在创建HashMap实例时最好能够根据预估的“映射记录大小”预计算“节点数组的初始化大小”。由于当映射记录大小 > 节点数组大小*loadFactor时进行扩容，故为尽量避免扩容，须使得满足节点数组大小 >= 映射记录大小/loadFactor不等式，上述第4个构造方法中的m.size() / loadFactor + 1.0f就是基于该不等式的一个常用等式，我们自己在创建HashMap实例时也应该使用该等式预计算传入的节点数组初始化大小

源代码2：

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2、惰性初始化
根据threshold的值分为两种情况：

  • threshold=0：节点数组初始化大小等于DEFAULT_INITIAL_CAPACITY(1 << 4)，新threshold值等于DEFAULT_INITIAL_CAPACITY(1 << 4) * DEFAULT_LOAD_FACTOR(0.75f)
  • threshold>0：节点数组初始化大小等于threshold，新threshold值等于threshold * loadFactor
1.2.2.2、扩容

节点数组只有“扩容”，没有“收缩”，扩容条件为：映射记录大小 > threshold。

扩容过程描述如下：

  • 2倍扩容。节点数组新大小是原来的2倍，成员变量threshold新值也是原来的2倍（语义不变）
  • 对原映射记录进行rehash操作：假设原节点数组大小为n，有一个“键”的二次哈希值为hash，则原散列到槽(n -1) & hash，现散列到槽(2*n - 1) & hash，这里可以有个计算优化，我们知道节点数组大小n是2的整数次幂，分析其比特位特点可知，对于以上运算，低n位比特位的&运算结果不变，故只需要计算从低位往高位方向第n位的比特位&结果，即n & hash

1.3、与JDK 1.6中HashMap实现比较

与JDK 1.6中HashMap实现相比，主要有以下几点改进：

  1. 在JDK 1.8中，当碰撞冲突链过长时，会转化为红黑树，优化操作性能；而在JDK 1.6中，没有该优化
  2. 对于节点数组的初始化，JDK 1.8中是惰性的，JDK 1.6中是即时的
  3. 对于第二次哈希算法，JDK 1.8中的实现相较JDK 1.6较为简单，其后果就是“第三次哈希后散列到槽相较不均匀，碰撞冲突链的长度相较更长的概率增大”，但是由于JDK 1.8中引入了过长碰撞冲突链转换为红黑树的机制，使得上述问题得到了充分的补偿
  4. 两者的实现都是针对非并发场景的，如果用于并发场景，可能会出现一些线程安全问题，比如：
    • 映射记录丢失。在JDK 1.8中并发执行p.next = newNode(hash, key, value, null)语句；在JDK 1.6中并发执行table[bucketIndex] = new Entry<K,V>(hash, key, value, e)语句
    • 扩容导致死循环。在JDK 1.6中，扩容会导致死循环，问题相关源代码见“源代码3”，一种可能是：线程A执行语句A.next = newTable[i]; newTable[i] = A;，线程B并发执行语句A.next = newTable[i];，然后最后有A.next = A;，导致产生了一个链表死循环；在JDK 1.8中，对此予以了改进，不存在扩容导致死循环问题

源代码3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];    //1
                newTable[i] = e;         //2
                e = next;
            } while (e != null);
        }
    }
}

二、ConcurrentHashMap

基本描述：

  • 用于并发场景的“映射表”，使用“CAS自旋锁+synchronized锁”实现线程安全
  • “键”和“键值”都不允许NULL值。因此如果取某一个键的值，当取到NULL键值只有一种含义——对于该键不存在相应的映射记录
  • 底层是“节点数组”，对键作哈希计算（准确来说是“3次哈希计算”），映射到的节点数组中的节点被称为“槽”，不同键同槽碰撞的解决策略是“链地址法”，对应的链可称之为“碰撞冲突链”，为优化过长（超过一定阈值）“碰撞冲突链”的操作性能，将其转换为红黑树结构；后续红黑树如果过短，再退化成普通的链表结构
  • 涉及到两类大小——“映射记录大小”和“节点数组大小”，当满足条件时，会对节点数组大小进行扩容
  • 时间复杂度：如果不考虑“CAS自旋”基本跟HashMap一致；否则，难以忽略而不可分析

2.1、哈希和碰撞

核心基本跟HashMap一致，除了以下两点：

  • 需要考虑线程安全问题
  • 第二次哈希算法不同，其源代码见“源代码4”，与HASH_BITS(0x7fffffff)进行&运算是为了避免结果值与3个特殊哈希值（MOVED = -1，TREEBIN = -2，RESERVED = -3）冲突

源代码4：

1
2
3
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

2.2、大小

ConcurrentHashMap涉及到两类大小：映射记录大小和节点数组大小。

2.2.1、映射记录大小

指ConcurrentHashMap中映射记录数量，比如“节点数组大小为8，在且只在第3个节点（槽）有一个长度为4的链表（碰撞冲突链），则映射记录大小为4”：

  • 对应于实例成员变量transient volatile long baseCount和transient volatile CounterCell[] counterCells。在没竞争的时候只使用baseCount，在有竞争的时候同时使用baseCount和counterCells
  • 对应于实例成员方法public int size()/public long mappingCount()的返回值（当映射记录大小大于Integer.MAX_VALUE时，后者更为准确；但是一般情况下用前者就足够了），这两个方法返回都基于成员变量transient volatile long baseCount和transient volatile CounterCell[] counterCells，当没竞争只使用baseCount时，时间复杂度为O(1)；当有竞争同时使用baseCount和counterCells时，时间复杂度不是O(1)

2.2.2、节点数组大小

指ConcurrentHashMap中节点数组大小，即成员变量 transient Node<K, V>[] table的大小。

节点数组大小为2的整数次幂，其好处如下：

  • 第三次哈希的计算公式为p & (n - 1)[假定节点数组大小为n，经过前两次哈希的结果值为p]，由于n=2^x，则n-1的低比特位全为1，使得“&”运算能够充分利用p数值相应比特位位置的信息，利于均匀散列到槽
  • 后续可知，节点数组大小为2的整数次幂，加快了扩容过程中的“rehash”操作

接下来介绍“初始化节点数组大小”和“扩容节点数组大小”，在介绍之前首先作以下几点说明：

  • 为简化描述和便于理解，不考虑极值大小的情况，比如节点数组大小>=MAXIMUM_CAPACITY(1 << 30)
  • 成员变量sizeCtl的语义是：
    • 当sizeCtl < 0时，表示正在扩容过程中或者正在初始化
    • 当sizeCtl >= 0时，
      • 当节点数组未初始化时：sizeCtl > 0表示节点数组初始化大小等于sizeCtl；sizeCtl = 0表示节点数组初始化大小等于DEFAULT_CAPACITY(16)
      • 当节点数组已初始化时：有sizeCtl = 节点数组大小*3/4（即0.75，表现形式为n - (n >>> 2)），此时不可能出现sizeCtl = 0，当映射记录大小 >= sizeCtl时扩容节点数组
2.2.2.1、初始化

惰性初始化，即“不是一开始就初始化，而是在需要时才初始化”。

1、构造方法
构造方法设置成员变量sizeCtl的值，具体描述如下表。

构造方法\成员变量 sizeCtl
ConcurrentHashMap() 等于“实例初始化默认0值”
ConcurrentHashMap(int initialCapacity) 等于tableSizeFor( initialCapacity + (initialCapacity >>> 1) + 1 )
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) 等于tableSizeFor( max(initialCapacity,concurrencyLevel) / loadFactor + 1.0 )
ConcurrentHashMap(int initialCapacity, float loadFactor) 等于this(initialCapacity, loadFactor, 1)
ConcurrentHashMap(Map<? extends K, ? extends V> m) 等于max( tableSizeFor( m.size() + (m.size() >>> 1) + 1 ), 16 )

有两点说明：

  1. 上述tableSizeFor方法（源代码见“源代码5”）的作用是：返回大于等于输入参数且为最近的“2的整数次幂”的数值，比如“输入10，返回16”
  2. 后续可知，扩容操作十分耗费性能（申请新节点数组内存资源，对原映射记录进行rehash操作），因此在创建ConcurrentHashMap实例时最好能够根据预估的“映射记录大小”预计算“节点数组的初始化大小”。由于当映射记录大小 >= 节点数组大小*3/4时进行扩容，故为尽量避免扩容，须使得满足节点数组大小 > 映射记录大小*4/3不等式，上述构造方法中的(initialCapacity + (initialCapacity >>> 1) + 1)/(m.size() + (m.size() >>> 1) + 1)（即：映射记录大小*3/2+1）和max(initialCapacity,concurrencyLevel) / loadFactor + 1.0（该等式满足条件与否跟loadFactor值有关，一般取值为0.75f，此时是满足条件的）就是基于该不等式的两个等式。很明显，跟HashMap不同，这里的预计算在构造方法内部自动完成，而在HashMap处预计算需要在外部手动完成，后者反人性

源代码5：

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2、惰性初始化
根据sizeCtl的值分为两种情况：

  • sizeCtl=0：节点数组初始化大小等于DEFAULT_CAPACITY(16)，新sizeCtl值等于DEFAULT_CAPACITY(16) * 3/4
  • sizeCtl>0：节点数组初始化大小等于sizeCtl，新sizeCtl值等于sizeCtl * 3/4
2.2.2.2、扩容

节点数组只有“扩容”，没有“收缩”，扩容条件为：映射记录大小 >= sizeCtl。

扩容过程描述如下：

  • 2倍扩容。节点数组新大小是原来的2倍，成员变量sizeCtl新值也是原来的2倍（语义不变）
  • 对原映射记录进行rehash操作：假设原节点数组大小为n，有一个“键”的二次哈希值为hash，则原散列到槽(n -1) & hash，现散列到槽(2*n - 1) & hash，这里可以有个计算优化，我们知道节点数组大小n是2的整数次幂，分析其比特位特点可知，对于以上运算，低n位比特位的&运算结果不变，故只需要计算从低位往高位方向第n位的比特位&结果，即n & hash

需要注意的是，跟HashMap的设计单线程扩容不同，ConcurrentHashMap的扩容被设计为支持并发的，其过程描述如下：

  1. 线程A增加映射记录，使得进入扩容过程，节点数组根据特定策略划分为K个扩容区间，线程A默认根据扩容区间索引位置从高到低逐次完成所有扩容区间的扩容
  2. 后续有线程B，C，D，…，根据其操作类型分为两类：
    • “增、删、改”映射记录，根据定位到槽S的状态分为两种情形：1）槽S已被标记为“扩容态（槽的第一个节点为ForwardingNode节点，其成员变量hash的值为MOVED(-1)）”，则并发抢占未完成扩容区间帮助扩容，只有加快完成扩容过程，槽S才能被正常操作；2）否则，正常操作成功，即“在扩容过程中，是可能正常操作成功的”
    • “查”映射记录，根据定位到槽S的状态分为两种情形：1）槽S已被标记为“扩容态（槽的第一个节点为ForwardingNode节点，其成员变量hash的值为MOVED(-1)）”，转发调用ForwardingNode节点的Node<K, V> find(int h, Object k)方法完成查找；2）否则，正常操作成功，即“在扩容过程中，是可能正常操作成功的”
  3. 直到扩容完成：可能是线程A独自完成所有K个扩容区间的扩容，也可能是线程A与其他几个线程共同完成所有K个扩容区间的扩容

2.3、与JDK 1.6中ConcurrentHashMap实现作比较

与JDK 1.6中ConcurrentHashMap实现相比，主要有以下几点改进：

  1. 在JDK 1.8中，当碰撞冲突链过长时，会转化为红黑树，优化操作性能；而在JDK 1.6中，没有该优化
  2. 对于节点数组的初始化，JDK 1.8中是惰性的，JDK 1.6中是即时的
  3. 对于第二次哈希算法，JDK 1.8中的实现相较JDK 1.6较为简单，其后果就是“第三次哈希后散列到槽相较不均匀，碰撞冲突链的长度相较更长的概率增大”，但是由于JDK 1.8中引入了过长碰撞冲突链转换为红黑树的机制，使得上述问题得到了充分的补偿
  4. 对于线程安全的实现，JDK 1.6采取“分段+分段锁（ReentrantLock）”的方案，JDK 1.8采取“CAS自旋锁+synchronized锁”的方案，前者的并发粒度为分段数量（默认为16），后者的并发粒度可近似认为是节点数量（槽数量），后者的并发性能大大提升

参考文献

[1]https://www.yinxiang.com/everhub/note/b612e3b9-cb07-4c7a-85a2-4eeb897ee1d4
[2]https://www.cnblogs.com/loading4/p/6239441.html
[3]https://stackoverflow.com/questions/53493706/how-the-conditions-sc-rs-1-sc-rs-max-resizers-can-be-achieved-in
[4]https://juejin.cn/post/6844903607901356046

您的支持将鼓励我继续分享！