一、介绍
基于哈希表的 Map 接口实现。此实现提供了所有可选的映射操作，并允许 null 值和 null 键。HashMap 类大致等同于 Hashtable，只是 HashMap 是非同步的，并且允许 null 作为键和值。HashMap 不保证映射的顺序，同样也不会保证顺序会随时间保持不变。
假如哈希函数将元素适当地分散到各个桶中，则此实现对基本操作 get 和 put 提供恒定时间性能。遍历集合视图所需的时间与 HashMap 实例的“容量”（桶的数量）加上其大小（键值映射的数量）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高或将载荷系数设置得太低。
HashMap 实例有两个参数影响其性能：初始容量和载荷系数。容量是哈希表中的桶数量，初始容量是在创建哈希表时的容量。载荷系数是衡量哈希表在自动增加容量之前可以变得多满的一个度量。当哈希表中存储的项的数量（Entry 的数量）超过载荷系数与当前容量的乘积时，哈希表将重新进行哈希从而重新构建内部数据结构，使哈希表的容量大约为现有桶数量的两倍。
一般来说，默认的载荷系数 0.75 在时间和空间成本之间提供了良好的折衷。较高的值减少了空间开销，但增加了查找成本（这体现在 HashMap 类的大多数操作中，包括 get 和 put）。在设置其初始容量时，应考虑映射中的预期条目数及其载荷系数，尽可能地最小化重新哈希操作的次数。如果初始容量大于条目最大数量除以载荷系数的结果，则永远不会发生重新哈希操作。
如果要在 HashMap 实例中存储许多映射，则使用足够大的容量创建它将允许更有效地存储映射，而不是让它根据需要自动重新哈希以扩展表。请注意，使用具有相同 hashCode() 值的键肯定会减慢哈希表的性能。为了减轻此影响，当键是可比较（实现 Comparable 接口）时，此类可能会使用键之间的比较顺序来帮助打破哈希值相同导致性能下降的情况。
HashMap 不是同步的。如果多个线程并发访问同一个 HashMap，并且至少有一个线程对映射进行了结构性修改，那么它必须额外进行同步操作。也可以选择使用 Collections.synchronizedMap 方法来“包装” map，这最好在创建时完成，以防止意外地对 map 进行非同步访问：
1
| Map m = Collections.synchronizedMap(new HashMap(...));
|
另外，结构性修改是指添加或删除一个或多个映射的任何操作；仅仅改变实例中已经包含的键所对应的值并不是结构性修改。
此类中所有“集合视图方法”返回的迭代器都是快速失败的：如果在迭代器创建后的任何时候，以非迭代器自身的 remove 方法之外的任何方式修改了映射的结构，迭代器将抛出 ConcurrentModificationException。因此，在面对并发修改时，迭代器会迅速干脆地失败。
注意，在存在不同步的并发修改的情况下，迭代器的快速失败行为是无法保证的。在面对快速失败时，迭代器会尽最大努力抛出 ConcurrentModificationException。因此，编写一个依赖于此异常来确保其正确性的程序是错误的：迭代器的快速失败行为仅应用于检测错误。
二、源码
1、常量
1
2
3
4
5
6
7
8
9
10
11
| static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
|
默认初始化容量由 DEFAULT_INITIAL_CAPACITY 指定，默认容量为 16，容量为桶数组的长度。属性注释上面还有一句：MUST be a power of two，值必须是 2 的幂。
最大容量由 MAXIMUM_CAPACITY 指定，当使用带有指定初始化容量的构造函数创建新的 map 时，如果初始化容量大于 MAXIMUM_CAPACITY 的值，将 map 的初始化容量赋值为 MAXIMUM_CAPACITY，如下代码所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
|
默认的载荷因子由 DEFAULT_LOAD_FACTOR 指定，在使用没有指定载荷因子的构造器创建 map 对象时，将使用此载荷因子。值为 0.75
TREEIFY_THRESHOLD 属性用来指定变成树型结构的阈值。当一个桶中的节点数量超过这个阈值时，该桶会从链表结构转换为树型结构（通常是红黑树），目的是提高桶中元素的查找和插入效率。默认值为 8，也就是说当桶中的元素数量超过 8，且此 HashMap 对象中的桶容量（桶数组的长度）大于等于 MIN_TREEIFY_CAPACITY 属性指定的容量时，这个桶中的链表将会转换为红黑树。链表查找的时间复杂度为 O(n)，而红黑树查找的时间复杂度为 O(log n)，这意味着当链表长度较大时，红黑树效率将更高。
MIN_TREEIFY_CAPACITY 属性用来定义触发树化操作的最小哈希表的容量（桶数组大小）。只有在哈希表容量大于或等于这个值时，才会触发树化操作。这是为了防止在哈希表很小且桶中链表元素数量相对较少的情况下过早地执行树化操作，因为这会引入额外的空间和时间开销。默认值为 64，也就是说，即使某个桶中的链表长度大于 TREEIFY_THRESHOLD 属性的值，但哈希表的总容量小于 64 时，不会执行树化操作。因为在哈希表容量较小时，扩容比树化更高效，既能减少哈希冲突，又能避免红黑树带来的额外的空间开销，红黑树节点占用空间是链表的两倍。
当向一个桶中添加元素时，如果该桶中的节点数量至少达到 TREEIFY_THRESHOLD 指定的阈值，桶将被转换为树形结构。该值必须大于 2，并且应至少为 8，为了与在删除操作中将树型结构转换为链表时的收缩检测阈值匹配。
UNTREEIFY_THRESHOLD 属性用来指定从树型结构转变为链表结构的阈值。当哈希表在进行扩容时（扩容会重新构建内部数据结构）之前因为链表过长而转换为红黑树的桶中的元素数量在扩容后小于该属性指定的值了，那么红黑树将会被转换为链表。该值应该要小于 TREEIFY_THRESHOLD 属性的值，为了防止因为短暂的列表长度增加而导致的频繁的树化和链表化操作。该值最多为 6（TREEIFY_THRESHOLD 为 8），以便与删除操作时的收缩检测匹配。
那后续什么时候会树化呢？万一是从 63 变为了 64，是不是此时会树化？
2、静态内部类 Node
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
| static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
return o instanceof Map.Entry<?, ?> e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}
}
|
内部类 Node 是 HashMap 中用于存储键值对的基础数据结构。它是 HashMap 中每个桶（bucket）中元素的节点，代表着键值对的存储单元。
类中定义的属性有：
key，节点所存储的键。value，节点所存储的值。hash，节点的哈希值，用于确定结点应该存放在哪个桶中。next，指向桶中下一个节点（链表结构中的下一个节点）的引用。此为处理哈希冲突的机制之一，当多个键的哈希值相同且映射到同一个桶中时，这些键值对会通过链表连接在一起。
Node 为 Map.Entry<K,V> 接口的具体实现，Map.Entry<K,V> 源码中包括待实现的方法还有默认方法：
1
2
3
4
5
6
7
8
9
10
11
12
| interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
|
3、属性
1
2
3
4
5
6
7
8
9
10
11
| transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
|
table 属性在首次使用时进行初始化，并根据需要调整大小。在初始化或调整大小时，该数组的长度总是 2 的幂。在某些操作中，还允许该数组的长度为 0
size 属性表示此哈希表中键值对映射的数量。
modCount 属性表示此哈希表被结构性修改的次数，结构性修改指的是改变哈希表中映射数量或以其他方式修改其内部结构的修改，比如在扩展哈希表容量时进行重新哈希。此字段用于在哈希表集合视图的迭代器中快速失败。
threshold 属性表示哈希表需要扩容之前允许的最大键值对数量，计算方式为 容量 * 载荷系数
loadFactor 属性表示哈希表的载荷系数
4、构造方法
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
| public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
|
构造方法主要是由初始容量和负载系数两个参数来决定的。另外还有使用其他哈希表来重新构建一个哈希表的构造方法，在此方法中载荷系数为默认的载荷系数（0.75）。
构造方法中设及到两个其他方法 tableSizeFor 和 putMapEntries。
4.1 tableSizeFor 方法
tableSizeFor 方法用来返回给定目标容量的 2 次幂。
1
2
3
4
| static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
|
4.2 putMapEntries 方法
putMapEntries 方法是一个用于将另一个 Map 中的所有条目（键值对）插入到当前 HashMap 中的辅助方法。这个方法通常用于批量插入条目，以提高效率。该方法由 putAll 方法和以 map 为参数的构造方法调用。
方法有两个参数：
- 第一个参数是一个 map
- 第二个参数表示是否为初次构建 map，初次构建时为 false，否则为 true。比如在该方法的两个调用点中，构造函数中
evict 参数传 false，putAll 方法中 evict 参数传 true
在插入新条目之前，putMapEntries 会检查当前哈希表是否需要扩容。如果哈希表的容量不足以容纳新插入的条目（即条目的数量超过 threshold），则会调用 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
28
29
| final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int size = m.size();
if (size > 0) {
if (table == null) {
double dt = Math.ceil(size / (double) loadFactor);
int t = dt < (double) MAXIMUM_CAPACITY ? (int) dt : MAXIMUM_CAPACITY;
if (t > threshold) {
threshold = tableSizeFor(t);
}
} else {
while (size > threshold && table.length < MAXIMUM_CAPACITY) {
resize();
}
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
|
5、查询方法
1
2
3
4
5
6
7
8
9
10
11
12
13
| public interface Map<K, V> {
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
}
|
5.1 size 方法
1
2
3
| public int size() {
return size;
}
|
5.2 isEmpty 方法
1
2
3
| public boolean isEmpty() {
return size == 0;
}
|
5.3 containsKey 方法
如果此 map 包含指定键的映射，则返回 true
1
2
3
| public boolean containsKey(Object key) {
return getNode(key) != null;
}
|
5.4 containsValue 方法
如果此 map 包含一个或多个指定值，则返回 true，否则返回 false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public boolean containsValue(Object value) {
Node<K,V>[] tab = table;
V v;
if (tab != null && size > 0) {
for (Node<K,V> e : tab) {
for (; e != null; e = e.next) {
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
|
该方法将哈希表的所有桶中的所有元素都遍历了一遍，直到查询出参数中指定的值为止。
5.5 get 方法
返回指定键映射的值，如果此映射中不包含该键的映射，则返回 null。
返回值为 null 并不一定表明映射中不包含该键的映射；也有可能映射明确地将该键映射为 null。可以使用 containsKey 操作来区分这两种情况。
1
2
3
4
| public V get(Object key) {
Node<K,V> e = getNode(key);
return e == null ? null : e.value;
}
|
6、修改方法
1
2
3
4
5
6
| public interface Map<K, V> {
V put(K key, V value);
V remove(Object key);
}
|
6.1 put 方法
1
2
3
| public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
|
put 方法对 putVal 方法进行调用，putVal 方法的参数 onlyIfAbsent 赋值为 false，也就是说如果待 put 元素存在则会覆盖掉。evict 参数为 true，表示不是哈希表初次构建时调用。
6.2 remove 方法
该 remove 方法根据指定键从哈希表中删除映射，如果存在的话。删除后会将键映射的值返回，如果指定键在哈希表中没有映射，将返回 null。注意，返回值为 null，也可能代表该键映射的值即为 null，因为 HashMap 中允许键或值为 null
1
2
3
4
| public V remove(Object key) {
Node<K,V> e = removeNode(hash(key), key, null, false, true);
return e == null ? null : e.value;
}
|
另外还有删除方法，是 Map 接口中的默认方法（default），在 HashMap 中重写了，该方法会根据元素的键和值删除元素。
1
2
3
4
| @Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
|
7、批量操作方法
1
2
3
4
5
6
| public interface Map<K, V> {
void putAll(Map<? extends K, ? extends V> m);
void clear();
}
|
7.1 putAll 方法
将指定 map 中的所有映射都复制到此哈希表中。如果待插入的元素的键在此哈希表中存在，则此哈希表中的元素将会被替换。
1
2
3
| public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
|
7.2 clear 方法
将此哈希表中的所有元素都删除。
1
2
3
4
5
6
7
8
9
10
11
12
| public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i) {
tab[i] = null;
}
}
}
|
8、基础支持方法
8.1 hash 方法
1
2
3
4
| static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
计算键的 hashCode() 并将哈希值的高位通过异或运算（XOR）传播到低位。由于哈希表使用的是 2 的幂次方掩码，因此那些在高位上有所变化的哈希集在当前掩码下总会发生碰撞。已知的例子包括在小容量的哈希表中，持有连续整数的 Float 类型键的集合。因此，应用了一种变换，将高位的影响向下传播。
在速度、实用性和位扩散质量之间存在权衡。因为许多常见的哈希集已经分布得相对合理（因此不需要进行位扩散），并且使用树结构来处理桶中的大量碰撞，所以只是通过最廉价的方式对一些移位后的位进行异或，以减少系统性损失，同时结合那些由于哈希表边界而不会用于索引计算的高位的影响。
8.2 getNode 方法
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
| final Node<K,V> getNode(Object key) {
Node<K,V>[] tab = table;
Node<K,V> first;
Node<K,V> e;
int hash;
K k;
if (tab != null && tab.length > 0
&& (first = tab[(tab.length - 1) & (hash = hash(key))]) != null) {
if (first.hash == hash
&& ((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;
}
|
8.2.1 通过 hashCode 确认元素所属桶的位置
上面的代码中有这么一部分：tab[(tab.length - 1) & (hash = hash(key))]，这部分的代码的作用是确定元素在数组（桶）中的存储位置。
其中 hash(key) 方法会根据 key 计算哈希码。tab.length 为哈希表底层数组（桶数组）的长度，这个长度是 2 的次幂，这个是 HashMap 的设计，目的是为了通过位运算来高效确定存储位置。
计算出来的哈希码是 int 类型，将一个整型映射到一个定长数组中，首先想到的是进行取模，即 %，被除数为哈希码，除数为 tab.length。而选择位运算取代取模运算的原因是：位运算相比取模运算，计算速度更快。
使用位运算取代取模运算的保证是：tab.length 是 2 的次幂。长度为 2 的次幂，那么长度减一的二进制将会表示为一连串的 1。例如，长度为 16，二进制为 10000，而 15 的二进制为 01111。按位与运算，左右操作数的相对应的二进制位都为 1 时，结果为 1，否则为 0。所以一个哈希值和 tab.length - 1 进行按位与运算，将只会保留哈希值的低位部分，而低位部分的长度是 tab.length 确定的，所以计算结果将会保持在数组的索引范围内。
示例如下，长度为 16，最终确认的索引位置为 8
1
2
3
4
5
6
7
8
9
10
11
12
| int length = 16;
String key = "name";
int result = (length - 1) & hash(i);
|
可以看到，不仅避免了取模运算的开销，同时还能有效分配桶索引，保证哈希分布较为均匀。
8.3 putVal 方法
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab = table;
Node<K,V> p;
int n = tab.length;
int i;
if (tab == null || n == 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) {
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
|
putVal 方法调用点：
putMapEntries 方法put 方法putIfAbsent 方法readObject 方法
该方法中中的两个参数：
onlyIfAbsent，布尔值，如果为 true 时，将不会覆盖已经存在的值evict，布尔值，如果为 false，表示方法是在哈希表初始化时调用的
8.4 resize 方法
初始化或翻倍表的大小。
如果表为空，则根据字段 threshold 中持有的初始容量目标进行分配。否则，由于使用 2 的幂次方进行扩展，每个桶中的元素必须保持在相同的索引位置，或者在新表中以 2 的幂次方偏移量移动。
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap = 0;
int 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;
}
} else if (oldThr > 0){
newCap = oldThr;
} else {
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);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
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 if (e instanceof TreeNode) {
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
} else {
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;
}
}
}
}
}
return newTab;
}
|
resize 方法的调用点有：
putVal 方法中，当第一次向哈希表中存元素时putVal 方法中，当哈希表中元素的数量超过了扩容阈值时treeifyBin 方法中，调用时哈希表容量（桶数组长度）还没有达到 MIN_TREEIFY_CAPACITY 最小树化元素数量阈值，之进行扩容操作，不对链表进行树化putMapEntries 方法中，向哈希表中存放大量元素时，调用 resize 直到满足扩容目标为止computeIfAbsent 方法compute 方法merge 方法
8.5 removeNode 方法
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab = table;
int n = tab.length;
int index = (n - 1) & hash;
Node<K,V> p = tab[index];
if (tab != null && n > 0 && p != null) {
Node<K,V> node = null;
Node<K,V> e;
K k;
V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
node = p;
} else if ((e = p.next) != null) {
if (p instanceof TreeNode) {
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
} else {
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null
&& (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode) {
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
} else if (node == p) {
tab[index] = node.next;
} else {
p.next = node.next;
}
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
|
9、红黑树相关
9.1 treeifyBin 方法
该方法会在满足树化条件的情况下根据哈希值将对应桶中的链表转换为红黑树。
树化有两个限制条件，满足这两个条件才会将桶中的链表转化为红黑树：
- 哈希表元素的总数量大于等于
MIN_TREEIFY_CAPACITY 常量所约定的数量
- hash 值对应的桶链表中元素的数量大于等于
TREEIFY_THRESHOLD 常量所约定的数量
该方法的调用点有：
putVal 方法compute 方法computeIfAbsent 方法merge 方法
treeifyBin 方法中只判断了 MIN_TREEIFY_CAPACITY，而针对 TREEIFY_THRESHOLD 方法的判断都在调用方法中。只满足 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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| final void treeifyBin(Node<K,V>[] tab, int hash) {
int n = tab.length;
int index;
Node<K,V> e;
if (tab == null || n < MIN_TREEIFY_CAPACITY) {
resize();
} else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null;
TreeNode<K,V> 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);
}
}
}
|
9.2 TreeNode
啊啊啊，红黑树好难，好多东西啊……
当某个桶中的链表长度超过 TREEIFY_THRESHOLD 且哈希表的所有节点数量超过了 MIN_TREEIFY_CAPACITY 属性指定的值时，HashMap 会将链表转换为红黑树结构，以提高查找和插入的效率。在这种情况下，Node 会被替换为 TreeNode，用于存储红黑树中的节点。
TreeNode 为树形桶的节点类。它继承了 LinkedHashMap.Entry（而 LinkedHashMap.Entry 又继承了 Node），因此既可以作为普通节点使用，也可以作为链表节点使用。
1
2
3
| static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
}
|
9.2.1. 属性
1
2
3
4
5
6
7
8
9
| TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
|
9.2.2 构造方法
HashMap 中的 TreeNode 对于红黑树的实现暂未整理……
三、其他
1、树化条件和扩容条件的区别
扩容由哈希表中元素数量超过阈值（容量 × 负载因子）触发，容量为桶数组的长度，负载因子为 loadFactor 属性指定，默认为 DEFAULT_LOAD_FACTOR，值为 0.75
树化则由单个桶的链表长度和哈希表容量（桶数组长度）共同决定，与总元素数量无关
2、同一个桶中的节点有什么相似性？
hash & (table.length - 1) 是相等的- 哈希值可能不同
3、哈希冲突
当不同键的哈希值（或哈希计算结果）映射到同一桶时，即发生哈希冲突。HashMap 通过链表或红黑树解决冲突。
哈希冲突仅要求 hash & (cap - 1) 相同，而非原始哈希值相同。
冲突的节点会被追加到链表中，导致链表长度增加。当链表长度超过阈值（默认 8）且桶数组容量 >=64 时，链表会转为红黑树以优化查询效率。
相关链接
红黑树 | z2huo
Java 中的 transient 关键字 | z2huo
OB links
[[transient 关键字]]
[[红黑树]]
#Java #源码 #未完待续
