投稿
  1. 极客之音首页
  2. 后端开发
  3. Java

老版本ConcurrentHashMap源代码解析

小半 • • Java • 阅读 158

不知道为了什么, 今天想介绍一下Java 7版本ConcurrentHashMap的代码.

构造器

构造器有很多个,不过核心就一个.

public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, 
                         int concurrencyLevel) 

前两个参数,都是我们的老朋友,最后一个ConcurrencyLevel是什么?

他也是我们的老朋友并行度.

并行度是什么?

在去年推荐《算法导论》第三版第27章(第四版变第26章了)多线程算法时候，曾经介绍过这个概念。

假如说有一件工作

  • 我们让1个人去做，理想状态需要1000年，这个值记为.
  • 如果让∞个人去做,  理想状态需要1年完成,  这个值记为
  • , 上面这件事,并发度明显是1000.

在达到并行度之前,增加人数是有意义的,达到以后,增加人力,往往没有什么意义.

切换回ConcurrentHashMap的语境里来, 这里的并发度,指的是,最多同时能有几个线程进行更新.

很明显并行度越大,一个操作对多线程修改的支持越好.调整参数时候, 最好是根据实际工作有多少并行度的需要, 来设置这个参数.

ConcurrentHashMap最大的并行度是多少?

//MAX_SEGMENTS = 1 << 16; 

if (concurrencyLevel > MAX_SEGMENTS)
    concurrencyLevel = MAX_SEGMENTS;

,也就是0b10000000000000000.

怎么在构造器里没看到熟悉的tableSizeFor?

ConcurrentHashMap用的不是HashMap那样的完全延迟初始化, 所以, 他没使用函数,而是写了个循环.

while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
}

这个代码就等价于HashMap里的tableSizeFor.如果愿意降低性能的话,这里可以改成这样:

int sshift = 32 - Integer.numberOfLeadingZeros(concurrencyLevel-1);
int ssize = 1 << sshift;

这个就是Java 17里面tableSizeFor的写法,一回事.都是把数字转成二的幂次就行. 并行度输入的11话,这里就变16了.

分配容量

初始容量如果100话,分割成16份,每人6个.

int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
    ++c;

根据小学算术知识知道,100-16*6=4,有4个会覆盖不到.第二段代码又是来给整数除法填坑的.

初始化

然后又是老一套,初始化第0段,然后塞到一个长度为ssize的table中.

Segment<K,V> s0 =new Segment<K,V>(loadFactor, (int)(cap * loadFactor),(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];

这个代码, 主要目的就是把普通HashMap的table为主的结构,改成table的table结构. 然后给这种table起了个好听的名字, 叫Segment.

相较于HashTable之类全局加一个锁, 这里因为分了很多个子部分,有多个锁.线程们抢着进来时候,因为锁多,并行度就高.效率就快了一点.

isEmpty 判空

普通的HashMap,判断空只要读下size,判断是不是0,就可以了.

但是这里有多段,每个上面都有个count,特别是65535个分段这种,检查一遍要好一会. 看着后面的,前面的突然就被改了.跟打地鼠一样,这怎么办?

损招

有个坏招, 是加个锁,求和一遍,然后判断. 但是这么干,好不容易提起来的并行度,嗖一下就又下去了.

解决办法,double check

  • 先进行第一轮核酸检测, 把所有segment的modCount都给收上来求和,进行混检,求得sum.
  • 如果第一轮混检为0,则认为没为空
  • 如果第一轮筛查不为0,则进行第二轮筛查,同时从sum中扣除modCount.
  • 如果最终sum不为0, 说明有某些段,在两轮检测中发生了变化.

这法子还是不错的,主要是巧妙利用了modCount只增不减的特性.收一轮进行求和,下一轮再减去,如果有变化,就被探测出来了.

size() 

size 这里需要计数, 和前面,也是一样的问题.提供了两种方式:

  • 快方式 fast-path, 就是按照前面2次检测的方式进行统计
  • 慢方式 slow-path, 是在快方式失败2次以后,给每个段加锁,进行统计

这个设计还是很有趣的.

get() &containsKey()

这块看着很乱, 但是其实就是一个特殊写法:

  • 对segments.length取模,获取某一段.
  • 对tab.length取模,获取表里的位置
  • 最后再顺着链表查一查

这里用的是Unsafe上的方法, 所以整体看着乱了些.主要是涉及到了Object的布局和结构问题,这个如果跳过,代码可以改成这样.

int i = (h >>> segmentShift) & segmentMask;
if ((s = segments[i]) == null || (tab = s.table) == null) {
    return null;
}
for (HashEntry<K,V> e = tab[(tab.length - 1) & h]; e != null; e = e.next) {
    if (e.key == key || e.hash == h && key.equals(e.key))
        return e.value;
}
return null;

看起来,清晰了一点. 当然,这是拿性能换的.

containsKey也是类似的,只是找到entry以后不再读取value了.

containsValue() 

这个函数, 自己猜就知道,需要遍历整个哈希表的所有节点,才能检查value是否存在,肯定慢.

而且这里很复杂.

  • 前面遇到过的isEmpty的双重检验手法, 这里有.
  • size里那种快慢检查, 快的不行就上锁,这里还有.
  • get里面奇奇怪怪的Unsafe和链表检查,一样有.只是换了个segmentAt方法.

这个方法本身不难,但是因为复合进来的功能点多,就变得很可观了.看完前面的,这个自然就懂了.

唯一需要注意的, 是这句

outer: for (;;) {

这个语法是一个标准语法,叫标签(label), Java里用来break跳出多层循环的唯一方法.

remove() &replace()

这两个函数的外围都是类似的, 根据hash找到Segment.

if (!tryLock())
    scanAndLock(key, hash);

接着是尝试加锁, 加锁失败就进死循环继续尝试加锁. 到这一步, 就必须看看Segment的结构了.

static final class Segment<K,V> extends ReentrantLock implements Serializable {

他其实是个ReentrantLock的子类.

  • 第一次尝试加锁就是普通的尝试tryLock
  • 进入死循环尝试tryLock后, 会统计一个失败尝试次数.
  • 失败多次以后,会直接调lock进行阻塞式加锁.这里retries从-1开始,里面有个额外的分支用来在偶数次尝试中,检查entry变了的情况.

这里面的最大尝试次数比较有趣,如果是多核,可以尝试64次,单核是1次..

Runtime.getRuntime().availableProceSSOrs() > 1 ? 64 : 1;

剩下的部分,就都差不多了.

replace因为不涉及链结构变化,直接赋值即可.

e.value = newValue; 

remove则需要根据删除的是否是头结点,是把下级节点提上去, 还是用上级节点往下指一下.

if (pred == null)
    setEntryAt(tab, index, next);
else
    pred.setNext(next);

put() &putIfAbsent()&putAll

putAll()函数,就是循环调用了put.

剩下两个函数流程比较清晰,唯一差别是最后一步的参数是true和false控制着在有值时候的行为.整体流程如下:

  • 找到segment
  • 确保他存在(这里存在延迟初始化的问题)
  • 调用segment的put方法

第一步和查找没什么本质区别.

ensureSegment这里比较有趣,他会以第0段,也就是构造器里初始化好的那个为模板,初始化好一个table,初始化好一个Segment,然后给设置到段表里去.

这块主要注意点是反复进行的多重校验,还有下面的Unsafe方法:

  • UNSAFE.getObject
  • UNSAFE.getObjectVolatile

这两者的差别,以及最后把值放回去用的

compareAndSwapObject

这里是个CAS操作.

Segment.put操作

这个方法比较大, 有变化, 所以,和replace,remove一样,需要锁.不过和上面的锁法不太一样, 这里的锁法叫scanAndLockForPut,是单独优化过的.多出来一个创建节点的操作.

if (e == null) {
    if (node == null) // speculatively create node
        node = new HashEntry<K,V>(hash, key, value, null);
    retries = 0;
}

拿到锁以后, 这里代码很长, 但是其实是两个半独立的部分.

前半部分, 就是一直,顺着链往下找啊找. 找到了, 就把value适时塞进去.

for (HashEntry<K,V> e = first;;) {
    if (e != null) {
        K k;
        if ((k = e.key) == key ||
            (e.hash == hash && key.equals(k))) {
            oldValue = e.value;
            if (!onlyIfAbsent) {
                e.value = value;
                ++modCount;
            }
            break;
        }
        e = e.next;
    }
}

后半部分, 解决的是,前面一直都没找到.那就把新节点放在第一个,头结点的位置.原来的头结点,放在他后面.

if (node != null)
    node.setNext(first);
else
    node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
    rehash(node);
else
    setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;

这中间,最值得注意的部分是rehash部分. 这块其实就是相当于resize了. 这段比较长, 理一下是这样:

开头, 翻倍扩容,重算阈值

HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
HashEntry<K,V>[] newTable =
    (HashEntry<K,V>[]) new HashEntry[newCapacity];
int sizeMask = newCapacity - 1;

接着复制单节点内容.

if (next == null)   //  Single node on list
    newTable[idx] = e;

最后,处理需要进行搬家的长链表. 这块比较晦涩.

  • 假设原来数组容量是n,链表的是在k位置
  • 扩容以后,元素要么是在k位,要么是在n+k位置.
  • 链表内元素未来的位置,可能是交错分布,就相当于[k,n+k,k,k,k,n+k,n+k,k,k,k]这样.

每一个连续的部分, 称为一个串(run). 理解这个就可以看懂这段代码了.

找到链表中最后一串的开头.

如果把要搬位置的,不要搬位置的,按照红色黑色染色, 这个链表结构就会变成这样.串的存在就比较明显了.

老版本ConcurrentHashMap源代码解析

搬迁代码的第一部分,主要就是在干这个,找到最后一串的头结点.

for (HashEntry<K,V> last = next;
     last != null;
     last = last.next) {
    int k = last.hash & sizeMask;
    if (k != lastIdx) {
        lastIdx = k;
        lastRun = last;
    }
}
把最后一串塞到指定位置

这部分只有一行,就是把最后一串的头节点给放到数组里.

//把这串链表放到指定位置去.
newTable[lastIdx] = lastRun;

他后面跟着的,也就相当于是放到正确位置了.其实这个是偷性能的方法,这段即使删了,也能运行,只是会有些额外消耗.

遍历链表,把余下元素,逐个插入到正确的位置去
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
    V v = p.value;
    int h = p.hash;
    int k = h & sizeMask;
    HashEntry<K,V> n = newTable[k];
    newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}

关键点在 newTable[k]这句上,这里获取到的可能是和原来节点序号一样的位置,也可能是新位置.随着循环的进行, 链表就这样自动分成了两条,插入到两个不同位置上.

//这里是获取table中的元素
HashEntry<K,V> n = newTable[k];
//这里是在构造器里把刚刚的元素作为新节点的next属性.也就是头插法.
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);

因为这里是从上往下遍历并插入, 链表在rehash过程中会发生头尾倒转.

涂鸦时刻

当然了, 纯看代码不够直观, 还是来画几张图吧.

不同并行度下的ConcurrentHashMap

这里准备16个元素, 按照1-16不同并行度存放一下,结果是这样的.

老版本ConcurrentHashMap源代码解析
老版本ConcurrentHashMap源代码解析
老版本ConcurrentHashMap源代码解析

看图也是意料之中,并发度为1时候, 他跟一个普通的HashTable差别不大.并行度其实就是里面的分段数量(除了需要用二的指数正规化一下).

不同负载因子下的ConcurrentHashMap

现在固定并行度为4,把负载因子从0.5-4变化一下.

老版本ConcurrentHashMap源代码解析
老版本ConcurrentHashMap源代码解析
老版本ConcurrentHashMap源代码解析
老版本ConcurrentHashMap源代码解析

扩容

重点看看扩容的变化, 所以这里放个更高负载的, 并行度倒是无所谓了,所以直接放个2就行.

老版本ConcurrentHashMap源代码解析
插入15前后对比图
老版本ConcurrentHashMap源代码解析
插入19前后对比图

前一张还不明显,这张图里rehash带来的头尾倒转就很明显了.我再加个标注线示意下.

老版本ConcurrentHashMap源代码解析

这里原来的长链,分为了两部分.最后一串(lastRun)是[6-5-0]这串, 他们就被放到了新位置.

  • 蓝色线对应的保持了原顺序
  • 红色线对应的发生了倒转

当然, 这里是因为元素的交错比较简单,可能只有两个序列,能明显看出lastRun在哪儿.

像下面这张,复杂一点,lastRun不一定能一眼看出来是哪部分.

老版本ConcurrentHashMap源代码解析

这份数据交错比较严重,能检查到的lastRun,只有一个元素.余下部分都需要靠第二轮逻辑进行重新插入, 发生了强烈的顺序倒转.

后话

关于这份消失了好多年,再也没人用的Java 7版本ConcurrentHashMap代码, 希望我解释清楚了, 对你有用.

还余下一部分Unsafe可以缓缓,配合对象布局单独说.我们下回再见.


老版本ConcurrentHashMap源代码解析

原文始发于微信公众号（K字的研究）：老版本ConcurrentHashMap源代码解析

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/24721.html

赞 (0)
小半的头像小半
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！