HashMap(JDK7)

Hash 表结构几个重要的通用操作, hash 函数、hash 冲突、rehash 及扩容;

存储结构与初始化

(1) 结构

底层结构中为每一个 Node 添加指向 prev, next 的引用

1
transient Entry[] table;

Entry 存储着键值对,为链表结构,数组每个位置相当于一个桶,桶中存放链表。借助其来处理 Hash 冲突。

1
2
3
4
5
6
class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}

(2) 初始化

① 无参初始化;

② Map 传入初始化;

③ 指定初始化容量;

④ 执行初始化容量和负载因子;

1
Map<Obejct, Object> map = new HashMap<>(x * 4/3);    // loadFactor to prevent grow

操作

1、hash 函数 | 元素定位

① 整体的定位

1
2
int hash = hash(key);
int i = indexFor(hash, table.length);

② 具体的 hash 确定

通过多次移位和异或进行 hash 扰动,使其尽量不依赖于传入的 hashCode 的不均匀性;

1
2
3
4
5
6
7
8
9
10
11
12
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

③ 根据 hash 确定桶下标

1
2
3
static int indexFor(int h, int length) {
return h & (length-1);
}

2、get()

查找需要分成两步进行:

  • 计算键值对所在的桶;
  • 在链表上顺序查找,时间复杂度和链表的长度成正比;
1
2
3
4
5
6
7
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}

3、put

(1) 总体实现流程

①判断初始化,未初始化则做对应的初始化

②Null 值特殊处理,Null 无法调用 hashCode(),防止 NullPointerException

③确定桶下标

④遍历链表,若重复直接覆盖并返回

⑤为新加入元素,插入 <K,V>

⑥根据情况看是否需要扩容处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 键为 null 单独处理
if (key == null)
return putForNullKey(value);
int hash = hash(key);
// 确定桶下标
int i = indexFor(hash, table.length);
// 先找出是否已经存在键为 key 的键值对,如果存在的话就更新这个键值对的值为 value
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
// 插入新键值对
addEntry(hash, key, value, i);
return null;
}

(2) 对于 NULL 的插入处理

无法调用 null 的 hashCode() 方法,也就无法确定该键值对的桶下标,只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) { /*0 bucket*/
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

(3) 处理 Hash 碰撞

头插法处理;

在容量阈值达到时,进行 2 倍扩容操作;

是一种添加之后,再进行扩容的行为,依赖的是上次添加完毕的情况;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 头插法,链表头部指向新的键值对
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

4、扩容 | rehash

(1) 影响的变量

① loadFactor: 负载因子时间上和空间上的一种平衡:

  • ↑ 查找性能差, 空间利用率高;
  • ↓ 查找性能高, 空间利用率低;

② size | threshold: size/capacity 达到负载因子时进行对应的扩容

③ modCount:用来处理扩容时出现并发访问造成数据不一致,从而 fail-fast

1
2
3
4
5
6
7
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;

(2) 扩容实现

在负载因子达到给定值的情况下进行扩容;

扩容为原来数组的两倍;

需要将原来的 Entry 重新插入到新建的表中;

1
2
3
4
5
6
7
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
...
}

(3) rehash | 计算桶下标

在进行扩容时,需要把键值对重新放到对应的桶上。HashMap 使用了一个特殊的机制,可以降低重新计算桶下标的操作。

根据 hash 值在当前的高位上是否为 0,进行不同的处理。

  • 为 0: 不需要移动
  • 为 1: 移动偏移 原来容量对应的桶上;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}

其他

(1) JDK7 与 JDK8 中 HashMap 的比较

① 底层结构上:

  • JDK8 采用 数组 + 链表 + 红黑树实现,长度过长转换成红黑树有效防范了 Hash 碰撞攻击;
  • 将原来的 Entry 改为 Node,表示红黑树节点、链表节点;

② hash 函数: JDK8 只需要一次移位和异或即可,既能有效处理冲突上还保证了执行效率;

③ 处理 hash 冲突上: 在为链表时,通过尾插法进行处理,避免出现逆序且链表死循环问题;

(2) 不安全体现

扩容时因为头插法而形成环形引用,造成无限循环,CPU 100%;

put 操作可能造成丢失修改;

HashMap(JDK8)

底层结构与初始化

(1) 整体结构

① table: 存储节点类型,用于多态扩展

② loadFactor: 负载因子,控制扩容的时机

③ modCount: 控制迭代访问, fail-fast

1
2
3
4
5
transient Node<K,V>[] table; 
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

(2) 节点与树化

① 控制树化的时机:

  • TREEIFY_THRESHOLD(8): 链表元素大于该值的时候进行树化
  • UNTREEIFY_THRESHOLD(6): TreeNode 中元素删除到该值时,将结构退化为链表,一般比 TREEIFY_THRESHOLD(8) 小,避免复杂度震荡
  • MIN_TREEIFY_CAPACITY(64): 在整个 HashMap 的容量小于该值的时候,即使单个桶中的元素达到 TREEIFY_THRESHOLD(8),不会进行树化,会直接进行 rehash。
1
2
3
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6; /* prevent complexity oscillation */
static final int MIN_TREEIFY_CAPACITY = 64; /* prevent resize and treeify conflict */

② 链表节点结构:

1
2
3
4
5
6
class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}

③ 红黑树节点结构: 继承 LinkedHashMap.Entry,便于从 tree 回退到 listNode

1
2
3
4
5
6
7
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}

操作

1、hash 函数 | 元素定位

一次异或一次移位进行 hash 扰动,避免依赖于原来 hashCode 处理键冲突,提高 hash 值的扩散性;

对于 null 的 KEY,直接使其 hash 值为 0,从而避免 NullPointerException;

1
2
3
4
int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、get()

执行过程:

  • 定位到对应的桶看是否有该 KEY
  • 首个节点为该 KEY,则直接返回
  • 若为 TreeNode,进行红黑树的查找逻辑
  • 若为 ListNode 进行链表的迭代遍历查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

3、put

(1) 执行流程:

① 如果 HashMap 未被初始化过,则初始化;

② 对 Key 求 Hash 值,然后再计算下标;

③ 如果没有碰撞直接放入桶中;

④ 如果碰撞了,以链表的方式链接到后面;

⑤ 如果链表长度超过阀值,就把链表转成红黑树;

⑥ 如果链表长度低于 6,就把红黑树转回链表;

⑦ 如果节点已经存在就替换旧值;

⑧ 如果桶满了(容量 16 *加载因子 0.75 ),就需要 resize(扩容 2 倍后重排)

(2) 额外功能:

  • null 值处理: 直接通过 hash(key) 给 NULL KEY 为 0 的值;
  • onlyIfAbsent: 实现 putIfAbsent() 方法逻辑,保留旧的值;
  • afterNodeAccess,afterNodeInsertion: hook 钩子函数进行特殊处理,可用于 LinkedHashMap 实现 LRU;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) /* 初始情况 */
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) /* 插入的桶无元素 */
tab[i] = newNode(hash, key, value, null);
else {
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) /* 总体的容量扩容 */
resize();
afterNodeInsertion(evict);
return null;
}

(3) Hash 冲突处理

对于链表的 hash 冲突

部分 putVal() 方法:

为了实现树化,需要统计链表中的个数,直接遍历到链表尾部,进行插入;

1
2
3
4
5
6
7
8
9
10
11
12
for (int binCount = 0; ; ++binCount) {                // 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;
}

3、 扩容 | rehash

两种可能情况:

  • 仍然在原来的位置
  • 在原来的位置上偏移原来的容量

(1) 链表拆分

将原来的链表拆成两条链表,低位链表的数据将会到新数组的当前下标位置,高位链表的数据将会到新数组的当前下标+当前数组长度的位置;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}

4、 树化

(1) 链表转为红黑树

在挂接的链表大于 TREEIFY_THRESHOLD 时进行树化逻辑;

容器整体大于 MIN_TREEIFY_CAPACITY 时才允许树化,否则进行 resize;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void treeifyBin(Node<K,V>[] tab, int hash) {                 
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); /* 当前容量太小,直接扩容,防 resize 和 treeify 频繁性能损耗 */
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

(2) 红黑树转变成链表

在红黑树节点数少于 UNTREEIFY_THRESHOLD(6) 时,进行结构转变;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// TreeNode.split
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}

ConcurrentHashMap(JDK7)

http://img.janhen.com/20210130172336image-20201031105854190.png

ConcurrentHashMap 和 HashMap 实现上类似,最主要的差别是 ConcurrentHashMap 采用了分段锁(Segment),每个分段锁维护着几个桶(HashEntry),多个线程可以同时访问不同分段锁上的桶,从而使其并发度更高(并发度就是 Segment 的个数)。

底层结构与初始化

(1) 全局结构

segmentShift | segmentMask: 用于快速定位到 Segment 的位置

1
2
3
4
final int segmentShift;
final int segmentMask;
final Segment<K,V>[] segments; // keep object
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

(2) Segment 结构

相当于一个带有锁的 HashMap(7)

① 继承自 ReentrantLock 从而实现并发加分段锁访问;

② 保存了 count 用于整个容器的统计,以及作为扩容的参考值;

默认情况下并发级别为 16;

1
2
3
4
5
6
7
8
9
static final class Segment<K,V> extends ReentrantLock implements Serializable {
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry<K,V>[] table;
transient int count; // use for size()
transient int modCount;
transient int threshold;
final float loadFactor;
}

(3) HashEntry 结构

1
2
3
4
5
6
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}

操作

1、hash & 定位

先整体进行了多次异或操作,进行 hash 扰动,将每位都用上。

通过 hash 借助 sementShift 和 segmentMask 来定位到对应的段上。

1
2
3
final Segment<K,V> segmentFor(int hash) {
return segments[(hash >>> segmentShift) & segmentMask];
}

定位到 Entry,定位 Segment 使用的是元素的 hashcode 通过再散列后得到的值的高位,而定位 HashEntry 直接使用的是再散列后的值。其目的是避免两次散列后的值一样,虽然元素在 Segment 里散列开了,但是却没有 HashEntry 里散列开。

1
2
hash >>> segmentShift) & segmentMask   // 定位Segment所使用的hash算法
int index = hash & (tab.length - 1);   // 定位HashEntry所使用的hash算法

2、get()

无锁获取值实现:

基于 volatile 来替代锁实现,由 JMM 提供的 happen before 原则保证可见性;

通过 hash 得出对应的散列值,之后通过 hash 定位到对应的段;

在桶中再进行 hash 得到对应的桶,只有在读取到 NULL 值时才进行加锁;

1
2
3
4
5
6
7
8
9
10
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}

// Segment 中的总数
transient volatile int count;

// HashEntry 中的值
volatile V value;

3、put()

判断是否需要扩容,不是添加之后进行判断的,在插入前进行判断,避免无效的扩容。

扩容仅仅是对当前的 Segment 进行扩容,无需对整个容器扩容。

4、size()

在执行 size 操作时,需要遍历所有 Segment 然后把 count 累计起来。

可能的两步操作:

① 先尝试通过 RETRIES_BEFORE_LOCK(2) 次借助 segment 中 volatile 保存的 count 相加,基于 modCount 来实现的;

② 若无法则对整个容器进行加锁统计所有 Segment 的大小;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static final int RETRIES_BEFORE_LOCK = 2;
public int size() {
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
// 过多 CAS 转换成对所有 Segment 加锁获取
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
// 连续两次得到的结果一致,则认为这个结果是正确的
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}

其他

(1) JDK7 与 JDK8 中 ConcurrentHashMap 的比较

① 底层结构: 链表过长转换成红黑树

② 同步机制: JDK7 采用分段锁实现,而 JDK8 可以有两种方案

  • 尝试通过 CAS 来支持更高的并发度;
  • 在 CAS 失败时通过内置锁 synchronized 锁住链表 | 红黑树的头结点;

ConcurrentHashMap(JDK8)

http://img.janhen.com/20210130172332image-20201031105915401.png

五十几个内部类,Guava 中的 Cache 基于此实现。

无法存放 NULL。

底层结构与初始化

(1) 底层结构

① nextTable: 用于并发下的扩容操作

② transferIndex: 在 rehash 情况下的标记索引

③ counterCells: 用于并发下获取容量,不精确,与 LongAdder 类似

1
2
3
4
5
6
7
transient volatile Node<K,V>[] table;
transient volatile Node<K,V>[] nextTable;
transient volatile long baseCount;
transient volatile int sizeCtl;
transient volatile int transferIndex;
transient volatile int cellsBusy;
transient volatile CounterCell[] counterCells;

(2) 初始化

五种初始化方式:

前四种同 HashMap 初始化方式;

⑤ 初始容量、负载因子、并发级别: 含有并发级别控制;

并发级别基本不用,初始化用于与 initialCapacity 进行比较取最大值;

与 JDK7 进行兼容的处理逻辑;

操作

1、hash 函数|定位

通过传入对象的 hashCode 来进行对应的处理

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

2、get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}

3、put()

① 判断 Node[] 数组是否初始化,没有则进行初始化操作

② 通过 hash 定位数组的索引坐标,是否有 Node 节点,如果没有则使用 CAS 进行添加(链表的头节点),添加失败则进入下次循环。

③ 检查到内部正在扩容,就帮助它一块扩容。

④ 如果 f != null 则使用 synchronized 锁住 f 元素(链表/红黑二叉树的头元素)

4.1如果是Node(链表结构)则执行链表的添加操作。

4.2如果是TreeNode(树型结构)则执行树添加操作。

⑤ 判断链表长度已经达到临界值 8 (default)节点数超过这个值就需要将链表转换为树结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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;;) { // may enter this loop many times
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) /* P1. not init */
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { /* P2. 第一个桶位置为空, CAS添加 */
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) /* P3. 其他线程正在扩容 */
tab = helpTransfer(tab, f);
else { /* 发生 hash 碰撞, 处理 listnode OR treenode, 只有此时才加锁, 其他情况都 CAS 循环尝试 */
V oldVal = null;
synchronized (f) { /* 使用第一个元素作为锁, 粒度比 Segment 分段锁更加细 */
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;
}

3、扩容

// todo

HashTable

http://img.janhen.com/20210130172343image-20201031105952779.png

与 JDK7 的 HashMap 基本一致;

线程安全的同步容器;

底层结构与初始化

(1) 底层结构

1
2
3
4
5
6
class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
}

(2) 初始化容量为 11

1
2
3
public Hashtable() {
this(11, 0.75f);
}

操作

1、hash | 定位

直接通过取模实现;

效率较 HashMap 低;

1
2
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

2、 扩容 | rehash

容量为 2*oldCapacity+1

初始容量和扩容机制都与 HashMap 不同;

1
int newCapacity = (oldCapacity << 1) + 1;

3、 迭代方式

通过 Enumerator 实现,而非 Iterator。

1
2
3
4
5
6
7
<T> Iterator<T> getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}

其他

(1) 与 HashMap的区别

① HashTable 设计上基于 Dictionary 实现,线程安全,执行效率低下,而 HashMap 基于 AbstractMap 实现,线程不安全,执行效率比 HashTable 高;

② NULL 值: HashMap 允许 NULL 值, HashTable 不允许;

③ 初始化与 hash 定位: HashTable 初始容量为 11,HashMap 初始容量为 16,HashTable 通过 % 的方式进行定位,HashMap 通过移位异或进行定位;

④ 迭代访问上: 两者实现的迭代不同,一个基于 Iterator,一个基于 Enumerator;

LinkedHashMap

默认保持元素插入属性的 Map;

可先通过 HashMap 来进行统计一些必要的数据,之后通过对 HashMap 的 KEY, VALUE 进行一些排序,将其变为有序的,使用 LinkedHashMap 来将这些顺序串联起来,之后进行对应的逻辑处理;

底层结构

(1) 全局属性

① accessOrder: 控制开启访问作为次序,可借助 LinkedHashMap 实现 LRU Cache;

② head|tail: 控制按照插入 | 访问顺序迭代;

1
2
3
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;

(2) 节点

before | after 用于将节点连接起来方便遍历;

HashMap.TreeNode 扩展此节点;

1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {       
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}

应用

(1) LRU Cache

通过 HashMap 的 putVal() 中提供的两个 hook 钩子函数实现特有的功能;

根据 assessOrder 值不同,迭代出不同的结果。为 true,执行 LRU 顺序,访问过后移到链表尾部,头部为最近最久未使用节点; 为 false,执行插入顺序,与 List 语义相同;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}
}

在 put 等操作之后执行,当 removeEldestEntry() 方法返回 true 时会移除最晚的节点,也就是链表首部节点 first。

evict 只有在构建 Map 的时候才为 false,在这里为 true。

1
2
3
4
5
6
7
void afterNodeInsertion(boolean evict) {     // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}

removeEldestEntry() 默认为 false,如果需要让它为 true,需要继承 LinkedHashMap 并且覆盖这个方法的实现,这在实现 LRU 的缓存中特别有用,通过移除最近最久未使用的节点,从而保证缓存空间足够,并且缓存的数据都是热点数据。

1
2
3
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}

(1-2) LinkedHashMap 实现的线程安全的 LRUCache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static final float DEFAULT_LOAD_FACTOR = 0.75f;

private int capacity;
private LinkedHashMap<K,V> cache;

public LRUCache(int capacity) {
this.capacity = capacity;
cache = new LinkedHashMap((int) Math.ceil(capacity/DEFAULT_LOAD_FACTOR) + 1, DEFAULT_LOAD_FACTOR, true){
private static final long serialVersionUID = 223232L;
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return cache.size() >= capacity;
}
};
}

public synchronized V get(K key) {
return cache.get(key);
}

public synchronized V put(K key, V val) {
return cache.put(key, val);
}

(2) 借助多态将 HashMap 中的数据按照一定的规则进行排序

如 HashMap 存放的是词频,可以根据词频进行排序,之后迭代访问时就是词频从高到低的序列;

其他

(1) 与 HashMap 的区别

① 设计层面上: LinkedHashMap 是 HashMap 的子类;

② 底层结构及功能扩展上: LinkedHashMap 节点中添加了 before, after 用于保证顺序;

③ put 操作: LinkedHashMap 在继承的基础上重写 HashMap 中的 hook(钩子) 方法,在 LinkedHashMap 中向哈希表中插入新 Entry 的同时,还会通过 Entry 的 addBefore 方法将其链入到双向链表中。

④ get 操作: LinkedHashMap 中重写了 HashMap 中的 get 方法,通过 HashMap 中的 getEntry 方法获取 Entry 对象。 在此基础上,进一步获取指定键对应的值。

⑤ 在扩容操作上: 虽然 LinkedHashMap 完全继承了 HashMap 的 resize 操作,但是鉴于性能和 LinkedHashMap 自身特点的考量, LinkedHashMap 对其中的重哈希过程(transfer 方法)进行了重写。

TreeMap

红黑树的实现

// todo

X、其他 与 HashMap 的区别

① 顺序性: TreeMap 可对按照 Key 的自然顺序或是传入的比较器进行排序;

② 存取效率上: O(1) VS O(logN);

ThreadLocalMap

对于 ThreadLocal:

  • 当使用 ThreadLocal 维护变量时,ThreadLocal 为每个使用该变量的线程提供独立的变量副本,所以每一个线程都可以独立地改变自己的副本,而不会影响其它线程所对应的副本;
  • 是一种无锁同步方案;
  • 是一种用空间换取时间来保证线程安全的方案;
  • 多线程情况下,对应的子线程的 ThreadLocal 无法获取到父线程的 ThreadLocal,需要第三方工具包支持,可选择 alibaba 的 transmittable-thread-local 包;

1、底层结构

(1) 全局结构

1
2
3
4
static final int INITIAL_CAPACITY = 16;
Entry[] table;
int size = 0;
int threshold;

(2) Entry

继承自 WeakReference ,在无活跃线程或栈中持有时,在 GC 时就会被回收;

节点只保存值,ThreadLocalMap 不是使用链地址法来解决 Hash 冲突;

多个线程,只设置一个 ThreadLocal 变量,在这个线程中的 ThreadLocal 变量的值始终是只有一个的,即以前的值被覆盖了的。这里是因为 Entry 对象是以该 ThreadLocal 变量的引用为 key 的,所以多次赋值以前的值会被覆盖。

1
2
3
4
5
6
7
static class Entry extends WeakReference<ThreadLocal<?>> {
Object value;
Entry(ThreadLocal<?> k, Object v) { /* ThreadLocal as key */
super(k);
value = v;
}
}

(3) 定位

通过此来进行 hash 桶的定位;

1
final int threadLocalHashCode = nextHashCode();

(4) 负载因子

0.66

空间利用率相较于 HashMap 的 0.75 较低,但加快查询;

同时配合开放地址法来快速定位到空闲的桶;

1
2
3
private void setThreshold(int len) {
threshold = len * 2 / 3;
}

操作

1、hash()

没有扰动函数,通过 ThreadLocal 中保存的 threadLocalHashCode 来实现;

threadLocalHashCode 根据维护的 AtomicInteger nextHashCode 获取;

1
2
3
4
5
6
7
8
// ThreadLocal
private final int threadLocalHashCode = nextHashCode();
private static AtomicInteger nextHashCode = new AtomicInteger();
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
// ThreadLocalMap.getEntry
int i = key.threadLocalHashCode & (table.length - 1);

2、get()

1
2
3
4
5
6
7
8
private Entry getEntry(ThreadLocal<?> key) {
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
if (e != null && e.get() == key)
return e;
else
return getEntryAfterMiss(key, i, e);
}

3、set()

① 先获取到 ThreadLocal 键的 thresholdLocalHashCode ,以此来确定对应的桶下标;

② 如果在该位置正好与当前进行重合,直接覆盖;

③ 如果该位置无元素,则将其放入该位置;

④ 上面两个都不满足的情况下,使用线性探测法不断寻找到对应的满足上述两个条件的位置;

⑤ 上述都不满足,创建一个节点,并清理一些桶位,之后进行重新 hash ;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private void set(ThreadLocal<?> key, Object value) {

// We don't use a fast path as with get() because it is at
// least as common to use set() to create new entries as
// it is to replace existing ones, in which case, a fast
// path would fail more often than not.

Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);

for (Entry e = tab[i]; // bucket position
e != null;
e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();

if (k == key) {
e.value = value;
return;
}

if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}

tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold) // add node need to clean some object
rehash();
}

4、扩容 | rehash

(1) rehash

1
2
3
4
5
6
void rehash() {
expungeStaleEntries();
// Use lower threshold for doubling to avoid hysteresis
if (size >= threshold - threshold / 4)
resize();
}

(2) resize

扩容为原来的两倍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void resize() {
Entry[] oldTab = table;
int oldLen = oldTab.length;
int newLen = oldLen * 2;
Entry[] newTab = new Entry[newLen];
int count = 0;

for (int j = 0; j < oldLen; ++j) {
Entry e = oldTab[j];
if (e != null) {
ThreadLocal<?> k = e.get();
if (k == null) {
e.value = null; // Help the GC
} else {
int h = k.threadLocalHashCode & (newLen - 1);
while (newTab[h] != null)
h = nextIndex(h, newLen);
newTab[h] = e;
count++;
}
}
}

setThreshold(newLen);
size = count;
table = newTab;
}

其他

(1)与 HashMap 的比较

① 底层结构:

  • ThreadLocalMap 只有数组,HashMap 通过数组 + 链表(Tree) 方式
  • 节点引用类型: ThreadLocalMap 节点为弱引用,会下一次 GC 被回收

② hash: 并发下通过 AtomicInteger 实现

③ hash 冲突处理: ThreadLocalMap 通过线性探测法实现的,HashMap 通过链地址法实现;

WeakHashMap

底层结构

(1)节点

与 Entry 继承 WeakReference,当前 Entry 需要引用队列来进行处理;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 成员
ReferenceQueue<Object> queue = new ReferenceQueue<>();
// 单独的 Entry
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
final int hash;
Entry<K,V> next;

Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) { /* must use reference queue */
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
}

操作

1、hash | 定位

通过四次异或来进行 hash 扰动,使其少依赖于原始的 hashCode()

1
2
3
4
5
6
7
8
final int hash(Object k) {
int h = k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
int indexFor(int h, int length) {
return h & (length-1);
}

2、put

NULL 值: 对 NULL 的 KEY 处理机制,将 NULL 作为指向一个对象进行存储

1
2
3
4
static final Object NULL_KEY = new Object();
private static Object maskNull(Object key) {
return (key == null) ? NULL_KEY : key;
}

Ref

  • 《Java并发编程的艺术》方腾飞 / 魏鹏 / 程晓明