0%

Java 集合框架 - HashMap 分析

1.HashMap实现原理

简述HashMap的工作原理:

HashMap是基于散列法(又称哈希法)的原理,使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。使用HashMap进行查询和修改的速度都很快,平均时间复杂度O(1)。HashMap非线程安全,如果需要考虑并发,则需要使用ConcurrentHashMap,且HashMap不保证存储元素的序列;


2.HashMap的底层结构

JDK18之前:数组+链表

JDK1.8之后:数组+链表+红黑树

特点是HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体。只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树!

在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。

数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。


3.源码阅读

3.1.HashMap的继承与实现

  • HashMap实现了Cloneable,可以被克隆。
  • HashMap实现了Serializable,可以被序列化。
  • HashMap继承自AbstractMap,实现了Map接口,具有Map的所有功能。
1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}

具体继承如下所示:

HashMap.png

3.2.HashMap的基本属性及内部类

3.2.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
/**
* 哈希数组初始容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* 哈希数组最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* HashMap默认装载因子(负载因子)
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 当前 HashMap 所能容纳键值对数量的最大值,超过这个值,则需扩容
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 哈希槽(链)上的红黑树上的元素数量减少到此值时,将红黑树转换为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 当桶的个数达到64的时候才进行树化
* 即是说当桶数组容量小于该值时,优先进行扩容,而不是树化
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* 哈希数组
*/
transient Node<K,V>[] table;

/**
* entry集合
*/
transient Set<Map.Entry<K,V>> entrySet;

/**
* HashMap的元素数量
*/
transient int size;

/**
* HashMap结构的修改次数
*/
transient int modCount;

/**
* (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.)
* HashMap扩容阈值,并没有默认阈值,原因是阈值可由容量乘上负载因子计算而来(注释中有说明)
* 计算公式:threshold = capacity * loadFactor
*/
int threshold;

/**
* HashMap当前使用的装载因子
*/
final float loadFactor;

上面举例了一些HashMap的属性字段,比较有意思的是羡慕几个属性字段,在接下来中会单拎出来进行详细讲解。:

  • 哈希数组的初始容量:DEFAULT_INITIAL_CAPACITY
  • 负载因子:loadFactor
  • 链表树化与树化链表的两个阈值:UNTREEIFY_THRESHOLD 和TREEIFY_THRESHOLD

3.2.2 Node内部类

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

HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体。只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树!

3.2.3 TreeNode内部类

TreeNode是一个典型的树型节点,其中,prev是链表中的节点,用于在删除元素的时候可以快速找到它的前置节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 位于HashMap中
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;
}

// 位于LinkedHashMap中,典型的双向链表节点
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);
}
}

3.3.HashMap的四种构造及参数分析

  1. 无参构造,初始化一个哈希数组容量为16,装载因子为0.75的HashMap
1
2
3
4
5
6
7
/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
  1. 初始化一个哈希数组容量为initialCapacity,装载因子为0.75的HashMap
1
2
3
4
5
6
7
8
9
10
/**
* Constructs an empty {@code HashMap} with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
  1. 初始化一个哈希数组容量为initialCapacity,装载因子为loadFactor的HashMap
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
/**
* Constructs an empty {@code HashMap} with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}
  1. 使用指定的HashMap中的元素来初始化一个新的HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Constructs a new {@code HashMap} with the same mappings as the
* specified {@code Map}. The {@code HashMap} is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified {@code Map}.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将指定HashMap中的元素存入到当前HashMap(允许覆盖)
putMapEntries(m, false);
}

我们这这里对几个字段进行解释一下:

3.4.查询

3.4.1.查询HashMap大小

该方法返回HashMap的大小,键值对的数目:

1
2
3
public int size() {
return size;
}

3.4.2 查询HashMap是否为空

1
2
3
public boolean isEmpty() {
return size == 0;
}

3.4.3.查询HashMap是否存在指定key

1
2
3
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}

3.4.4.查询HashMap中是否存在指定value的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
// 进行循环遍历查找value
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;
}

3.5.取值

1
2
3
4
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

它调用了getNode(int hash, Object key)方法,详细代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果桶的数量大于0,并且所查找的key所在的桶的第一个元素不为空
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.6.添加

3.6.1.HashMap的添加过程

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

实际上它调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法,详细代码如下所示:

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
/*
* 向当前Map中存入新的元素,并返回旧元素
*
* hash key的哈希值
* onlyIfAbsent 是否需要维持原状(不覆盖旧值)
* evict 如果为false,则表处于创建模式。
*
* 返回同位元素的旧值(在当前Map中占据相同位置的元素)
* 如果不存在同位元素,即插入了新元素,则返回null
* 如果存在同位元素,但同位元素的旧值为null,那么也返回null
*
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果桶的长度为0,未初始化,则进行初始化并得到长度n
if ((tab = table) == null || (n = tab.length) == 0)
// 调用resize进行初始化
n = (tab = resize()).length;
// 如果桶中还没有元素,则将要插入的key和value放到第一位
// 使用(n - 1) & hash 计算元素在哪个桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 桶中此时已存在元素
Node<K,V> e; K k;
// 如果待插入的元素的hash值和key值与第一个元素的哈希值和key相同,保存到e用于后续修改value值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 如果桶的第一个元素为树节点,则调用树节点的putTreeVal方法插入元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历这个桶对应的链表,binCount用于存储链表中元素的个数
for (int binCount = 0; ; ++binCount) {
// 遍历整个链表,没有相同哈希值和key的元素,则在链表最后插入该key和value结点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果插入结点之后的长度大于等于8,则树化
// 这里-1的解释为:因为第一个元素没有加到binCount中,所以这里-1
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 进行树化
treeifyBin(tab, hash);
break;
}
// 假如待插入的key在链表中找到,则退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到了对应key的元素
if (e != null) { // existing mapping for key
V oldValue = e.value; // 记录旧值
// 判断是否需要替换旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value; // 替换旧值为新值
// 在节点被访问后做点什么事,在LinkedHashMap中用到
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 到了此处证明没有找到元素,即添加了新元素,修改次数加1
++modCount;
// 如果哈希数组的容量已超过阈值,则需要对哈希数组扩容
if (++size > threshold)
resize();
// 在节点插入后做点什么事,在LinkedHashMap中用到
afterNodeInsertion(evict);
return null;
}

添加方法除了可以单个key-value键值对的添加,还可以将指定HashMap中的元素存入到当前HashMap中(允许覆盖),详细代码如下:

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
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 如果当前HashMap的哈希数组还未初始化
if (table == null) { // pre-size
// 根据HashMap中的元素数量反推哈希数组的最低容量要求
float ft = ((float)s / loadFactor) + 1.0F; // 注意这里!!!!
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果大于需要扩容的阈值,则重新计算扩容阈值
if (t > threshold)
threshold = tableSizeFor(t);
} else {
// Because of linked-list bucket constraints, we cannot
// expand all at once, but can reduce total resize
// effort by repeated doubling now vs later
// 由于链表存储桶的限制,我们无法一次全部扩展
// 但可以通过立即加倍与以后加倍来减少总的调整工作量
// 初始化哈希数组,或者对哈希数组扩容,并返回新的哈希数组
while (s > 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);
}
}
}

3.6.2.HashMap的扩容过程

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
/*
* 扩容机制:在初始化时、对哈希数组扩容时两种情况下调用
*
*/
final Node<K,V>[] resize() {
// 旧数组
Node<K,V>[] oldTab = table;
// 旧容量,或者未初始化时的容量
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;
}
// 如果旧容量的两倍(左移一位)小于最大容量,并且大于默认初始容量(16)
// 则新容量扩大为旧容量的两倍,扩容阈值也扩大为旧阈值的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果哈希数组还未初始化(首次进来)并且实例化HashMap的时候指定了初始容量
else if (oldThr > 0) // initial capacity was placed in threshold
// 则将哈希数组的当前容量初始化为与旧阈值一样大(传入初始容量时候会调用tableSizeFor()方法)
newCap = oldThr;
// 如果哈希数组还未初始化(首次进来)并且实例化HashMap的时候没有指定了初始容量
else { // zero initial threshold signifies using defaults
// 则使用默认的初始容量(16)和默认公式计算的阈值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新扩容阈值为0,则使用公式计算得到新的扩容阈值,并且不可超过最大容量
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;
// 如果桶中的第一个元素不为空,则赋值给e
if ((e = oldTab[j]) != null) {
// 清空旧桶,帮助GC
oldTab[j] = null;
// 如果桶中只有一个元素,进行新桶的位置定位,并搬迁
// 注意:只有第一个元素才可以这样,因为每次扩容都是两倍
// 则第一个元素搬移到新桶的时候肯定还没有元素
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果该哈希槽上链接了不止一个元素,且该元素是TreeNode类型
else if (e instanceof TreeNode)
// 如果第一个元素是树节点,则把这颗树打散成两颗树插入到新桶中去
// 拆分红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 如果这个链表不止一个元素且不是一颗树
// 则进行分化成两个链表插到新的桶中
// 举例:假如原来容量为4,3、7、11、15这四个元素都在三号桶中
// 现在扩容到8,则3和11还是在三号桶,7和15要搬移到七号桶中去
// 也就是分化成了两个链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// (e.hash & oldCap) == 0的元素放在低位链表中
// 比如,3 & 4 == 0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// (e.hash & oldCap) != 0的元素放在高位链表中
// 比如,7 & 4 != 0
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 遍历完成得到两个链表
// 低位链表在新桶的位置与旧桶一样(即3和11还在三号桶中)
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位链表在新桶中的位置正好是原来的位置加上旧容量(即7和15搬移到七号桶了)
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

3.7.移除

1
2
3
4
5
6
7
8
/**
* 根据传入的key进行数据移除元素,并返回刚刚移除的元素的值
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}

实际上它调用了removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)方法,详细代码如下所示:

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
/*
* 从HashMap中移除指定的元素,并返回刚刚移除的元素(移除失败返回null)
*
* matchValue 移除元素时是否需要考虑value的匹配问题
* movable 移除元素后如果红黑树根结点发生了变化,那么是否需要改变结点在链表上的顺序
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 如果桶的数量大于0(不空)且待删除的元素所在的桶的第一个元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 如果键的值与链表第一个节点相等,则将 node 指向该节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果该Tab的第一个元素是树节点,则以树的方式进行寻找
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);
}
}
// 如果找到了该元素,则进行值比对
// 根据传递进来的matchValue判断是否需要匹配
// 如果不需要匹配直接删除,如果需要匹配看是否与传入的value相等
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);
// 如果待删除的元素是第一个元素,则将第二个元素移到到第一个元素的位置
// 注意:上面的代码可知,node==p的情况只有待删除元素node是第一个结点才会发生
else if (node == p)
tab[index] = node.next;
// 如果待删除的元素不是第一个元素,则将中间结点连接断开(单向链表)
else
p.next = node.next;
// 修改次数+1
++modCount;
// size-1
--size;
// 删除结点之后应处理的事情
afterNodeRemoval(node);
return node;
}
}
return null;
}