首页 > 编程语言 >【Java】concurrentHashMap

【Java】concurrentHashMap

时间:2022-11-11 12:04:57浏览次数:49  
标签:concurrentHashMap hash int segments return key Java sum


concurrentHashMap类引入了段的概念,读操作不需要上锁,写操作只需要获取相应的段的锁即可,而非锁定全部的数据。所以map里面是一个segment的数组,segment里面才是entry的数组。map的操作最终会定位到每一个具体的段,进行get和put操作。

private static int hash(int h) {
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}

/**
* Returns the segment that should be used for key with given hash
* @param hash the hash code for the key
* @return the segment
*/
final Segment<K,V> segmentFor(int hash) {
return segments[(hash >>> segmentShift) & segmentMask];
}

也是从key的hashCode值计算得到hash值,然后从hash值利用移位和掩码得到segment的索引,委托给segment进行操作。

transient volatile int count;

/**
* Number of updates that alter the size of the table. This is
* used during bulk-read methods to make sure they see a
* consistent snapshot: If modCounts change during a traversal
* of segments computing size or checking containsValue, then
* we might have an inconsistent view of state so (usually)
* must retry.
*/
transient int modCount;

/**
* The table is rehashed when its size exceeds this threshold.
* (The value of this field is always <tt>(int)(capacity *
* loadFactor)</tt>.)
*/
transient int threshold;

/**
* The per-segment table.
*/
transient volatile HashEntry<K,V>[] table;

/**
* The load factor for the hash table. Even though this value
* is same for all segments, it is replicated to avoid needing
* links to outer object.
* @serial
*/
final float loadFactor;


V get(Object key, int hash) {
if (count != 0) { // read-volatile
HashEntry<K,V> e = getFirst(hash);
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)
return v;
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
return null;
}


V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock();
try {
int c = count;
if (c++ > threshold) // ensure capacity
rehash();
HashEntry<K,V>[] tab = table;
int index = hash & (tab.length - 1);
HashEntry<K,V> first = tab[index];
HashEntry<K,V> e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;

V oldValue;
if (e != null) {
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value;
}
else {
oldValue = null;
++modCount;
tab[index] = new HashEntry<K,V>(key, hash, first, value);
count = c; // write-volatile
}
return oldValue;
} finally {
unlock();
}
}


所以,对mao中单个entry的操作实际上是定位到具体的段,然后委托给段处理的,每一段的内部可以决定是否上锁,锁粒度很小。具体的处理逻辑和hashmap差不多。

但是对于整个map的操作则需要所有段协同,比如size。但是这里也不是锁住整个map进行的。

public int size() {
final Segment<K,V>[] segments = this.segments;
long sum = 0;
long check = 0;
int[] mc = new int[segments.length];
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
check = 0;
sum = 0;
int mcsum = 0;
for (int i = 0; i < segments.length; ++i) {
sum += segments[i].count;
mcsum += mc[i] = segments[i].modCount;
}
if (mcsum != 0) {
for (int i = 0; i < segments.length; ++i) {
check += segments[i].count;
if (mc[i] != segments[i].modCount) {
check = -1; // force retry
break;
}
}
}
if (check == sum)
break;
}
if (check != sum) { // Resort to locking all segments
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;
}


size的思路是先不锁,计算每一个段的大小,累加,然后也存一下每一个段的modcount,然后再计算一次sum,同时比较每一个段的modcount和第一次是否相同,如果不同,说明这个段在两次计算之间发生了改变,需要重新进行这个过程。这就是for循环内部的过程。这个双重检验的过程会进行最多2次,由RETRIES_BEFORE_LOCK标示。然后退出这个循环。再检测一次sum和check是否相等,到这里可能是因为想等退出的也可能是重试次数用完到达的,所以要检测。若想等返回,否则说明一直有修改,需要上锁再计算,这就是整个size的操作。



标签:concurrentHashMap,hash,int,segments,return,key,Java,sum
From: https://blog.51cto.com/u_15873544/5844105

相关文章

  • 【Java】Map 实现类
    hashmap:遍历时顺序无法保证linkedhashmap:遍历时按照插入顺序treemap:遍历时按照大小顺序linkedhashmap实现上是继承了hashmap,多了一个双向的链表记录插入顺序,重写了迭代器,基......
  • 【Java】 Set实现类
    Set是collection的子接口,对应数学中的集合。与list的最主要的区别是,set无法通过索引取值,因为set是无序的。set还有一个特性是唯一性,不能存相同的元素。第一个实现类是hashse......
  • 【Java】垃圾回收机制 GC
    GC是java中比较有特色的技术,减轻了程序员的负担。当然也是面试中的高频话题。对于垃圾回收,首先要解决的是找出哪些对象是需要回收的。第一个方法是计算引用数目,实现比较简单......
  • springboot 引入外部包的坑Lookup method resolution failed; nested exception is ja
    手动引入jar包<dependency><groupId>com.allinpay.sdk</groupId><artifactId>top-sdk-java</artifactId><version>1.0.5</......
  • java
    Java是一种编程语言和计算平台,由SunMicrosystems在1995年首次发布。它从微末起步,逐渐发展为当今数字世界中很大一部分资产所依赖的基础,是用于构建许多服务和应用程序......
  • Java之找不到或无法加载主类
    IDEA报错:错误:找不到或无法加载主类。解决方法1:原因:未能成功编译。尝试:菜单栏Build->RebuildProdject 解决方法2:原因:IDEA缓存问题。尝试:菜单栏File->Invalida......
  • Java--comparator接口与Comparable接口的区别
    1.Comparator和Comparable相同的地方他们都是java的一个接口,并且是用来对自定义的class比较大小的,什么是自定义class:如publicclassPerson{Stringname;int......
  • Java实现算法之--选择排序
        选择排序也是比较简单的一种排序方法,原理也比较容易理解,它与冒泡排序的比较次数相同,但选择排序的交换次数少于冒泡排序。冒泡排序是在每次比较之后,若比较的两个......
  • 20个高级Java面试题汇总
    什么是可变参数?断言的用途?什么时候使用断言?什么是垃圾回收?用一个例子解释垃圾回收?什么时候运行垃圾回收?垃圾回收的最佳做法?什么是初始化数据块?什么是静态初始化器?什么是实例......
  • Java集合Map接口与Map.Entry学习
    Map接口不是Collection接口的继承。Map接口用于维护键/值对(key/valuepairs)。该接口描述了从不重复的键到值的映射。(1)添加、删除操作:Objectput(Objectkey......