注释对于ConcurrentHashMap的源码实现,JDK1.8与之前的版本有很大的不同,下文针对的是JDK1.8的源码剖析。
注释是代码作者最想留给读者的话,我们真的应该好好读一读。
- 从线程安全的角度来讲,ConcurrentHashMap与Hashtable是可以互用的,但是从同步机制上二者是有一些区别的。
- ConcurrentHashMap并不对并发读取 *** 作上锁,读写 *** 作有可能会同时进行。一些方法诸如size/isEmpty/containsValue反映的是某一个临时状态,因此如果有另外的线程在并发写的时候是不太适合使用的。
- 无论如何,hashmap的扩容 *** 作都是一个相对比较耗时的 *** 作,如果有可能的话,尽量先根据实际情况估计一个大小,然后作为构造函数的参数传入,尽量减少扩容次数。
- 该类实现了Map和Iterator接口的所有方法
- 不允许空值作为key或value,这点和hashtable类似,但是和hashmap不同
- MAXIMUM_CAPACITY:hash表的最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
- DEFAULT_CAPACITY:hash表默认初始化大小,一般为2的整数倍
private static final int DEFAULT_CAPACITY = 16;
- DEFAULT_CONCURRENCY_LEVEL:默认并发级别,JDK1.8中已经不再使用了,只是为了兼容旧的版本。
- LOAD_FACTOR:扩容因子,触发扩容 *** 作的关键阈值。
private static final float LOAD_FACTOR = 0.75f;
- TREEIFY_THRESHOLD:某一个哈希值的节点数目超过此值时由链表存储转为红黑树。
static final int TREEIFY_THRESHOLD = 8;
- UNTREEIFY_THRESHOLD:某一个哈希值的节点数目低于此值时由红黑树存储转为链表。
static final int MIN_TREEIFY_CAPACITY = 64;
- MAX_RESIZERS:扩容 *** 作允许的最大线程数,受RESIZE_STAMP_BITS的制约。
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
- sizeCtl:控制哈希表初始化和扩容。负数表示正在进行初始化或扩容,-1是正在初始化,-N表示(N-1)个线程正在执行扩容。否则,如果尚未进行初始化,那这个正数表示需要初始化的大小,初始化执行之后,该值保存的是下次扩容的大小。
private transient volatile int sizeCtl;内部类 TreeBin
TreeBin本身不包含key和value值,而是指向TreeNodes的根节点。它用来维护读写锁的状态,强迫写线程在树的重构 *** 作完成前等待读线程结束。
TreeNodeTreeBin里面使用的真正的红黑树节点。
主要方法 构造函数- 无参,默认初试大小为16
public ConcurrentHashMap() { }
- 指定初始大小,如果可以预计元素数量的话,建议使用这种方式初始化,可以避免动态扩容带来的损耗。
public ConcurrentHashMap(int initialCapacity) { this(initialCapacity, LOAD_FACTOR, 1); }
- 指定初始大小和扩容因子
public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); }
- 指定扩容因子、初始大小和并发度,上面的构造函数都会调用此函数
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }
initialCapacity其实相当于是初始的元素个数,真正的初始容量大小是由loadFactor,再结合tableSizeFor方法计算得到的,关于tableSizeFor方法的详解可参考前文:啊哈瞬间之tableSizeFor。
initTable初始化哈希表的方法,见下面的注解部分
private final Nodeput方法[] initTable() { Node [] tab; int sc; while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) //如果为负数,则表示有操作在进行中,自旋等待 Thread.yield(); // lost initialization race; just spin else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { //获得操作权限后进行原子操作,将SIZECTL值置为-1,表示正在进行操作 try { if ((tab = table) == null || tab.length == 0) { //二次检查哈希表是否需要初始化 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //如果sc大于0,则使用sc的值作为哈希表的大小,否则使用默认值 @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node,?>[n]; table = tab = nt; sc = n - (n >>> 2); //修改sc的值,如果n为16,则sc = 16-16/4 = 12 } } finally { sizeCtl = sc; //修改sizeCtl的值,初始化结束,让出控制权 } break; } } return tab; }
流程图如下:
关键点说明
- 首先通过spread函数计算哈希值,该函数通过将高16位与低16位进行异或 *** 作,在table大小较小的情况下,让高位也参与运算,能够让得到的哈希值分布的更均匀,尽可能的避免哈希碰撞。
int hash = spread(key.hashCode());
- 如果hash表为空,则执行初始化方法。采用了“懒加载”的方式,即哈希表的初始化并不是在构造阶段完成的,而是在首次插入数据的时候进行的。详细过程见上面的initTable方法介绍。
- onlyIfAbsent变量表示是否需要覆盖之前的值,当为false时会覆盖掉之前的值
- 与hashMap的区别之处在于发生hash碰撞对Node进行处理时会对Node上锁,这也是ConcurrentHashmap线程安全的原因
- 并不是说只要链表长度超过TREEIFY_THRESHOLD(默认为8)一定会进行变形为树结构,还需结合当前hashtable的size,如果size
get方法比较简单,基本上就是根据哈希值查找map中是否存在该元素,对于存在哈希碰撞的元素,则在对应的链表或者红黑树中进行查找。
tryPresize方法该方法负责table的扩容 *** 作,扩容 *** 作的核心是transfer方法,此方法逻辑比较复杂,后面有时间单独进行说明。
private final void tryPresize(int size) { //确定待扩容的空间大小,确保不能超过MAXIMUM_CAPACITY的前提下,是大于1.5*size+1的整数次幂 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; while ((sc = sizeCtl) >= 0) { Node[] tab = table; int n; //初始化表的情况 if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node,?>[n]; table = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } } } else if (c <= sc || n >= MAXIMUM_CAPACITY) break; // tab == table说明还没开始迁移节点 else if (tab == table) { int rs = resizeStamp(n); //开始迁移原tab[] 中的数据,将sizeCtl设置为一个很大的负值 if (U.compareAndSetInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) //具体的迁移方法,设计多线程迁移的逻辑 transfer(tab, null); } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)