漫画：什么是ConcurrentHashMap？

冷不防 2024-02-18 18:19 39阅读 0赞

![04596a128824435e83752b7987ef0d2c.jpeg][]

![4762798c9d4f473aa2f312f8dd2c161f.jpeg][]

![20f625bfea974132b567cb7fb759cc63.jpeg][]

![c3a0fa89d2a044af9ffbbfc79da0309f.jpeg][]

————————————

![690a762986e3473ab97ea081f8b3344f.jpeg][]

![fd6b3f67c47e4b5ea0b95caea0ff17b1.jpeg][]

![f3ba8aefce784ec8b3cf7f29d45a8a8f.jpeg][]

![fb64b97b456840d6a92df625c7b7cfa0.jpeg][]

![326ebaa74454450fa36db72f8e1dbc63.jpeg][]

![498d419563324dfbacea218f74c7d515.jpeg][]

![f5994054829944a7b25754ecb07ff9c7.jpeg][]

![32067509b42a4c5abd358e633f02a997.jpeg][]

![c7880bba5e9944e793f679cd0d9f2a4a.jpeg][]

![0f9836eb503f4f04bdd6fbda3dbda89f.jpeg][]

![1d1a4271b7584172b99de690e054aa01.jpeg][]

![a06783541e1643e3b302ba480d3e4b01.jpeg][]

————————————

![2052795f4f334c91959542f2a17525d7.jpeg][]

![eb415a60b5d146e3a975ae6eb0c7deab.jpeg][]

前两期我们讲解了HashMap的基本原理，以及高并发场景下存在的问题。没看过的小伙伴可以点击下面链接：

如果实在懒得看也没有关系，我们来简单回顾一下HashMap的结构：

![5092118c6eca4ba69f29887da4188ced.png][]

简单来说，HashMap是一个Entry对象的数组。数组中的每一个Entry元素，又是一个链表的头节点。

Hashmap不是线程安全的。在高并发环境下做插入操作，有可能出现下面的环形链表：

![904061bc794f4e67a0ed9aae2f137605.png][]

![ff521fd8a369415ea9d240d7ae8af005.jpeg][]

![5828a109196b4afd8c78a43c3ffa01eb.jpeg][]

![83486b03b4994d58a2191c4656bbb8b7.png][]

![a1b0e850b11c4ff38d38d5354cbad922.png][]

![de21b97be1ce48ffb3c207aaf4fce126.jpeg][]

![34604ddf16304a36bf112bb21d0b169d.jpeg][]

![57d9b17a48b74e47b1657967cd9c37fd.jpeg][]

Segment是什么呢？Segment本身就相当于一个HashMap对象。

同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。

单一的Segment结构如下：

![2cea8e2edfde494dbf0333988c48f5c6.png][]

像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个，共同保存在一个名为segments的数组当中。

因此整个ConcurrentHashMap的结构如下：

![2ccf12c1980349e382ce3088dc853317.png][]

可以说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。

这样的二级结构，和数据库的水平拆分有些相似。

![f10dcfd51aa64bad9c7310271ddf6fa7.jpeg][]

![828c671f626048c584bf4f219044a2e2.jpeg][]

![958f1be2fb6a49a583a7f7d9aef91b9d.jpeg][]

Case1：不同Segment的并发写入

![5c19c5021da0475a8b5f69449f2549f0.png][]

不同Segment的写入是可以并发执行的。

Case2：同一Segment的一写一读

![40851a75d322440184ace228869edaa2.png][]

同一Segment的写和读是可以并发执行的。

Case3：同一Segment的并发写入

![dacaa8c462b74751be50a758c65baf0f.png][]

Segment的写入是需要上锁的，因此对同一Segment的并发写入会被阻塞。

由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

![17ced32aa6ff4fe9aff169bb1951a320.jpeg][]

![207d39cedddd46dc9092b6fac3d24e5c.jpeg][]

Get方法：

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象

3.再次通过hash值，定位到Segment当中数组的具体位置。

Put方法：

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象

3.获取可重入锁

4.再次通过hash值，定位到Segment当中数组的具体位置。

5.插入或覆盖HashEntry对象。

6.释放锁。

![471f5f9da0c74ef1a940948a8e4f5593.jpeg][]

![35eef8649a95465db81a87efdcb2362e.jpeg][]

Size方法的目的是统计ConcurrentHashMap的总元素数量， 自然需要把各个Segment内部的元素数量汇总起来。

但是，如果在统计Segment元素数量的过程中，已统计过的Segment瞬间插入新的元素，这时候该怎么办呢？

![fa47efaad25f4a16b3b0d66094a81061.png][]

![b6afab752a3a4abcbbdaad2d85b64cbd.png][]

![d4450d43bcdf42ac94c2a9775387953b.png][]

![d6d8ef730297452a80e9bf754c098f93.jpeg][]

ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：

1.遍历所有的Segment。

2.把Segment的元素数量累加起来。

3.把Segment的修改次数累加起来。

4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。

5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。

6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。

7.释放锁，统计结束。

官方源代码如下：

public int size() \{

// Try a few times to get accurate count. On failure due to

// continuous async changes in table, resort to locking.

final Segment< K, V>\[\] segments = this. segments;

int size;

boolean overflow; // true if size overflows 32 bits

long sum; // sum of modCounts

long last = 0L; // previous sum

int retries = - 1; // first iteration isn't retry

try \{

for (;;) \{

if (retries++ == RETRIES\_BEFORE\_LOCK) \{

for ( int j = 0; j < segments. length; ++j)

ensureSegment(j).lock(); // force creation

sum = 0L;

size = 0;

overflow = false;

for ( int j = 0; j < segments. length; ++j) \{

Segment< K, V> seg = segmentAt(segments, j);

if (seg != null) \{

sum += seg. modCount;

int c = seg. count;

if (c < 0 || (size += c) < 0)

overflow = true;

if (sum == last)

break;

last = sum;

\} finally \{

if (retries > RETRIES\_BEFORE\_LOCK) \{

for ( int j = 0; j < segments. length; ++j)

segmentAt(segments, j).unlock();

return overflow ? Integer. MAX\_VALUE : size;

为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。

为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。

![a2427ee839304349b911e4226f1a0658.jpeg][]

几点说明：

1. 这里介绍的ConcurrentHashMap原理和代码，都是基于Java1.7的。在Java8中会有些许差别。

2.ConcurrentHashMap在对Key求Hash值的时候，为了实现Segment均匀分布，进行了两次Hash。有兴趣的朋友可以研究一下源代码。

[04596a128824435e83752b7987ef0d2c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/50409cd2502547149db4a06652cefed9.png
[4762798c9d4f473aa2f312f8dd2c161f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/3b9c296c63184aa282579297b43a139d.png
[20f625bfea974132b567cb7fb759cc63.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/60880826cb924d55a2a4019aec11adef.png
[c3a0fa89d2a044af9ffbbfc79da0309f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/7ca1204a89ae49ad80eb7f8c4fe33409.png
[690a762986e3473ab97ea081f8b3344f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/357dbf261a5947baa8bd8224055619a5.png
[fd6b3f67c47e4b5ea0b95caea0ff17b1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1fadbf0e0f68480fbce62ceff26eeee2.png
[f3ba8aefce784ec8b3cf7f29d45a8a8f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a23f76651ae448c3915a193eccbe7e7c.png
[fb64b97b456840d6a92df625c7b7cfa0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/fc1b4da74c174a64b9a4a2e73c650414.png
[326ebaa74454450fa36db72f8e1dbc63.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/528f06f868fa440983abbaf41aeca338.png
[498d419563324dfbacea218f74c7d515.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f38d987b722c4d84b89cf41188eadb09.png
[f5994054829944a7b25754ecb07ff9c7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/b16654a2e71e4847b46e20a5e432143b.png
[32067509b42a4c5abd358e633f02a997.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ed1e82fa0d684a818cd295eec1e77be7.png
[c7880bba5e9944e793f679cd0d9f2a4a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4ad0d2c621294e5da1ce2ac30b680ae5.png
[0f9836eb503f4f04bdd6fbda3dbda89f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0bc89968de14461aba613e2661d53806.png
[1d1a4271b7584172b99de690e054aa01.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8495b3bc5dba42abb08ba6913917309d.png
[a06783541e1643e3b302ba480d3e4b01.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c8aee7ee187a43cf85915b6b256fc738.png
[2052795f4f334c91959542f2a17525d7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/92040ed1b70648bc8570e8f6c4ee0f08.png
[eb415a60b5d146e3a975ae6eb0c7deab.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/b8f16b7e0d6949219f3f997189b1cc39.png
[5092118c6eca4ba69f29887da4188ced.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/477b32382262421191a72bbc442ff76f.png
[904061bc794f4e67a0ed9aae2f137605.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/849667a4a8ac443ab138370d37319602.png
[ff521fd8a369415ea9d240d7ae8af005.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/9368c764842b46e28a8839e012e8d311.png
[5828a109196b4afd8c78a43c3ffa01eb.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171120/5828a109196b4afd8c78a43c3ffa01eb.jpeg
[83486b03b4994d58a2191c4656bbb8b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/7437accf95954058b26692b248eb5918.png
[a1b0e850b11c4ff38d38d5354cbad922.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/029c5deb85484f919f60e0f7dd52fb94.png
[de21b97be1ce48ffb3c207aaf4fce126.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/888678de85154d1a8bd497090e43a5c0.png
[34604ddf16304a36bf112bb21d0b169d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/73c153dc9ef7493ab7428fc0424da73d.png
[57d9b17a48b74e47b1657967cd9c37fd.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0790a7140f6944398ff308163bd8ced4.png
[2cea8e2edfde494dbf0333988c48f5c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1f5f356c3cb64e179b1cb9d1a7d3e95e.png
[2ccf12c1980349e382ce3088dc853317.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4813e3fa3e814a4882612e5320d7c788.png
[f10dcfd51aa64bad9c7310271ddf6fa7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/d6a7e600f73747b9b5d11daf4789c16d.png
[828c671f626048c584bf4f219044a2e2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/cdfc15f3f0cd43be868f9c2ab5b4217f.png
[958f1be2fb6a49a583a7f7d9aef91b9d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/695552e401a34ebeaea789ce8c76f151.png
[5c19c5021da0475a8b5f69449f2549f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/88be514ab3f1421fabb3db294ed30842.png
[40851a75d322440184ace228869edaa2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/389f85bd530f41a69d40097af983cff4.png
[dacaa8c462b74751be50a758c65baf0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a93c2ec8c06e40b4b5e8f01bd6243d77.png
[17ced32aa6ff4fe9aff169bb1951a320.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1fe4debcc79c4b8980036fbed5e3673c.png
[207d39cedddd46dc9092b6fac3d24e5c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8907eaf455dd4be4bc7d3a1d3309ae42.png
[471f5f9da0c74ef1a940948a8e4f5593.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ee30e605dcef406fba8c045e828ca773.png
[35eef8649a95465db81a87efdcb2362e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/dd48035be8be483396f4a73ee67198bf.png
[fa47efaad25f4a16b3b0d66094a81061.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c774b02f6f644d0cbc016d4eac79a126.png
[b6afab752a3a4abcbbdaad2d85b64cbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5aae993b6019463e8213a7528e90acfd.png
[d4450d43bcdf42ac94c2a9775387953b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/808973130292478b99e40bcc7674e91c.png
[d6d8ef730297452a80e9bf754c098f93.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/de02b29ea4864cd5aed6c695b2b65e8d.png
[a2427ee839304349b911e4226f1a0658.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/7b9c7e0f858443999405193a2d1c2d18.png