Java8之后的ConcurrentHashMap, 舍弃分段锁
JDK 源码中 HashMap 的 hash 方法原理是什么？
ConcurrentHashMap 源码解读
unsafe
unsafe arrayIndexScale
tableSizeFor方法 先来分析有关n位操作部分：先来假设n的二进制为01xxx...xxx。接着
对n右移1位：001xx...xxx，再位或：011xx...xxx
对n右移2为：00011...xxx，再位或：01111...xxx
此时前面已经有四个1了，再右移4位且位或可得8个1
同理，有8个1，右移8位肯定会让后八位也为1。
综上可得，该算法让最高位的1后面的位全变为1。
最后再让结果n+1，即得到了2的整数次幂的值了。
0100 0000 0000 0000 0000 0000 0000 0000
向右移动1位
0010 ...
进行|运算，得到结果
0110 ...
向右移动2位
0001 1000 ...
进行|运算，得到结果
0111 1000 ...
向右移动4位
0000 0111 1000 ...
进行|运算，得到结果
0111 1111 1000 ...
向右移动8位
0000 0000 0111 1111 1000 ...
进行|运算，得到结果
0111 1111 1111 1111 1000 ...
向右移动16位
0000 0000 0000 0000 0111 1111 1111 1111
【j.u.c|j.u.c ConcurrentHashMap tableSizeFor方法】进行|运算，得到结果
0111 1111 1111 1111 1111 1111 1111 1111
最终结果
0111 1111 1111 1111 1111 1111 1111 1111

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

如果n=9
0000 0000 0000 0000 0000 0000 0000 1000
向右移动1位
0000 0000 0000 0000 0000 0000 0000 0100
进行|运算，得到结果
0000 0000 0000 0000 0000 0000 0000 1100
向右移动2位
0000 0000 0000 0000 0000 0000 0000 0011
进行|运算，得到结果
0000 0000 0000 0000 0000 0000 0000 1111
向右移动4位
0000 0000 0000 0000 0000 0000 0000 0000
进行|运算，得到结果
0000 0000 0000 0000 0000 0000 0000 1111
向右移动8位
0000 0000 0000 0000 0000 0000 0000 0000
进行|运算，得到结果
0000 0000 0000 0000 0000 0000 0000 1111
向右移动16位
0000 0000 0000 0000 0000 0000 0000 0000
进行|运算，得到结果
0000 0000 0000 0000 0000 0000 0000 1111
最高位下的所有位都替换成1，
最后n+1
最高位的上一位替换成1， 低位都是0
最终得到2幂次方，且最接近n的值
为了兼容最大的
01xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
所以累积最大移动31位
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
hash spread hash&(length-1) 决定元素在数组中的位置。
HASH_BITS
01111111 11111111 11111111 11111111

static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS; }

h^(h>>>16) 低16位和高16位异或运算， 不用管h的高16位。
“扰动函数”： 低16位和高16位异或运算，，以此来加大低16位的随机性；混合后的低位参杂了高位16位的特征， 这样高位信息也被变相保留下来。
putVal方法
文章图片
putVal执行流程.png

/** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value =https://www.it610.com/article/= null) throw new NullPointerException(); // 求hash值 int hash = spread(key.hashCode()); int binCount = 0; for (Node[] tab = table; ; ) {Node f; int n, i, fh; if (tab == null || (n = tab.length) == 0)// 初始化数组 tab = initTable(); // 如果数组是空的 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 数组中的i位置添加第一个元素 if (casTabAt(tab, i, null, new Node(hash, key, value, null))) break; // no lock when adding to empty bin }// 数组在扩容？else if ((fh = f.hash) == MOVED)// 帮助数组扩容tab = helpTransfer(tab, f); else { V oldVal = null; // 第一个节点，作为锁synchronized (f) {// 双重检测 if (tabAt(tab, i) == f) {if (fh >= 0) { // 链表 binCount = 1; for (Node e = f; ; ++binCount) { // 遍历链表。K ek; // 如果新key和老key 相同， 则用新值替换旧值if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; // absent缺失的，只有当onlyIfAbsent=false才能用新值来替换旧值， 否则不允许覆盖。if (!onlyIfAbsent) e.val = value; break; }// 如果没有重复的，则把新节点添加的链表的结尾 Node pred = e; if ((e = e.next) == null) { pred.next = new Node(hash, key, value, null); break; } } } // 6.当前为红黑树，将新的键值对插入到红黑树中else if (f instanceof TreeBin) { Node p; binCount = 2; // 调用putTreeVal方法，插入新值 if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) { // key已经存在，则替换。 oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } }// 7.插入完键值对后再根据实际大小看是否需要转换成红黑树 // 链表长度最大是8if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD)// 插入新节点后，达到链表转换红黑树阈值，则执行转换操作 // 此函数内部会判断是树化，还是扩容：tryPresize// 数组长度要至少64， 才会触发树化， 否则扩容。treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }

treeifyBin(tab, i); 将链表转换成红黑树。将判断是否树化还是扩容。树化、链化

/* ---------------- Conversion from/to TreeBins -------------- *//** * Replaces all linked nodes in bin at given index unless table is * too small, in which case resizes instead. */ private final void treeifyBin(Node[] tab, int index) { Node b; int n, sc; if (tab != null) { if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode hd = null, tl = null; for (Node e = b; e != null; e = e.next) { TreeNode p = new TreeNode(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } setTabAt(tab, index, new TreeBin(hd)); } } } } }/** * Returns a list on non-TreeNodes replacing those in given list. 尝试预先调整表的大小以容纳给定数量的元素。 */ static Node untreeify(Node b) { Node hd = null, tl = null; for (Node q = b; q != null; q = q.next) { Node p = new Node(q.hash, q.key, q.val, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; }

数组扩容； 暂时不看

/** * Tries to presize table to accommodate the given number of elements. * * @param size number of elements (doesn't need to be perfectly accurate) */ // 数组扩大一倍 private final void tryPresize(int size) { int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); // 数组长度16扩容到32 ； 数组长度 32扩容到64int sc; while ((sc = sizeCtl) >= 0) { Node[] tab = table; int n; if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; if (U.compareAndSwapInt(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; else if (tab == table) { int rs = resizeStamp(n); if (sc < 0) { Node[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); } } }

static final int MIN_TREEIFY_CAPACITY = 64; 数组长度至少64， 才会触发 链表转换成红黑树
sizeCtl的作用 // 默认是0 或者在构造方法中和cap大小相同；
private transient volatile int sizeCtl;
j.u.c ConcurrentHashMap addCount方法
1、当总节点数量超过sizeCtl则对数组执行扩容操作； 将数组长度扩大为原来的2倍；
2、记录当前总节点的数量；
当添加、修改 元素都会触发判断数组是否需要扩容的操作：
sizeCtl作为判断是否对数组进行2倍扩容的依据；
sizeCtl= loaderFactor*当前数组长度；
一般loaderFactor=3/4.
sizeCtl 在初始化数组或者做数组扩容的时候，用来乐观锁标记的；初始化数组结束之后、或者扩容结束之后， sizeCtl=0.75*数组长度； 当总节点数量大于sizeCtl,则触发对数组的扩容操作。
初始化数组 yeild方法
unsafe.compareAndSwapInt(当前对象， Unsafe.SIZECTL就是对sizeCtl字段的偏移量， 期待值， 新值替换sizeCtl中的旧值)
// Unsafe.SIZECTL就是对sizeCtl字段的偏移量
SIZECTL = U.objectFieldOffset(k.getDeclaredField("sizeCtl"));

/** * Initializes table, using the size recorded in sizeCtl. */ private final Node[] initTable() { Node[] tab; int sc; while ((tab = table) == null || tab.length == 0) {//第一层判断， 数组是空的if ((sc = sizeCtl) < 0) //第二层判断， 其他线程在操作数组Thread.yield(); // lost initialization race; just spin； 放弃竞争， 等待其他线程完成。// 否则， 加锁， 让其他线程放弃竞争。 //unsafe.compareAndSwapInt(当前对象，Unsafe.SIZECTL就是对sizeCtl字段的偏移量， 期待值， 新值替换sizeCtl中的旧值)这是个原子操作 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try {// 第三层判断， 数组是空的。 这是为了数组都初始化完成了， 锁也放开了，又被其他线程初始化了一遍。或者根本就没有竞争， 直接初始化数组了。if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // 创建数组 @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node[n]; table = tab = nt; //第四步中0.75为四分之三，这里n - (n >>> 2)是不是刚好是n-(1/4)n=(3/4)n，sc = n - (n >>> 2); } } finally { // 5、 作用是为了让其他的线程跳出while循环 sizeCtl = sc; } break; } } return tab; }

乐观锁代码部分

// Unsafe mechanics private static final sun.misc.Unsafe U; // 乐观锁， 通过这个控制数组这个共享变量的读写在多线程环境中的一致性。private static final long SIZECTL; private static final long TRANSFERINDEX; private static final long BASECOUNT; private static final long CELLSBUSY; private static final long CELLVALUE; private static final long ABASE; private static final int ASHIFT; static { try { U = sun.misc.Unsafe.getUnsafe(); Class k = ConcurrentHashMap.class; SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class ck = CounterCell.class; CELLVALUE = https://www.it610.com/article/U.objectFieldOffset (ck.getDeclaredField("value")); Class ak = Node[].class; ABASE = U.arrayBaseOffset(ak); int scale = U.arrayIndexScale(ak); if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); } }

tableAt方法

// 这边为什么i要等于((long)i << ASHIFT) + ABASE呢,计算偏移量 static final Node tabAt(Node[] tab, int i) { // Key对应的数组元素的可见性，由Unsafe的getObjectVolatile方法保证。//((long)i << ASHIFT) + ABASE就算i最后的地址 return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); }

*这边为什么i要等于((long)i << ASHIFT) + ABASE呢,计算偏移量
*ASHIFT是指tab[i]中第i个元素在相对于数组第一个元素的偏移量，而ABASE就算第一数组的内存素的偏移地址
*所以呢，((long)i << ASHIFT) + ABASE就算i最后的地址
Unsafe对数组操控
这部分主要介绍与数据操作相关的arrayBaseOffset与arrayIndexScale这两个方法，两者配合起来使用，即可定位数组中每个元素在内存中的位置。
//返回数组中第一个元素的偏移地址
public native int arrayBaseOffset(Class arrayClass);
//返回数组中一个元素占用的大小
public native int arrayIndexScale(Class arrayClass);
为什么数组长度都是2的幂次方呢？ *但是这边为什么i要等于((long)i << ASHIFT) + ABASE呢,计算偏移量
*((long)i << ASHIFT)是指tab[i]中第i个元素在相对于数组第一个元素的偏移量，而ABASE就算第一数组的内存素的偏移地址
*所以呢，((long)i << ASHIFT) + ABASE就算i最后的地址

Class ak = Node[].class; ABASE = U.arrayBaseOffset(ak); int scale = U.arrayIndexScale(ak); // 到底表示什么暂时无解

// 下面这段代码暂时无解， 不能理解
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
有些问题暂时是无解的， 先搞定能搞定的 节点类型 ForwardingNode 链表第一个
ReservationNode 保留节点
A place-holder node used in computeIfAbsent and compute
Node 普通节点
helpTransfer 数组扩容代码， 在看扩容代码之前， 先看链表/红黑树插入新节点。

/** * Helps transfer if a resize is in progress. */ final Node[] helpTransfer(Node[] tab, Node f) { Node[] nextTab; int sc; if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode)f).nextTable) != null) { int rs = resizeStamp(tab.length); while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { transfer(tab, nextTab); break; } } return nextTab; } return table; }

负载因子 // load_factor table的负载因子，当前节点数量超过 n * LOAD_FACTOR，执行扩容
// 位操作表达式为 n - (n >>> 2), n是节点数量
private static final float LOAD_FACTOR = 0.75f
putALL

public void putAll(Map m) { tryPresize(m.size()); for (Map.Entry e : m.entrySet()) putVal(e.getKey(), e.getValue(), false); }

数组扩容源码分析

// size参数 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); // 扩容2倍 private final void tryPresize(int size) {// 计算扩容后的数组长度 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; while ((sc = sizeCtl) >= 0) { // sizeCtl 当前数组长度的0.75Node[] tab = table; // 旧的数组int n; if (tab == null || (n = tab.length) == 0) { // 如果旧的数组为空或者长度为0，则执行初始化操作，初始化操作和initTable方法初始化数组的代码一样。n = (sc > c) ? sc : c; if (U.compareAndSwapInt(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) // 如果扩容后的数组长度不大于sizeCtl（当前数组的0.75， 或者当前的数组长度已经达到了最大限制，则不再扩容。break; else if (tab == table) {// 旧的数组没变int rs = resizeStamp(n); if (sc < 0) { Node[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); } } }

邮戳

static final int resizeStamp(int n) {//Must be at least 6 for 32bit arrays. private static int RESIZE_STAMP_BITS = 16; // 求出n的二进制，32位， 第一个位是1的， 之前有多少个0 // 位或， 用来记录n的二进制前面位是0的总数。 return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); }

数组单元 红黑树结构退化成 链表结构

static final int UNTREEIFY_THRESHOLD = 6;

当红黑树节点数<=6则退化成链表。

/** * Returns a list on non-TreeNodes replacing those in given list. */ // 这个方法用来将红黑树退化成链表static Node untreeify(Node b) { Node hd = null, tl = null; for (Node q = b; q != null; q = q.next) { Node p = new Node(q.hash, q.key, q.val, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; }

推荐阅读

• 

  redmi|vivo/OPPO/荣耀成为球最受欢迎手机品牌；王一博惊叹小米新技术
• 

  安逸的日子
• 

  十一月祝福语 一月祝福语大全
• 

  马桶冲不下去水往上涨是什么原因
• 

  安卓6.0软件闪退,6.0版收不到话音提醒请关闭电脑
• 

  mysql中的排序 mysql删除时排序
• 

  牛年雷姓与啥名打分高 雷总名字打分97分
• 

  广州房租费一个月多少钱 – 广州公租房租金价目表
• 

  2019-01-14|2019-01-14 感谢我的学生让我成长
• 

  工作了还能考全日制研究生吗 参加工作了还能考全日制研究生吗
• 

  意大利斯密静雅壁挂炉怎么解决？
• 

  梦到去厕所很脏 专家帮你分析你的梦境
• 

  caj文件怎么打开
• 

  诺贝尔奖的地位
• 

  向阳花班記事—心若向阳花自开
• 

  怀孕想吐怎么办吃什么好 怀孕初期反胃怎么办
• 

  Vue指令02——v-on指令和v-show的使用
• 

  【思维导图实战派】百图绘制计划MMT128/100初春胃肠炎
• 

  苹果自带编程软件叫什么来着，itouchiphone里的软件是用什么编程语言
• 

  蟑螂爬过的床还能睡吗

• HashMap&ConcurrentHashMap&HashTable
• Java8|Java8 中的 HashMap 和 ConcurrentHashMap 全解析
• ConcurrentHashMap的实现原理(JDK1.7和JDK1.8)
• 面试突击19（为什么ConcurrentHashMap不允许插入null值（））
• firewalld与iptables防火墙工具详细介绍
• IPTABLES的连接跟踪与NAT分析
• HashMap|HashMap,HashTabel,ConcurrentHashMap
• docker容器|docker 启动container的时候出现iptables failed
• stanford|stanford cs143 Compilers 7.4 LL(1) Parsing Tables
• Linux|关于iptables