HashMap
HashMap put()方法逻辑
- 懒加载 当put时判断如果没有初始化entry数组则开始初始化执行resize操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;- 如果当前位置没有元素，则初始化放置node并返回
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);- 如果当前位置有元素，按照情况分别执行更新、树化和后插法操作
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}HashMap resize() 扩容方法逻辑
- 调用时机
- 懒加载初始化时
- put操作后发现节点数量大于扩容阈值时
- 业务逻辑
- 计算最新的capacity和扩容阈值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}- 申请2*olcCapacity的内存区间
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];- 将已有所有元素进行搬移：
- 列表位置是单节点时，将新区间位置直接赋值。（节点是不会有hash导致的位置冲突的，考虑下）
- 由于新扩容是原始容量的两倍，因此通过节点hash值与oldCap做与，当为0时，代表仍在oldCap区间，因此在对应位置尾插法搬移节点，为1时，在oldCap 编号的位置尾插法插入节点；
- 位置是红黑树时，按照同样逻辑判断节点归属并执行尾插法放置对象。相比链表，多一个判断新位置的树的节点数量，决定执行treeify或者untreeify的操作
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 if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j oldCap] = hiHead;
}
}
}
}
}HashMap TreeNode()结构
- TreeNode的继承关系 : TreeNode<K,V> -> LinkedHashMap.Entry<K,V> -> HashMap.Node<K,V> -> Map.Entry<K,V>
- TreeNode属性和方法
- 属性next: 继承于Map.Entry， 使得TreeNode可以通过链表的方式进行关联
- 方法putTreeVal：新增树化节点对象
- 方法treeify将槽位元素树化
- 方法untreeify将槽位元素反树化
LinkedHashMap
主要数据结构：
- Node节点维持了before和after指针，分别指向前后Entry节点；
- Map维护了head, tail变量，记录队首和队尾Entry节点
维持LinkedHashMap节点状态属性的操作：
- removeNode: 维持节点链表顺序：
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}- 新增节点：如果链表head为null，则维护head值，否则将新节点尾插到列表，维持map Entry的插入顺序：
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}- 更新/查询节点：将新节点移到列表末尾
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
modCount;
}
}ConcurrentHashMap
初始化操作
- while循环等待， 通过SIZECTL作为CAS的锁；
- 由于set值为负，只有一个线程能拿到CAS锁并完成初始化，其它线程会由于table已经初始化而跳过init步骤
- 如果值为-1，则说明其它线程已经CAS成功，则让出时间片
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
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<K,V>[] nt = (Node<K,V>[])new Node<?,?>n;
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}注：上述原理用到了Unsafe类的知识，这篇文章有总结：https://cloud.tencent.com/developer/article/1951649
扩容操作（transfer）
- 对于新扩容的操作，初始化nextTab，申请内存空间。对新申请的内存空间
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);- 多线程协同扩容。在当获取到桶的Entry的Hash值为-1（一种特殊的节点，标识该节点正在进行扩容操作）时，通过无锁CAS操作协同扩容。要点有以下几方面：
- 扩容任务如何划分？
- advance标志位
- ForwardingNode标志桶已扩容
- 通过变量i标识当前处理桶的编号；
- 在最后扩容线程退出时，校验是否所有的桶都已扩容
- 扩容任务的划分： ConcurrentHashMap使用了分桶的范围迁移的方法，通过CAS操作当前的transferIndex完成线程间扩容任务的协调：
首先是任务步长的计算逻辑：
代码语言：java复制 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; //核心分工代码如下。每次将当前的tranferIndex取出，并通过CAS确定本次扩容的桶范围；有多线程协同扩容时，可以分别处理不同桶范围的对象，单线程扩容时也可以分步进行扩容工作
代码语言：java复制else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}- advance标志位处理：标识是否应该走到下一个桶，在后续处理过程中维护该bool值，如果设置为true，代表当前桶处理完毕，否则可能是CAS操作没有成功，继续当前桶的逻辑处理；
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;
}
}后续对advance标志位的维护：
- 当前桶为null时，将ForwardingNode CAS到对应桶的节点，如果成功，则advance设为true，继续下一个桶处理，否则下一次再尝试CAS修改状态
- 当前桶的hash为MOVED，即被forwardingNode标记，则设为true，跳过该节点处理；
- 对于桶不为null且hash不为MOVED时，则需要将桶的元素进行搬移，这里用到了synchronize锁锁住头节点并搬移节点。搬移操作同HashMap操作，对高位进行判断确定在新桶列表中的位置，不同点在于需通过CAS的操作修改新桶列表的头结点；执行完成后将advance设为true执行下一个节点，并将原桶列表对应位置CAS为forwardingNode标记。
注：
* 这里加锁和CAS操作的都是原列表节点，不会影响新的桶列表
* 在synchronize加锁桶节点后，进入扩容代码前会判断当前的tab节点还是不是synchronize锁住的节点（因为其它线程拿到锁后已经将该桶节点CAS为forwardingNode标识节点）；
* TreeBIN的默认Hash值为-2;
代码语言：java复制else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) { // 再次判断，确保当前位置没有被其它线程CAS为forwardingNode
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;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}注：
源码中对链表元素搬移的代码可以学习下。链表构造函数中带上其后继节点，每次新建时相当于返回了节点的前一个节点，最终将首节点置到新桶列表的位置上
代码语言：java复制 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);- 扩容结束
- 判断当前的sizeCtl时，如果(sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT，则还有其它线程正在扩容，这里直接返回，减少不必要的确认；否则将i重新赋值，再检查一次是否老table的数据已经完全迁移（通过每个桶的hash值是否为MOVED进行判断）
- 将SIZECTL CAS为当前值减1。因为有其它线程协助transfer时，会将SIZECTL的值 1
- SIZECTL在扩容时会被置为负值，正常使用时为正值，concurrentHashMap默认是n * 0.75。在最后退出时将sizeCtl通过赋值操作进行还原
if (i < 0 || i >= n || i n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1); // 还原sizeCtl为0.75n
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
}
}put操作
- 当tab为null时初始化table，通过CAS确保线程安全；
- 桶元素为null时，CAS将当前key value新建node放到对应桶上，不阻塞；如果被该桶的位置被其它线程放置元素，则下次循环时该桶元素不为null，满足条件；
- 如果当前桶元素的hash值为MOVED，结合transfer函数可以知道当前位置正处于扩容状态，执行helpTransfer方法加入扩容
- 如果当前值不为null，通过上文提到的synchronize和检查结合机制将节点进行插入
- 执行addCount处理，主要执行transfer扩容方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(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<K,V> e = f;; binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
