一、存储结构
HashMap和ConcurrentHashMap的存储结构是一样滴
数组+链表+红黑树
二、HashMap扩容
扩容就是将老数组的数据迁移到新数组中。
老数组索引为1的数据，可能会放到新数组索引为1或者为17的位置
// HashMap扩容
final Node<K,V>[] resize() {
// 省略部分代码，这部分代码是计算新数组长度和新阈值的。
// 扩容时，新数组长度是老数组长度的2倍
// 声明新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 给成员变量赋值~~
table = newTab;
// 保证我是扩容操作！
if (oldTab != null) {
// 遍历老数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 获取第一次循环的值
// 如果数据为空，不需要搬运这个数据到新数组
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 说明当前桶位置下没有链表
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else {
// 桶下有链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 声明当前节点的next
next = e.next;
if ((e.hash & oldCap) == 0) {
// 如果当前数据与老数组长度&运算的结果为0，lo里面
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 否则放到hi里面
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将lo链表扔到新数组的原位置，（老数组的位置）
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将hi链表扔到新数组的原位置 + 老数组长度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
三、ConcurrentHashMap线程安全的方式
CAS + synchronized
CAS：轻量级锁 （compare and swap）
synchronized：重量级锁
四、扩容触发条件
- 链表长度达到8，但是数组长度没达到64，扩容
- 数组上的数据，已经存放到了75%，达到了阈值，扩容
- 调用putAll方法，查询的Map比原数组长，直接扩容
五、扩容戳
ConcurrentHashMap，为了保证扩容时线程安全，并且保证多线程可以协助扩容。
为每一次扩容生成了一个扩容戳。
// 准备扩容
// sizeCtl是ConcurrentHashMap中的一个标识
// sizeCtl = -1：代表Map正在初始化
// sizeCtl < -1：代表Map正在扩容！
// sizeCtl = 0：代表还没有初始化！
// sizeCtl > 0：如果已经初始化了，数值代表扩容阈值。 如果没有初始化，代表初始化的数组长度
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
private transient volatile int sizeCtl;
// ------------------------------------------------
private final void tryPresize(int size) {
// 声明sc，将sizeCtl赋值进来
int sc;
// sc >= 0,现在没扩容
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
else if (tab == table) {
// 生成扩容戳~就是一个数字
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
// Doug Lea的BUG~
if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||
sc == rs + 1 || // 问题代码
sc == rs + MAX_RESIZERS || // 问题代码
// https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427
(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);
}
}
}
// 生成扩容戳,比如n是32
static final int resizeStamp(int n) {
// 获取n这个变量在二级制标识时，前面为0的个数
// 26 |
return Integer.numberOfLeadingZeros(n) | (1 << 15);
}
00000000 00000000 00000000 00011010 =26
|
00000000 00000000 10000000 00000000 =1 << 15
=
00000000 00000000 10000000 00011010 =扩容戳（半成品）rs
将sizeCtl替换为下述值
(rs << RESIZE_STAMP_SHIFT) + 2
00000000 00000000 10000000 00011010 =扩容戳（半成品）rs
10000000 00011010 00000000 00000010 =扩容戳（完全体），低位表示正在扩容的线程个数 - 1
高位16位是扩容的唯一标识
低位16位表示扩容的线程个数
扩容戳基于老数组长度生成的，记录了指定长度的唯一标识，以及一起扩容的线程有多少个。
六、扩容源码分析
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
// 计算扩容的间隔
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
// 如果基于长度和CPU内核运算，得到的结果比16大， 那么每次迁移数据的长度就用计算的
// 否则每次最少迁移16位
// 如果 nextTab == null，代表我是第一个进来扩容的线程
// 初始化新数组
if (nextTab == null) {
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
nextTable = nextTab;
transferIndex = n;
}
// 获取新数组长度
int nextn = nextTab.length;
// ForwardingNode在桶迁移完数据后，放置的节点，代表当前位置已经迁移完毕
// fwd的hash值为-1，代表当前桶迁移数据完毕
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// advance，代表当前线程还有活干么？
boolean advance = true;
// finishing，代表扩容完事了么？
boolean finishing = false;
// 死循环，i代表桶上限值，bound代表下限值
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
// // 暂时不看。
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 开始搬运数据
if (i < 0) {
// 数据搬完了！！！
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
// 获取i位置数据，如果为null，设置设置为fwd
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 如果当前位置的hash值为MOVED，说明是fwd节点，搬完了！
else if ((fh = f.hash) == MOVED)
advance = true;
else {
// 有数据，加锁！
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// 代表不是树，
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Comments NOTHING