jdk8 版本 CurrentHashMap 中 bin 的修改加了 synchronized。是因为扩容吗？如果不扩容是否可以不加 synchronized。

[22yune]

[guyeu]

我猜你是说 ConcurrentHashMap 。。。没有见过 java8 之前的 ConcurrentHashMap，我猜以前也是有锁的，可能不是这个关键字？

[22yune]

@guyeu -_-|| 是 ConcurrentHashMap 。之前也有锁，segment 继承 ReentrantLock 。

之前是按 segment 锁的。segment 里面是 table 。jdk8 版本支持的并发度更高了。每个 bin 一个锁。

ConcurrentHashMap 对单个 KV 对的操作应该是不需要锁的（不同的 Key 之间是没有关系的，Map 只需保证对 KV 的 CURD，单个 Key 可以用 CAS 不需要锁），对 size 这种跨 Key 的接口提供的都是快照，不准确的。

我想是因为扩容才需要锁定，否则转移的时候会丢失。

[smilekung]

因为链表修改也是要加锁吧，不然并发下会丢数据

[22yune]

@smilekung 恩
但假设不用链表，也用 ConcurrentHashMap 呢？

不考虑 hash 完全相同的情况。也就是假设没有 hash 碰撞，是否可以完全不用锁？

就像现在的 ConcurrentHashMap 是每个 bin 一个锁，如果没有碰撞就是完全并发了。

我发现与 1.6 版本可以单个 segment 扩容不同，1.8 版本是整个表扩容。

我觉得在 hash 分布不均匀的时候，只在密度大的地方扩容，应该可以节省空间。

且用 map 替换链表应该也可以提高并发读。除非 hash 完全相同才用链表或红黑树。hash 不同时用 HashMap 是最快的。

[Hurriance]

不是。扩容跟 synchroized 没有直接关系吧。ConCurrentHashMap 是多线程安全的 HashMap 来的吧，就是为了实现线程安全设计的，必定是要加入锁的，1.7 是 synchrroized 加在每个 segment 上的，1.8 是 CAS+synchroized 加在每个结点上的。解决扩容链表成环的解决方案是改成尾插法吧。

[Hurriance]

ConCurrentHashMap--> ConcurrentHashMap

[iEverX]

@22yune #4

@22yune #4

> 不考虑 hash 完全相同的情况。也就是假设没有 hash 碰撞，是否可以完全不用锁？
> 就像现在的 ConcurrentHashMap 是每个 bin 一个锁，如果没有碰撞就是完全并发了。

如果确认元素数目小于 capacity，并且 hash 后取模绝不冲突，可以认为退化成了一个数组。那就是数组的元素访问是否是线程安全的。那需要有 volatile

[22yune]

@Hurriance 链表也可以不加锁，如链表本身就是线程安全的。但这样得不偿失。

我说不需要加锁是从 ConcurrentHashMap 提供的接口语义看，key 之间没有关系，更新锁定 key 就可以了。

@iEverX
但实际用的链表导致 key 之间有关系，维护起来需要锁。如果某些情况（ hash 碰撞但不完全相同）改用 ConcurrentHashMap 代替链表保存数据是不是有#4 说的更好的效果。

与数组是不同的，这个按 hash 分布的密度分布分配空间，不均匀分布。数组按 hash 范围分配空间，均匀分布。我假设是说明一个可以优化的场景，就像链表长度到 8 转红黑树，我的意思是说 hash 不完全相同转 map 。

[yeqizhang]

有没有老哥知道哪一篇网文解释的好 jdk7 的 HashMap 扩容时成环的原因，我在网上就没找到靠谱点的……总感觉都写的不太对

[Aresxue]

题主可能是想通过无锁化来基于 HashMap 创造一种新的更高性能的并发容器，但我觉得难点其实在于 hash 冲突的问题，一个 hash 碰撞率极低的算法它的实现是极为繁琐的，哪怕你实现了它的性能必然也是很低下的，所以很多人才没有朝这个方向发展，就像都知道 RSA 的安全性更高，实际代码中加密却还大多数是 MD5

[22yune]

@yeqizhang 我没有装 jdk7，看了下网上的文章及文中贴出的关键代码 transfer 方法。下面是我根据文章的理解。

关键代码 e.next = newTable[i]; newTable[i] = e;

transfer 中 table 是共享的，transfer 中只修改了 table 中 node 的 next 。next 会指向 newTable，newTable 也 可能 会通过 next 传播到线程外。

说可能是因为 线程 A 对 next 的修改不知道什么时候传播到线程 B 。线程 B 读到的 next 指向原来的 node，也可能指向线程 A 中 newTable 的 node 。

假设 table 中有一个 bin 是 a->b->c->null 。正常情况下，单线程 A 会把这个 bin 移到 newTable，变成 c->b->a->null 。

多线程情况下。线程 A 遍历到 b 了，产生的新链是 b->a->null 。

线程 B 开始遍历，这个时候线程 A 的修改还没传播到线程 B，所以线程 B 还是按 a->b->c->null 遍历。

当线程 B 移完了 a，新链是 a->null 。开始移 b 的时候，线程 A 的修改传播到线程 B 了，这时线程 B 就会按 b->a->null 遍历。

线程 B 按 b->a->null 遍历到 a 后，产生的新链就是 a->b->a 。这个就是环了。

即，正常按 a->b->c->null 遍历，翻转成 c->b->a->null ；多线程情况下，遍历到 b 时，变成按 a->b->a->null 遍历了。翻转的结果就是 a->b->a 了。

总结

单线程情况下 链表翻转了。多线程情况下，前面的线程正常翻转，后面的线程翻转到半途中链表已经变成了翻转后的，这时再翻转就是回头路了。

[22yune]

@Aresxue 是的

我是希望能通过分层 Hash 来解决这个问题。并不是依赖实现 hash 碰撞率极低的算法。

如在现有实现下，假设是 len=32 的 table 。当 hash 碰撞时，说明 hash 后面 5 位是相同的。如果 bin 再通过 hash 另外的 27 位，均匀分布的概率相比 32 位时应该会更大。

而且（我感觉很矛盾） 32 位时用 HashMap 平衡时间与空间，为何里面的 bin 不能用 HashMap，而用链表或红黑树？

[yeqizhang]

@22yune 昨晚后来我用谷歌搜了一下就比百度出来的结果好的多。
其实主要是很多文章都没讲出最重要的一句前提是 Entry<K,V> next = e.next; ，

假设链表为 a->b->null

一个线程 1 刚好第一次循环执行完 Entry<K,V> next = e.next;，已经拿到之前的链表指向关系，即 e 为 a，则 next 是 b，并且 e.next = newTable[i];设置了链表节点 a 的下个节点为 null，现在不考虑 b 节点的链表结构意图为 a->null，下次循环处理 b ；

实际上另外一个线程 2 已经把链表倒转过来成了：b->a->null，

所以第二次内循环处理 b 节点时，next 是 a ！！！，而这里 e.next = newTable[i];设置了链表节点 b 的下个节点为 a ；这里链表结构图为 b->a->null(和线程 2 的结果一致)，暂时没有问题，但还要处理 next a 。

第三次循环处理 a，next=a.next 为 null，重点来了：
e.next = newTable[i];设置了链表节点 a 的下个节点为 b ！！！改变了原来 a->null，这时候链表就成了，ab 互相指向，没有 null ！！！因为这个循环里 next 变量为 null 所以没有下次循环，循环也可以正常结束。(线程 2 两次循环就结束了)

而扩容结束后，因为 ab 这个环的原因，get 使用 next 遍历链表就会死循环。

我这里相当于自己总结了一下做个笔记，谢谢你的回答，我感觉别人总结的东西我都比较难理解，因为每个人的思维方式、理解能力、知识储备等不太一样，我写了这么一些应该你也看不下去，如果发现写的有问题麻烦帮忙指正一下~

[Aresxue]

@22yune 你分层是有限的，你的 hashCode 的位数总会被使用完, 而你分层越多，你的容器的容量就会越小。这两个其实还可以接受, 因为正常使用中容量也许不会很大(或者我们就是要创造一种需要结合业务使用量分配层数的容器)，更加致命的是随着容器的层数的增加，扩容带来的开销成倍增长，在理想情况下可以并发进行，但如果遭遇 hash 攻击这种估计瞬间就崩溃了。不过我觉得这个容器还是很有思考和时间意义的，分多少层？每层限量又是多少?我该是扩容下层还是当前层亦或是上层？

[22yune]

@Aresxue 是的，问题还很多。你问的问题，有一些不成熟的思路。我初始想法是把现有的 ConcurrentHashMap 中的红黑树（链表不需要）在某些情况下换成 ConcurrentHashMap （ hash 攻击不在情况内）。

我希望分层是基于密度分布的。也就是基于 hash 的分布而分布。关于分多少层和在哪里分层都应该是基于分布比例来。就像 28 法则里面的 2 可能还适用 28 法则也可能不适应了。基于单个 bin 中数量与整体容量的比例来估算。

hash 有 32 位，值范围 1<<32 。假设 table 的长度 32，容量 24.假设 24 个中有 8-12 个落在一个 bin.通过统计同一个 bin 中 27 个位的分布，取其中分布最均匀的 4 位 hash 到一个长度 16 的 table 。（分布均匀度计算方法：如指定位 1 的比例；如第 7 位 1 与 0 一样多，这个位分布就比较均匀。应该有好的数学算法）。

假如容量 24 已经满了后，又插入一个，这个时候应该扩容了。该扩容 32 的表还是 16 的表？

如果新插入的落入了 16 的表，而 16 的表容量 12 还没满的话，应该不用扩容。如果 16 的表容量 12 已满的话，应该扩容 16 的表。

如果新插入没有落入 16 的表。应该技术除了 16 的表的负载，方便起见可以把 16 的表的负载排除在 32 的表之外。如 16 的表中有 12 个，32 的表中有 12 个，则 32 的表的负载为 12/32 或 13/32.

也就是说对于在哪里扩容的问题，把 bin 是 map 的负载排除计算容量，来决定 table 是否要扩容。有个问题，主 table 扩容后子 table 怎么办？

对于分层，是根据单个 bin 占重容量的比例或者 8 个以上就用子 table （与前面按密度分配矛盾）？（衡量标准是计算用子 table 的优缺点）；

上面只是记录些我的思路，写的不清不楚（本来也没想清楚）。打扰见谅，可以不用回复。

[Aresxue]

@22yune 你这个东西越说越像 B 树了。。。其实我觉得这种东西一定要结合实际业务场景来思考，一定要能解决在某种情况下的技术痛点，在某些场景下比 HashMap 更优更让程序员"偷懒"。 就好比 HashMap 红黑树的树化阈值是 8，是因为 hash 碰撞 8 次的可能性是亿分之六(假设数据遵从泊松分布)，所以它在实际使用中几乎很少树化（更多是为了应对 hash 攻击），但在某些领域要求极其严苛的情况下，你能将这亿分之六都处理好那么你这个东西就有很高的实用价值。

[22yune]

@Aresxue 额（︶︿︶）=凸

我说的就是 hash tree 。刚刚搜了下，已经有这种数据结构了。

[EXChen]

@Hurriance 对的。

[warcraft1236]

借楼，问个问题，如果是这样结构的 ConcurrentHashMap<String, FilterEntity>, FilterEntity 的结构是

{
List<String> accept;
List<String> reject;
}


ConcurrentHashMap 是在 main 方法里边 static final new 的


如果我在多线程里边做的事情是，取到 Map 中的这两个 List，然后做一些事情后，这两个 list 分别 .add 数据


请问这样是线程安全的吗？