logo头像
Snippet 博客主题

深入分析HashMap源码

Map这种Key-Value格式的数据结构在日常开发中是非常的常见,大部分的高级编程语言都有Map类型,Map类型常用于在内存中存取数据。

在Java中,HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文深入探讨JDK1.8的HashMap的结构实现和功能原理。

Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示:

Java中Map继承体系

下面针对各个实现类的特点做一些说明:

  • HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
  • Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁(JDK8还有优化)。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。
  • LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。
  • TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

搞清楚HashMap,首先需要知道HashMap是什么,即它的存储结构-字段;其次弄明白它能干什么,即它的功能实现-方法。众所周知 HashMap 底层是基于数组+链表组成的,下面我们针对这两个方面详细展开讲解。

数据结构

在JDK1.7之前的HashMap的结构中,其实存在一个很明显的缺陷就是:

当 Hash 冲突严重时,在桶上形成的链表会变的越来越长,这样在查询时的效率就会越来越低;时间复杂度为 O(N)

JDK8重点优化了这个查询效率,在原先的数组+链表上再增加红黑树。当链表大小达到一定的阈值(HashMap是8)时,会自动转换为红黑树的数据结构。修改为红黑树之后查询效率即时间复杂度直接提高到了 O(logn)

数据结构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
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
/** 
* 默认位桶数组初始容量,必须是2的幂,这里默认是16
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* 位桶数组大小的最大值。构造参数的大小必须是2的几次幂并且小于等于1<<30
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 默认负载因子是0.75,可以在构造参数里设置
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 一个桶中的bin的存储方式由链表转换为红黑树的阈值,当链表大小超过TREEIFY_THRESHOLD的时候转换为红黑树
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 红黑数转换为链表(收缩机制),当执行resize操作时,桶中bin的数量少于UNTREEIFY_THRESHOLD时6时,此时收
* 缩为普通链表,提高查询效率
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;


/**
* 当桶中bin被树化时最小的hash表容量.(若没有达到这个阈值,即hash表容量小于MIN_TREEIFY_CAPACITY
* 当桶中bin数量太多时会执行resize扩容操作).这个MIN_TREEIFY_CAPACITY的值至少TREEIFY_THRESHOLD
* 的4倍。
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* 位桶数组,即Hash表,其大小总是2的几次幂,JDK1.7类型是Entry<K,V>[],JDK8优化成Node<K,V>[]
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;

/**
* 缓存的entrySet,即键值对映射对象,这里使用了AbstractMap的keyset()和values()
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;

/**
* 当前map中包含的key-value数,即map的大小
* The number of key-value mappings contained in this map.
*/
transient int size;

/**
*
* HashMap的修改次数,在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,
* 比如迭代器迭代时候我们手动删除元素时,modCount会增加这个值。在迭代过程中,判断modCount和
* expectedModCount是否相等,不相等则抛出ConcurrentModificationException异常,这就是所谓的
* Fail-Fast机制。同样,ArrayList,LinkedList也有这个字段。
* 具体详情请参照HashMap源码下的抽象迭代类HashIterator,
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;

/**
* 要根据threshold的阈值来判断map是否要扩容,即threshold = capacity * load factor,
* 第一次扩容为16 * 0.75 = 12 , 当map的数组容量为12的时,此时需要继续扩容。
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

/**
* hash table的默认负载因子,默认是DEFAULT_LOAD_FACTOR,即0.75
* The load factor for the hash table.
* @serial
*/
final float loadFactor;

数据结构

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* 基本的hash桶节点,即数组存放的元素类型,实现了Map.Entry<K,V>接口。
* JDK1.7的结构是Map.Entry<K, V>的子类HashEntry<K, V>
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
// key的哈希值,用来定位数组索引位置
final int hash;
// map的key,不可不变对象,一旦设置新Key,不可更改key的值,HashMap中可存null值
final K key;
// map的value,也可以存放null值。key相同则覆盖value,
V value;
// 链表的下一个node
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;
}
// 获取key
public final K getKey() { return key; }
// 获取value
public final V getValue() { return value; }
// 重写toString
public final String toString() { return key + "=" + value; }

// 重写hashCode,node的hashCode为key的hashCode与value的hashCode的异或结果
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

// 设置新的value,返回旧的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

// 一般重写了hashCode方法,equals也会重写。
public final boolean equals(Object o) {
// 引用都是一个,则判断是同一个对象,直接返回true
if (o == this)
return true;
// 判断是否是Map.Entry同一类型,若类型不同,则返回false
if (o instanceof Map.Entry) {
// 若是 Map.Entry类型,进行向下转型。
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// 如果两个对象的key和value同时都相等,则认为是相等,返回true
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

TreeNode红黑树

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
127
128
129
130
131
132
133
/**
* 红黑树节点,继承LinkedHashMap.Entry<K,V>
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}

/**
* 把红黑树的根节点设为 其所在的数组槽 的第一个元素
* 首先明确:TreeNode既是一个红黑树结构,也是一个双链表结构
* 这个方法里做的事情,就是保证树的根节点一定也要成为链表的首节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) { // 根节点不为空 并且 HashMap的元素数组不为空
int index = (n - 1) & root.hash; // 根据根节点的Hash值 和 HashMap的元素数组长度 取得根节点在数组中的位置
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 首先取得该位置上的第一个节点对象
if (root != first) { // 如果该节点对象 与 根节点对象 不同
Node<K,V> rn; // 定义根节点的后一个节点
tab[index] = root; // 把元素数组index位置的元素替换为根节点对象
TreeNode<K,V> rp = root.prev; // 获取根节点对象的前一个节点
if ((rn = root.next) != null) // 如果后节点不为空
((TreeNode<K,V>)rn).prev = rp; // root后节点的前节点 指向到 root的前节点,相当于把root从链表中摘除
if (rp != null) // 如果root的前节点不为空
rp.next = rn; // root前节点的后节点 指向到 root的后节点
if (first != null) // 如果数组该位置上原来的元素不为空
first.prev = root; // 这个原有的元素的 前节点 指向到 root,相当于root目前位于链表首位
root.next = first; // 原来的第一个节点现在作为root的下一个节点,变成了第二个节点
root.prev = null; // 首节点没有前节点
}

/*
* 这一步是防御性的编程
* 校验TreeNode对象是否满足红黑树和双链表的特性
* 如果这个方法校验不通过:可能是因为用户编程失误,破坏了结构(例如:并发场景下);也可能是TreeNode
* 的实现有问题(这个是理论上的以防万一);
*/
assert checkInvariants(root);
}
}

/**
* 参数为HashMap的元素数组
*/
final void treeify(Node<K,V>[] tab) {
// 定义树的根节点
TreeNode<K,V> root = null;
// 遍历链表,x指向当前节点、next指向下一个节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next; // 下一个节点
x.left = x.right = null; // 设置当前节点的左右节点为空
if (root == null) { // 如果还没有根节点
x.parent = null; // 当前节点的父节点设为空
x.red = false; // 当前节点的红色属性设为false(把当前节点设为黑色)
root = x; // 根节点指向到当前节点
}
else { // 如果已经存在根节点了
K k = x.key; // 取得当前链表节点的key
int h = x.hash; // 取得当前链表节点的hash值
Class<?> kc = null; // 定义key所属的Class
for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历,此遍历没有设置边界,只能从内部跳出
// GOTO1
int dir, ph; // dir 标识方向(左右)、ph标识当前树节点的hash值
K pk = p.key; // 当前树节点的key
if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值
dir = -1; // 标识当前链表节点会放到当前树节点的左侧
else if (ph < h)
dir = 1; // 右侧

/*
* 如果两个节点的key的hash值相等,那么还要通过其他方式再进行比较
* 如果当前链表节点的key实现了comparable接口,并且当前树节点和链表节点是相同Class的实
* 例,那么通过comparable的方式再比较两者。
* 如果还是相等,最后再通过tieBreakOrder比较一次
*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);

TreeNode<K,V> xp = p; // 保存当前树节点

/*
* 如果dir 小于等于0 : 当前链表节点一定放置在当前树节点的左侧,但不一定是该树节点的左孩
* 子,也可能是左孩子的右孩子 或者 更深层次的节点。如果dir 大于0 : 当前链表节点一定放置在
* 当前树节点的右侧,但不一定是该树节点的右孩子,也可能是右孩子的左孩子 或者 更深层次的节
* 点。
*
* 如果当前树节点不是叶子节点,那么最终会以当前树节点的左孩子或者右孩子为起始节点 再从
* GOTO1 处开始 重新寻找自己(当前链表节点)的位置。
* 如果当前树节点就是叶子节点,那么根据dir的值,就可以把当前链表节点挂载到当前树节点的左或
* 者右侧了。
* 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。
*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp; // 当前链表节点 作为 当前树节点的子节点
if (dir <= 0)
xp.left = x; // 作为左孩子
else
xp.right = x; // 作为右孩子
root = balanceInsertion(root, x); // 重新平衡
break;
}
}
}
}

// 把所有的链表节点都遍历完之后,最终构造出来的树可能经历多个平衡操作,根节点目前到底是链表的哪一个节点是不确定的
// 因为我们要基于树来做查找,所以就应该把 tab[N] 得到的对象一定根节点对象,而目前只是链表的第一个节点对象,所以要做相应的处理。
moveRootToFront(tab, root);
}

}

重要方法

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
/**
* 计算key的hash值,
* key为null则hashCode为0;不为null则将key的hashCode赋值给h,最终的hashCode = h ^ (h >>> 16);
* 这里我们要讲讲数组索引的计算方式:(n- 1) & hash,n表示table.length
* 这里通过key.hashCode()计算出key的哈希值,然后将哈希值h右移16位,再与原来的h做异或^运算,这一步是高位运
* 算。设想一下,如果没有高位运算,那么hash值将是一个int型的32位数。而从2的-31次幂到2的31次幂之间,有将近几
* 十亿的空间,如果我们的HashMap的table有这么长,内存早就爆了。所以这个散列值不能直接用来最终的取模运算,而
* 需要先加入高位运算,将高16位和低16位的信息"融合"到一起,也称为"扰动函数"。这样才能保证hash值所有位的数值
* 特征都保存下来而没有遗漏,从而使映射结果尽可能的松散。最后,根据 n-1 做与操作的取模运算。这里也能看出为什么
* HashMap要限制table的长度为2的n次幂,因为这样,n-1可以保证二进制展示形式是(以16为例)0000 0000 0000
* 0000 0000 0000 0000 1111。在做"与"操作时,就等同于截取hash二进制值得后四位数据作为下标。这里也可以看
* 出"扰动函数"的重要性了,如果高位不参与运算,那么高16位的hash特征几乎永远得不到展现,发生hash碰撞的几率就
* 会增大,从而影响性能。
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put方法

1
2
3
4
// 我们实际用的put方法,底层调用的是putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* (onlyIfAbsent为true时,如果key存在,就不会进行put操作,原有的对应的value不会被覆盖)
* @param evict if false, the table is in creation mode.
* (evict参数用于LinkedHashMap中的尾部操作,这里没有实际意义。)
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义变量tab是将要操作的Node数组引用,p表示tab上的某Node节点,n为tab的长度,i为tab的下标。
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断当table为null或者tab的长度为0时,即table尚未初始化,此时通过resize()方法得到初始化的table。
if ((tab = table) == null || (n = tab.length) == 0)
// 这种情况是可能发生的,HashMap的table字段注释中提到:The table, initialized on first use, and resized as necessary。
n = (tab = resize()).length;
// 此处通过(n - 1)& hash计算出的值作为tab的下标i,并另p表示tab[i],也就是该链表第一个节点的位置。并判断p是否为null。
if ((p = tab[i = (n - 1) & hash]) == null)
// 当p为null时,表明tab[i]上没有任何元素,即不存在Hash冲突,那么接下来就new第一个Node节点,调用newNode方法返回新节点赋值给tab[i]。这里值得注意的是i = (n - 1) & hash相当于对hash对n的取模
tab[i] = newNode(hash, key, value, null);
// 下面进入p不为null的情况,有三种情况:p为链表节点;p为红黑树节点;p是链表节点但长度为临界长度TREEIFY_THRESHOLD,再插入任何元素就要变成红黑树了。
else {
// 定义e引用,表示即将插入的Node节点,并且下文可以看出 k = p.key。
Node<K,V> e; K k;
if (p.hash == hash &&
// HashMap中判断key相同的条件是key的hash相同(Hash是否冲突),并且符合equals方法。这里判断了p.key是否和插入的key相等,如果相等,则将p的引用赋给e。e会在最后统一进行赋值及返回。
((k = p.key) == key || (key != null && key.equals(k))))
// 这一步的判断其实是属于一种特殊情况,上述三个条件都满足,即两者hash值相同且key完全相同,于是插入操作就不需要了,只要把原来的value覆盖就可以了。e会在最后统一进行赋值及返回,这里先不进行覆盖操作。
e = p;
else if (p instanceof TreeNode)
// 现在开始了第一种情况,当前桶p是红黑树节点,那么肯定插入后仍然是红黑树节点,就要按照红黑树的方式写入数据。所以我们直接强制转型p后调用TreeNode.putTreeVal方法,返回的引用赋给e。
// 你可能好奇,这里怎么不遍历tree看看有没有key相同的节点呢?其实,putTreeVal内部进行了遍历,存在相同hash时返回被覆盖的TreeNode,否则返回null。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 接下里就是p为链表节点的情形,也就是上述说的另外两类情况:插入后还是链表/插入后转红黑树。另外,上行转型代码也说明了TreeNode是Node的一个子类。
else {
// 我们需要一个计数器来计算当前链表的元素个数,并遍历链表,binCount就是这个计数器。
for (int binCount = 0; ; ++binCount) {
// 遍历过程中当发现p.next为null时,说明链表到头了,就需要将当前的key、value封装成一个新节点,将新的链表节点直接在p的后面插入即可,即把新节点的引用赋给p.next,插入操作就完成了。注意此时e赋给p。
if ((e = p.next) == null) {
// 最后一个参数为新节点的next,这里传入null,保证了新节点继续为该链表的末端。
p.next = newNode(hash, key, value, null);
// 插入成功后,要判断是否需要转换为红黑树,因为插入后链表长度加1,而binCount并不包含新节点,所以判断时要将临界阈值减1。binCount大于等于7(其实实际上链表此时的大小为8)时转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 当满足上述转换条件时,调用treeifyBin方法,将该链表转换为红黑树。
treeifyBin(tab, hash);
// 当然如果不满足转换条件,那么插入数据后结构也无需变动,所有插入操作也到此结束了,break退出即可。
break;
}
// 在遍历链表的过程中,有可能遍历到与插入的key相同的节点,此时只要将这个节点引用赋值给e,最后通过e去把新的value覆盖掉就可以了。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 找到了相同key的节点,那么插入操作也不需要了,直接break退出循环进行最后的value覆盖操作。
break;
// e是当前遍历的节点p的下一个节点,p = e 就是依次遍历链表的核心语句。每次循环时p都是下一个node节点。
p = e;
}
}
// 下面JDK注释已经很清晰了,针对已经存在key的情况做处理。即我们对e进行处理。
if (e != null) { // existing mapping for key
//定义oldValue,即原存在的节点e的value值。
V oldValue = e.value;
// 方法注释提到,onlyIfAbsent为true时,若存在key相同时不做覆盖处理,这里作为判断条件,可以看出当onlyIfAbsent为默认值false或者oldValue为null时,进行覆盖操作。
if (!onlyIfAbsent || oldValue == null)
// 覆盖操作,将原节点e上的value设置为插入的新value。
e.value = value;
// 这个函数在hashmap中没有任何操作,是个空函数,它存在主要是为了linkedHashMap的一些后续处理工作。
afterNodeAccess(e);
// 返回的是被覆盖的oldValue。我们在使用put方法时很少用他的返回值,甚至忘了它的存在,这里我们知道,他返回的是被覆盖的oldValue。
return oldValue;
}
}
// 收尾工作,值得一提的是,对key相同而覆盖oldValue的情况,在前面已经return,不会执行这里,所以那一类情况不算数据结构变化,并不改变modCount值。如果走到这里,说明已经新增一个Key-Value的Node节点,modCount要自增
++modCount;
// 同理,覆盖oldValue时显然没有新元素添加,除此之外都新增了一个元素,这里++size并与threshold判断是否达到了扩容标准。
if (++size > threshold)
// 当HashMap中存在的node节点大于threshold时,hashmap进行扩容。
resize();
// 这里与前面的afterNodeAccess同理,是用于linkedHashMap的尾部操作,HashMap中并无实际意义。
afterNodeInsertion(evict);
// 最终,对于真正进行插入元素(不是覆盖的操作)的情况,put函数一律返回null。
return null;
}

get方法

1
2
3
4
5
6
// 我们实际用的get方法,底层调用的是getNode方法
public V get(Object key) {
Node<K,V> e;
// 根据key及其hash值查询node节点,如果存在,则返回该节点的value值;如果不存在,则返回null。
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none 。
* 如果找到node返回node,没有找到node则返回null
* 根据key搜索节点的方法。记住判断key相等的条件:hash值相同 并且 符合equals方法。
*/
final Node<K,V> getNode(int hash, Object key) {
// 定义变量tab是将要遍历查找的Node数组引用,first和e表示tab上的找到的Node节点,n为tab的长度,k为Key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 根据输入的hash值,可以直接计算出对应的下标(n - 1) & hash,缩小查询范围,如果存在结果,则必定在table的这个位置上。
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))))
// 判断第一个存在的节点的key是否和查询的key相等。如果相等,直接返回该节点。
return first;
// 如果第一个不匹配,则判断它的下一个是红黑树还是链表。遍历该链表/红黑树直到next为null。
if ((e = first.next) != null) {
// 红黑树就按照树的查找方式返回值。
if (first instanceof TreeNode)
// 当这个table节点上存储的是红黑树结构时,在根节点first上调用getTreeNode方法,在内部遍历红黑树节点,查看是否有匹配的TreeNode。
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 链表的方式遍历匹配返回值。
do {
// 当这个table节点上存储的是链表结构时,若两者hash相同且key是否完全相同则直接返回。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
// 如果key不同,一直遍历下去直到链表尽头,直到e.next == null才终止循环。
} while ((e = e.next) != null);
}
}
// 没有找到则返回null。
return null;
}

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
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/**
* map扩容机制
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 当前所有元素所在的数组,称为老的元素数组
Node<K,V>[] oldTab = table;
// 老的元素数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 老的扩容阀值设置
int oldThr = threshold;
// 新数组的容量,新数组的扩容阀值都初始化为0
int newCap, newThr = 0;
// 如果老数组长度大于0,说明已经存在元素
if (oldCap > 0) {
// 超过最大值就不再扩充了,即2的30次方时,就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
// 扩容阀值设置为int最大值(2的31次方 -1 ),因为oldCap再乘2就溢出了。
threshold = Integer.MAX_VALUE;
// 超过了最大的容量,不能扩容,直接返回老的元素数组
return oldTab;
}
/* 没超过最大值,就扩充为原来的2倍
* 如果数组元素个数在正常范围内,那么新的数组容量为老的数组容量的2倍(左移1位相当于乘以2)
* 如果扩容之后的新容量小于最大容量并且老的数组容量大于等于默认初始化容量(16),那么新数组的扩
* 容阀值设置为老阀值的2倍。(老的数组容量大于16意味着:要么构造函数指定了一个大于16的初始化容量值,
* 要么已经经历过了至少一次扩容)
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 运行到这个else if,说明老数组没有任何元素
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果老数组的扩容阀值大于0,那么设置新数组的容量为该阀值,这一步也就意味着构造该map的时候,指定了初始化容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 能运行到这里的话,说明是调用无参构造函数创建的该map,并且第一次添加元素
// 设置新数组容量为16
newCap = DEFAULT_INITIAL_CAPACITY;
// 设置新数组扩容阀值为 16 * 0.75 = 12。0.75为负载因子(当元素个数达到容量了4分之3,那么扩容)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果扩容阀值为0
if (newThr == 0) {
// 计算新的resize上限
float ft = (float)newCap * loadFactor;
// 计算扩容阀值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 设置新数组的扩容阀值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组(对于第一次添加元素,那么这个数组就是第一个数组;对于存在oldTab的时候,那么这个数组就是要需要扩容到的新数组)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将该map的table属性指向到该新数组newTab
table = newTab;
// 如果老数组不为空,说明是扩容操作,那么涉及到元素的转移操作
if (oldTab != null) {
// 遍历老数组把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
// 数组中的某个元素
Node<K,V> e;
// 如果当前位置元素不为空,那么需要转移该元素到新数组
if ((e = oldTab[j]) != null) {
// 释放掉老数组对于要转移走的元素的引用(主要为了使得数组可被回收)
oldTab[j] = null;
// 如果元素没有有下一个节点,说明该元素不存在hash冲突
if (e.next == null)
// 把元素存储到新的数组中,存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值 % 数组长度】 = 【 hash值 & (数组长度-1)】
// 这种与运算求模的方式要求 数组长度必须是2的N次方,但是可以通过构造函数随意指定初始化容量呀,如果指定了17,15这种,岂不是出问题了就?没关系,最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。 15 -> 16、17-> 32
newTab[e.hash & (newCap - 1)] = e;
/*
* 如果该元素有下一个节点,那么说明该位置上存在一个链表了(hash相同的多个元素以链表的方式存
* 储到了老数组的这个位置上了)。例如:数组长度为16,那么hash值为1(1%16=1)的和hash值为
* 17(17%16=1)的两个元素都是会存储在数组的第2个位置上(对应数组下标为1),当数组扩容为
* 32(1%32=1)时,hash值为1的还应该存储在新数组的第二个位置上,但是hash值为17(17%32=1
* 7)的就应该存储在新数组的第18个位置上了。所以,数组扩容后,所有元素都需要重新计算在新数组
* 中的位置。
*/
else if (e instanceof TreeNode)
// 如果该节点为TreeNode类型
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 链表优化重hash的代码块
// 按命名来翻译的话,应该叫低位首尾节点
Node<K,V> loHead = null, loTail = null;
// 按命名来翻译的话,应该叫高位首尾节点
Node<K,V> hiHead = null, hiTail = null;
// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
Node<K,V> next;
// 遍历链表
do {
// next表示下一个node节点
next = e.next;
// 原索引
// 这一步判断好狠,拿元素的hash值和老数组的长度做与运算
// 数组的长度一定是2的N次方(例如16),如果hash值和该长度做与运算,结果为0,就说明该hash值和数组长度取模后的值一定小于数组长度(例如mod值为1)。
// 那么该hash值再和新数组的长度取摸的话mod值也不会放生变化,所以该元素的在新数组的位置和在老数组的位置是相同的,所以该元素可以放置在低位链表中。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 如果没有尾,说明链表为空,链表为空时,头节点指向该元素。
loHead = e;
else
// 如果有尾,那么链表不为空,把该元素挂到链表的最后。
loTail.next = e;
// 把尾节点设置为当前元素。
loTail = e;
}
// 原索引+oldCap
// 如果与运算结果不为0,说明hash值大于老数组长度(例如hash值为17)。
// 此时该元素应该放置到新数组的高位位置上。
// 例:老数组长度16,那么新数组长度为32,hash为17的应该放置在数组的第17个位置上,也就是下标为16,那么下标为16已经属于高位了,低位是[0-15],高位是[16-31]。
else {
if (hiTail == null)
// 如果没有尾,说明链表为空,链表为空时,头节点指向该元素。
hiHead = e;
else
// 如果有尾,那么链表不为空,把该元素挂到链表的最后。
hiTail.next = e;
// 把尾节点设置为当前元素。
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里,即低位的元素组成的链表还是放置在原来的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里,即高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置。
if (hiTail != null) {
hiTail.next = null;
// 例1:hash为17在老数组放置在0下标,在新数组放置在16下标;
// 例2:hash为18在老数组放置在1下标,在新数组放置在17下标。
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新的位桶数组
return newTab;
}

treeifyBin方法

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
/**
* 转换为红黑树的操作
* 参数tab: 元素数组
* 参数hash: key的hashCode
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/*
* 如果元素数组为空或者数组长度小于 树结构化的最小限制
* MIN_TREEIFY_CAPACITY 默认值64,对于这个值可以理解为:
* 如果元素数组长度小于这个值,没有必要去进行结构转换;
* 当一个数组位置上集中了多个键值对,那是因为这些key的hash值和数组长度取模之后结果相同.(并不是因为这些
* key的hash值相同).因为hash值相同的概率不高,所以可以通过扩容的方式,来使得最终这些key的hash值在和新
* 的数组长度取模之后,拆分到多个数组位置上。
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 如果数组为null或者小于MIN_TREEIFY_CAPACITY=64则进行扩容操作
resize();
// 如果元素数组长度已经大于等于了 MIN_TREEIFY_CAPACITY,那么就有必要进行结构转换了。
// 根据hash值和数组长度进行取模运算后,得到链表的首节点。
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;
// 当遍历尾节点为null时候,则结束,否则有节点继续遍历链表
} while ((e = e.next) != null);

// 到目前为止 也只是把Node对象转换成了TreeNode对象,把单向链表转换成了双向链表
// 把转换后的双向链表,替换原来位置上的单向链表
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

tableSizeFor方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 返回大于输入参数且最近的2的整数次幂的数,例如输入14,则返回2的4次幂,即16。
* 如果算出来的n大于等于最大的容量,则取最大的容量。
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

先来分析有关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的整数次幂的值了。

现在回来看看第一条语句:

1
int n = cap - 1;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。

参考文献

支付宝打赏 微信打赏

请作者喝杯咖啡吧