登录注册
最新博客
最新资源下载
ConcurrentHashMap源码解析（3）
勿忘初心2018-12-19 15:58此文已由作者赵计刚授权网易云社区发布。
欢迎访问网易云社区，了解更多网易技术产品运营经验。
4、get(Object key)
使用方法：
map.get("hello");
源代码：
ConcurrentHashMap的get(Object key)
/**
* 根据key获取value
* 步骤：
* 1)根据key获取hash值
* 2)根据hash值找到相应的Segment
* 调用Segment的get(Object key, int hash)
* 3)根据hash值找出HashEntry数组中的索引index，并返回HashEntry[index]
* 4)遍历整个HashEntry[index]链表，找出hash和key与给定参数相等的HashEntry，例如e，
* 4.1)如没找到e，返回null
* 4.2)如找到e，获取e.value
* 4.2.1)如果e.value!=null，直接返回
* 4.2.2)如果e.value==null,则先加锁，等并发的put操作将value设置成功后，再返回value值
*/
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}
Segment的get(Object key, int hash)
/**
* 根据key和hash值获取value
*/
V get(Object key, int hash) {
if (count != 0) { // read-volatile
HashEntry<K, V> e = getFirst(hash);//找到HashEntry[index]
while (e != null) {//遍历整个链表
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)
return v;
/*
* 如果V等于null,有可能是当下的这个HashEntry刚刚被创建，value属性还没有设置成功，
* 这时候我们读到是该HashEntry的value的默认值null,所以这里加锁，等待put结束后，返回value值
*/
return readValueUnderLock(e);
}
e = e.next;
}
}
return null;
}
Segment的getFirst(int hash)
Segment的readValueUnderLock(HashEntry<K, V> e)
注意点：
- 注释很重要，一定要看
- 注释已经写明了详细流程，这里说一下大致流程：
- 根据key获取hash值
- 根据hash值找到相应的Segment
- 根据hash值找出Segment中的哪一个HashEntry[index]
- 遍历整个HashEntry[index]链表，找出hash和key与给定参数相等的HashEntry，例如e
- 如没找到e，返回null
- 如找到e，获取e.value
- 如果e.value!=null，直接返回
- 如果e.value==null,则先加锁，等并发的put操作将value设置成功后，再返回value值
- 如果e.value!=null，直接返回
- 如没找到e，返回null
- 根据key获取hash值
- 对于get操作而言，基本没有锁，只有当找到了e且e.value等于null,有可能是当下的这个HashEntry刚刚被创建，value属性还没有设置成功，这时候我们读到是该HashEntry的value的默认值null,所以这里加锁，等待put结束后，返回value值
- 据说，上边这一点还没有发生过
5、remove(Object key)
使用方法：
map.remove("hello");
源代码：
ConcurrentHashMap的remove(Object key)
/**
* 删除指定key的元素
* 步骤：
* 1)根据key获取hash值
* 2)根据hash值获取Segment
* 调用Segment的remove(Object key, int hash, Object value)
* 1)count-1
* 2)获取将要删除的元素所在的HashEntry[index]
* 3)遍历链表，
* 3.1)若没有hash和key都与指定参数相同的节点e，返回null
* 3.2)若有e，删除指定节点e，并将e之前的节点重新排序后，将排序后的最后一个节点的下一个节点指定为e的下一个节点
* （很绕，不知道JDK为什么这样实现）
*/
public V remove(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).remove(key, hash, null);
}
Segment的remove(Object key, int hash, Object value)
V remove(Object key, int hash, Object value) {
lock();
try {
int c = count - 1;//key-value对个数-1
HashEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
HashEntry<K, V> first = tab[index];//获取将要删除的元素所在的HashEntry[index]
HashEntry<K, V> e = first;
//从头节点遍历到最后，若未找到相关的HashEntry，e==null，否则，有
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue = null;
if (e != null) {//将要删除的节点e
V v = e.value;
if (value == null || value.equals(v)) {
oldValue = v;
// All entries following removed node can stay
// in list, but all preceding ones need to be
// cloned.
++modCount;
HashEntry<K, V> newFirst = e.next;
/*
* 从头结点遍历到e节点，这里将e节点删除了，但是删除节点e的前边的节点会倒序
* eg.原本的顺序：E3-->E2-->E1-->E0，删除E1节点后的顺序为：E2-->E3-->E0
* E1前的节点倒序排列了
*/
for (HashEntry<K, V> p = first; p != e; p = p.next)
newFirst = new HashEntry<K, V>(p.key, p.hash, newFirst, p.value);
tab[index] = newFirst;
count = c; // write-volatile
}
}
return oldValue;
} finally {
unlock();
}
}
注意：具体的实现方式看注释，个人感觉比较绕，所以有兴趣的朋友可以按照如下步骤实现了一遍：（实现的过程可以参照HashMap的remove(Object key)）
- 根据key获取hash值
- 根据hash值获取Segment
- 获取将要删除的元素所在的HashEntry[index]
- 遍历链表
- 若没有hash和key都与指定参数相同的节点e，返回null
- 若有e，删除指定节点e，并将e的前一个节点的next指向e的下一个节点，之后count-1
6、containsKey(Object key)
使用方法：
map.containsKey("hello")
源代码：
ConcurrentHashMap的containsKey(Object key)
/**
* 是否包含指定key的数据
* 步骤：
* 1)根据key计算hash值
* 2)根据hash获取相应的Segment
* 调用Segment的containsKey(Object key, int hash)
* 3)根据hash值找出HashEntry数组中的索引index，并返回HashEntry[index]
* 4)遍历整个HashEntry[index]链表，找出hash和key与给定参数相等的HashEntry，例如e，
* 4.1)如找到e，返回true
* 4.2)如没找到e，返回false
*/
public boolean containsKey(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).containsKey(key, hash);
}
Segment的containsKey(Object key, int hash)
说明：代码清晰简单，流程步骤查看注释即可
7、keySet().iterator()
使用方法：
Map<String, Object> map = new ConcurrentHashMap<String, Object>();
map.put("hello3", "world2");
map.put("hello2", "world");
for(String key : map.keySet()){
System.out.println(map.get(key));
}
源代码不写了。
流程：
遍历每个Segment中的HashEntry[]，完成所有对象的读取，不加锁。
8、size()
源代码：
/**
* 计算map中的key-value对总数
* 步骤：
* 1)遍历所有段,计算总的count值sum,计算总的modCount值
* 2)如果有数据的话（modCount！=0），再遍历所有段一遍，计算总的count值check，在这期间只要有一个段的modCount发生了变化，就再重复如上动作两次
* 3)若三次后，还未成功，遍历所有Segment，分别加锁（即建立全局锁），然后计算，最后释放所有锁
*/
public int size() {
final Segment<K, V>[] segments = this.segments;
long sum = 0;//总量
long check = 0;//标志位
int[] mc = new int[segments.length];//存放每个段的modCount
for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
check = 0;
sum = 0;//总的count值
int mcsum = 0;//总的modCount值
for (int i = 0; i < segments.length; ++i) {//遍历所有段
sum += segments[i].count;//计算总的count值
mcsum += mc[i] = segments[i].modCount;//计算总的modCount值
}
if (mcsum != 0) {//有数据的话，再检查一遍
for (int i = 0; i < segments.length; ++i) {
check += segments[i].count;//计算总的count
if (mc[i] != segments[i].modCount) {//只要有一个段发生了变化（在遍历期间发生了增删变化）
check = -1;
break;//跳出所有循环
}
}
}
if (check == sum)//成功
break;
}
if (check != sum) { //以上三次都为成功的话
sum = 0;
//每一个段全部加锁（相当于加了一个全局锁）
for (int i = 0; i < segments.length; ++i)
segments[i].lock();
//进行统计
for (int i = 0; i < segments.length; ++i)
sum += segments[i].count;
//全部解锁
for (int i = 0; i < segments.length; ++i)
segments[i].unlock();
}
if (sum > Integer.MAX_VALUE)
return Integer.MAX_VALUE;
else
return (int) sum;
}
在不加锁的情况下遍历所有Segment，读取每个Segment的count和modCount，并进行统计；
完毕后，再遍历一遍所有Segment，比较modCount，是否发生了变化，若发生了变化，则再重复如上动作两次；
若三次后，还未成功，遍历所有Segment，分别加锁（即建立全局锁），然后计算，最后释放所有锁。
注：以如上的方式，大部分情况下，不需要加锁就可以获取size()
总结：
- 数据结构：一个指定个数的Segment数组，数组中的每一个元素Segment相当于一个HashTable
- 加锁情况（分段锁）：
- put
- get中找到了hash与key都与指定参数相同的HashEntry，但是value==null的情况
- remove
- size()：三次尝试后，还未成功，遍历所有Segment，分别加锁（即建立全局锁）
免费领取验证码、内容安全、短信发送、直播点播体验包及云服务器等套餐
更多网易技术、产品、运营经验分享请点击。
分享至：
