concurrenthashmap是一个非常好的map实现,在高并发操作的场景下会有非常好的效率。实现的目的主要是为了避免同步操作时对整个map对象进行锁定从而提高并发访问能力。
ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对;Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。
static final class HashEntry<K,V> { final K key; // 声明 key 为 final 型 final int hash; // 声明 hash 值为 final 型 volatile V value; // 声明 value 为 volatile 型 final HashEntry<K,V> next; // 声明 next 为 final 型 HashEntry(K key, int hash, HashEntry<K,V> next, V value) { this.key = key; this.hash = hash; this.next = next; this.value = value; } }
static final class Segment<K,V> extends ReentrantLock implements Serializable { transient volatile int count; //在本 segment 范围内,包含的 HashEntry 元素的个数 //volatile 型 transient int modCount; //table 被更新的次数 transient int threshold; //默认容量 final float loadFactor; //装载因子 /** * table 是由 HashEntry 对象组成的数组 * 如果散列时发生碰撞,碰撞的 HashEntry 对象就以链表的形式链接成一个链表 * table 数组的数组成员代表散列映射表的一个桶 */ transient volatile HashEntry<K,V>[] table; /** * 根据 key 的散列值,找到 table 中对应的那个桶(table 数组的某个数组成员) * 把散列值与 table 数组长度减 1 的值相“与”,得到散列值对应的 table 数组的下标 * 然后返回 table 数组中此下标对应的 HashEntry 元素 * 即这个段中链表的第一个元素 */ HashEntry<K,V> getFirst(int hash) { HashEntry<K,V>[] tab = table; return tab[hash & (tab.length - 1)]; } Segment(int initialCapacity, float lf) { loadFactor = lf; setTable(HashEntry.<K,V>newArray(initialCapacity)); } /** * 设置 table 引用到这个新生成的 HashEntry 数组 * 只能在持有锁或构造函数中调用本方法 */ void setTable(HashEntry<K,V>[] newTable) { threshold = (int)(newTable.length * loadFactor); table = newTable; } }
注意Segment继承了ReentrantLock 锁
get操作不需要锁。第一步是访问count变量,这是一个volatile变量,由于所有的修改操作在进行结构修改时都会在最后一步写count变量,通过这种机制保证get操作能够得到几乎最新的结构更新。对于非结构更新,也就是结点值的改变,由于HashEntry的value变量是volatile的,也能保证读取到最新的值。接下来就是对hash链进行遍历找到要获取的结点,如果没有找到,直接访回null。对hash链进行遍历不需要加锁的原因在于链指针next是final的。但是头指针却不是final的,这是通过getFirst(hash)方法返回,也就是存在table数组中的值。这使得getFirst(hash)可能返回过时的头结点,例如,当执行get方法时,刚执行完getFirst(hash)之后,另一个线程执行了删除操作并更新头结点,这就导致get方法中返回的头结点不是最新的。这是可以允许,通过对count变量的协调机制,get能读取到几乎最新的数据,虽然可能不是最新的。要得到最新的数据,只有采用完全的同步。
- V get(Object key, int hash) {
- if (count != 0) { // read-volatile
- HashEntry 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 readValueUnderLock(HashEntry e) {
- lock();
- try {
- return e.value;
- } finally {
- unlock();
- }
- }
put操作一上来就锁定了整个segment,这当然是为了并发的安全,修改数据是不能并发进行的,必须得有个判断是否超限的语句以确保容量不足时能够rehash,而比较难懂的是这句int index = hash & (tab.length - 1),原来segment里面才是真正的hashtable,即每个segment是一个传统意义上的hashtable,如上图,从两者的结构就可以看出区别,这里就是找出需要的entry在table的哪一个位置,之后得到的entry就是这个链的第一个节点,如果e!=null,说明找到了,这是就要替换节点的值(onlyIfAbsent == false),否则,我们需要new一个entry,它的后继是first,而让tab[index]指向它,什么意思呢?实际上就是将这个新entry插入到链头,剩下的就非常容易理解了。
- V put(K key, int hash, V value, boolean onlyIfAbsent) {
- lock();
- try {
- int c = count;
- if (c++ > threshold) // ensure capacity
- rehash();
- HashEntry[] tab = table;
- int index = hash & (tab.length - 1);
- HashEntry first = (HashEntry) tab[index];
- HashEntry 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(key, hash, first, value);
- count = c; // write-volatile
- }
- return oldValue;
- } finally {
- unlock();
- }
- }
remove操作非常类似put,但要注意一点区别,中间那个for循环是做什么用的呢?(*号标记)从代码来看,就是将定位之后的所有entry克隆并拼回前面去,但有必要吗?每次删除一个元素就要将那之前的元素克隆一遍?这点其实是由entry 的不变性来决定的,仔细观察entry定义,发现除了value,其他所有属性都是用final来修饰的,这意味着在第一次设置了next域之后便不能再 改变它,取而代之的是将它之前的节点全都克隆一次。至于entry为什么要设置为不变性,这跟不变性的访问不需要同步从而节省时间有关,关于不变性的更多 内容,请参阅之前的文章《线程高级---线程的一些编程技巧》
- V remove(Object key, int hash, Object value) {
- lock();
- try {
- int c = count - 1;
- HashEntry[] tab = table;
- int index = hash & (tab.length - 1);
- HashEntry first = (HashEntry)tab[index];
- HashEntry e = first;
- while (e != null && (e.hash != hash || !key.equals(e.key)))
- e = e.next;
- V oldValue = null;
- if (e != null) {
- 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 newFirst = e.next;
- * for (HashEntry p = first; p != e; p = p.next)
- * newFirst = new HashEntry(p.key, p.hash,
- newFirst, p.value);
- tab[index] = newFirst;
- count = c; // write-volatile
- }
- }
- return oldValue;
- } finally {
- unlock();
- }
- }
探索 ConcurrentHashMap 高并发性的实现机制:
http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/
ConcurrentHashMap之实现细节
http://www.iteye.com/topic/344876
Map的并发处理(ConcurrentHashMap)
http://zl198751.iteye.com/blog/907927
集合框架 Map篇(4)----ConcurrentHashMap
http://hi.baidu.com/yao1111yao/blog/item/232f2dfc55fbcd5ad7887d9f.html
java ConcurrentHashMap中的一点点迷惑
http://icanfly.iteye.com/blog/1450165
相关推荐
主要介绍了java ConcurrentHashMap锁分段技术详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小,允许多个修改操作并发进行,其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的...
NULL 博文链接:https://107192468a.iteye.com/blog/2296911
java源码剖析-ConcurrentHashMap
ConcurrentHashMap源码剖析
源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556
Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~
ConcurrentHashMap具体是怎么实现线程安全的呢,肯定不可能是每个方法加synchronized,那样就变成了HashTable。
本文将结合Java内存模型,分析JDK源代码,探索ConcurrentHashMap高并发的具体实现机制,包括其在JDK中的定义和结构、并发存取、重哈希和跨段操作,并着重剖析了ConcurrentHashMap读操作不需要加锁和分段锁机制的内在...
解析concurrenthashmap的源码,学习多线程的思想
这时候ConcurrentHashMap达到容量扩容而忽略了ReservationNode情况,调用put的时候在synchronized(f)没有对ReservationNode处理,所以会出现死循环。 在jdk1.8和1.9中对比 http://gee.cs.oswego.edu/cgi- bin/...
程序员面试加薪必备_ConcurrentHashMap底层原理与源码分析深入详解
java本地缓存ConcurrentHashMap
ConcurrentHashMap使用了分段锁(Segment)来实现并发的读写操作,每个Segment都相当于一个小的HashMap,将整个哈希表分成多个部分。这样可以同时进行多个线程的并发读写操作,不会阻塞其他线程的访问。 需要注意的...
ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小,不用对整个ConcurrentHashMap加锁。ConcurrentHashMap为了提高本身的并发能力,在内部采用了...
ConcurrentHashMap之实现细节
concurrenthashmap1.7的源码分析
Java——并发容器之ConcurrentHashMap;Java——并发容器之ConcurrentHashMap;Java——并发容器之ConcurrentHashMap;Java——并发容器之ConcurrentHashMap;Java——并发容器之ConcurrentHashMap;Java——并发...
java7-8中的 HashMap和ConcurrentHashMap全解析
ConcurrentHashMap的实现原理(纯干货)