简体中文HashMap的源码分析
HashMap基于散列表，散列表中每一个Node节点（桶）是链表，当两个条目（entry）的key的hash值对桶数（capacity）取模的值相等时，这两个entry会存储在同一个链表中。但当链表中元素达到一定数目时，链表结构会转变为树结构。
本文从初始化，扩容，插入，获取，删除这几个方面深入讨论了HashMap的实现细节。
此文中没有讨论
HashMap中涉及到树结构的源码。
基础字段 #
HashMap中定义了如下字段：
1// 默认初始容量为16
2static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
3//最大容量为2^30
4static final int MAXIMUM_CAPACITY = 1 << 30;
5//默认装载因子 0.75
6static final float DEFAULT_LOAD_FACTOR = 0.75f;
7//“树化”临界值，当链表数组中的条目数>=8时转变为树结构
8static final int TREEIFY_THRESHOLD = 8;
9//
10static final int UNTREEIFY_THRESHOLD = 6;
11//
12static final int MIN_TREEIFY_CAPACITY = 64;
13//hashmap存放键值对的容器，Node[]数组的大小就是hashmap的容量大小
14transient Node<K,V>[] table;
15//键值对集
16transient Set<Map.Entry<K,V>> entrySet;
17//键值对数目
18transient int size;
19//hashmap发生结构变化的计数器
20transient int modCount;
21//扩容临界键值对数临界值，当size>threshold时扩容
22int threshold;
23//装载因子，初始化时不指定默认为0.75
24final float loadFactor;
初始化 #
构造器 #
HashMap提供了以下几个构造器
1public HashMap(int initialCapacity, float loadFactor){
2 if (initialCapacity < 0)
3 throw new IllegalArgumentException(
4 "Illegal initial capacity: " + initialCapacity);
5 if (initialCapacity > MAXIMUM_CAPACITY)
6 initialCapacity = MAXIMUM_CAPACITY;
7 if (loadFactor <= 0 || Float.isNaN(loadFactor))
8 throw new IllegalArgumentException(
9 "Illegal load factor: " + loadFactor);
10 // 字段初始化
11 this.loadFactor = loadFactor;
12 this.threshold = tableSizeFor(initialCapacity);
13}
14
15// 获取table size容量的方法，结果总是为2的幂
16static final int tableSizeFor(int cap) {
17 int n = cap - 1;
18 n |= n >>> 1;
19 n |= n >>> 2;
20 n |= n >>> 4;
21 n |= n >>> 8;
22 n |= n >>> 16;
23 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
24 }
25
26public HashMap(int initialCapacity) {
27 this(initialCapacity, DEFAULT_LOAD_FACTOR);
28}
29
30public HashMap() {
31 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
32}
33
34public HashMap(Map<? extends K, ? extends V> m) {
35 this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
36 putMapEntries(m, false);
37}
38
39// 使用已有Map初始化
40final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
41 int s = m.size();
42 if (s > 0) {
43 if (table == null) { // pre-size
44 // 若无键值对在HashMap中，此处的计算出table size
45 float ft = ((float)s / loadFactor) + 1.0F;
46 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
47 (int)ft : MAXIMUM_CAPACITY);
48 if (t > threshold)
49 threshold = tableSizeFor(t);
50 }
51 //若参数集过大，先对原集合扩容
52 else if (s > threshold)
53 resize();
54 // 将参数集中的键值对填入新的HashMap中
55 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
56 K key = e.getKey();
57 V value = e.getValue();
58 putVal(hash(key), key, value, false, evict);
59 }
60 }
61 }
可以看到，除了最后一个构造器额外调用了putVal()方法外，构造器都只做了一些字段初始化工作，那么HashMap的键值对是如何“放入”的呢？
插入键值对 #
键值对的插入与扩容密不可分，接下来从这两个方法来阐述HashMap的键值对插入过程
当使用put(K,V)向映射中插入键值对时，实际上调用的是putVal()方法
1public V put(K key, V value) {
2 return putVal(hash(key), key, value, false, true);
3}
4
5/**
6 * Implements Map.put and related methods. 向HashMap中插入元素
7 *
8 * @param hash key的hash值
9 * @param key
10 * @param value
11 * @param onlyIfAbsent 若真，那么不修改原键的值（若原键值不为null）
12 * @param evict if false, the table is in creation mode.
13 * @return 之前键映射的值，若之前键不存在则返回null
14 */
15final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
16 // HashMap的数据拷贝一份先
17 Node<K,V>[] tab; Node<K,V> p; int n, i;
18
19 if ((tab = table) == null || (n = tab.length) == 0)
20 /*
21 * 若是第一次插入，则执行此操作
22 * 此操作调用了resize方法，实际上做的是初始化table的操作
23 */
24 n = (tab = resize()).length;
25 if ((p = tab[i = (n - 1) & hash]) == null)
26 // (n-1) & hash == hash % n, 用于计算key-value放在哪个桶中
27 // 若桶中尚未有内容，则新建一节点 插入新值
28 // 良好的散列表应该走这里
29 tab[i] = newNode(hash, key, value, null);
30 else {
31 // 若桶中有内容
32 Node<K,V> e; K k;
33 if (p.hash == hash &&
34 ((k = p.key) == key || (key != null && key.equals(k))))
35 // 并且第一个节点和新节点的key值一样（更新值）
36 // 更新已经存在的k-v值，在桶中直接命中
37 e = p;
38 else if (p instanceof TreeNode)
39 // 如果已经树化，使用树化后的相关方法
40 // 不好
41 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
42 else {
43 // 开始找在桶中的位置
44 for (int binCount = 0; ; ++binCount) {
45 if ((e = p.next) == null) {
46 // 桶中只有一个元素，但是key没命中，说明这个桶要来新客人了
47 // 向桶中插入新值
48 //遍历桶中的节点，若至链尾，则在链尾加入节点
49 p.next = newNode(hash, key, value, null);
50 //同时判断此时链表中的node数，若 > 8，则由链表转化为二叉树
51 // binCount = 7时说明链表中已经有8个节点了，此时节点数已经 >8个了
52 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
53 //树化
54 // sad
55 treeifyBin(tab, hash);
56 break;
57 }
58 if (e.hash == hash &&
59 ((k = e.key) == key || (key != null && key.equals(k))))
60 // 命中，跳出 更新已有k-v对
61 //同理，key已存在，跳出for循环
62 break;
63 // 将p顺延
64 p = e;
65 }
66 }
67 if (e != null) { // existing mapping for key
68 V oldValue = e.value;
69 // 满足条件会更新
70 if (!onlyIfAbsent || oldValue == null)
71 e.value = value;
72 // LinkedHashMap中用到
73 afterNodeAccess(e);
74 return oldValue;
75 }
76 }
77
78 ++modCount;
79 // 扩容判断
80 if (++size > threshold)
81 resize();
82 // LinkedHashMap中用到
83 afterNodeInsertion(evict);
84 //key不存在，插入新key，返回null
85 return null;
86}
综上， 插入键值对的流程可以概括为：
flowchart TD
a([putVal]) --> b{"bucket is empty?"} --> |Yes| c(Insert new k-v)
c --> m(afterNodeInsertion)-->z([return])
b --> |No|d{bucket.hash = k.hash?} --> |Yes|o(update exist k-v)
o --> y(afterNodeAccess) --> z
d --> |No|e{treeified?}
e -->|No|g[search buckets] -->| for cycle| g
e --> |Yes| f(putTreeNode)-->y
g --> h{bucket.k = k} --> |Yes|o
h --> |No| j[add new k-v in bucket] --> k{bucket elements > 8?}
k --> |Yes| l(Trrify)-->o
k --> |No| o
扩容 #
由putVal()方法可知，resize()方法在初始化过程中也发挥了作用。
1/**
2 * 初始化或扩容table
3 *
4 * @return the table
5 */
6final Node<K,V>[] resize() {
7 /*
8 * 初始化时，table == null， threshold=0或2^n，视构造器而定
9 */
10 Node<K,V>[] oldTab = table;
11 int oldCap = (oldTab == null) ? 0 : oldTab.length;
12 int oldThr = threshold;
13 int newCap, newThr = 0;
14 if (oldCap > 0) {
15 if (oldCap >= MAXIMUM_CAPACITY) {
16 threshold = Integer.MAX_VALUE;
17 return oldTab;
18 }
19 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
20 oldCap >= DEFAULT_INITIAL_CAPACITY)
21 newThr = oldThr << 1; // double threshold
22 }
23 else if (oldThr > 0)
24 // 有参构造使用传入值的2^n作为table size
25 newCap = oldThr;
26 else {
27 // 无参构造器初始化使用默认值作为table size
28 newCap = DEFAULT_INITIAL_CAPACITY;
29 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
30 }
31 if (newThr == 0) {
32 float ft = (float)newCap * loadFactor;
33 //若table size > 2^30则使threshold为最大整数，扩容不再发生
34 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
35 (int)ft : Integer.MAX_VALUE);
36 }
37 threshold = newThr;
38 //以下是扩容之后的内容拷贝
39 @SuppressWarnings({"rawtypes","unchecked"})
40 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
41 table = newTab;
42 if (oldTab != null) {
43 for (int j = 0; j < oldCap; ++j) {
44 Node<K,V> e;
45 if ((e = oldTab[j]) != null) {
46 oldTab[j] = null;
47 if (e.next == null)
48 //桶中只有一个元素，重新计算key值在桶中的位置
49 newTab[e.hash & (newCap - 1)] = e;
50 else if (e instanceof TreeNode)
51 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
52 else { // preserve order
53 //桶中有多个元素
54 //那么将桶中的元素分裂到2个链表里面去，然后分别放入新table
55 //比如原桶数是4，新桶数即为8，原3号桶中有3，7，11，15四个hash
56 //那么3&4和11&4为0，放在新桶的3号桶；7&4和15&4不为0，放在新桶的7号桶
57 //元素在新桶中保持原顺序不变，3的下一节点hash由7变成11
58 Node<K,V> loHead = null, loTail = null;
59 Node<K,V> hiHead = null, hiTail = null;
60 Node<K,V> next;
61 do {
62 next = e.next;
63 // 此处的逻辑比较晦涩，需仔细推敲
64 if ((e.hash & oldCap) == 0) {
65 /*
66 * 此处的逻辑为：
67 * 第一次循环将loTail和loHead均初始化为e
68 * 第二次将loTail.next改为满足条件
69 * ((e.hash & oldCap) == 0)的e的更新值
70 * 这一过程将跳过中间不满足条件的节点
71 * 由于loHead和loTail都是指向e的引用，loHead.next随之而变
72 * 接下来将loTail指向e的更新值
73 * 如此往复，loHead-loTail形成一个新链
74 */
75 if (loTail == null)
76 loHead = e;
77 else
78 loTail.next = e;
79 loTail = e;
80 }
81 else {
82 if (hiTail == null)
83 hiHead = e;
84 else
85 hiTail.next = e;
86 hiTail = e;
87 }
88 } while ((e = next) != null);
89 if (loTail != null) {
90 // 去尾
91 // 有可能loTail还有子节点，而子节点不应该出现在当前链中
92 loTail.next = null;
93 newTab[j] = loHead;
94 }
95 if (hiTail != null) {
96 hiTail.next = null;
97 newTab[j + oldCap] = hiHead;
98 }
99 }
100 }
101 }
102 }
103 return newTab;
104}
上述resize()方法的结论可以通过以下代码验证
1public class NodeTest<K, V> {
2
3 final Node<K, V>[] table = new Node[4];
4 final Node<K, V>[] newtab = new Node[8];
5
6 // 构造代码块，构造NodeTest实例时执行
7 {
8 Node node = new Node(5, "five", null);
9
10 Node node1 = new Node(3, "four", null);
11 Node node2 = new Node(7, "three", node1);
12 Node node3 = new Node(11, "two", node2);
13 Node node4 = new Node(15, "one", node3);
14 Node node5 = new Node(17, "six", node4);
15 Node node6 = new Node(21, "seven", node5);
16
17 Node node7 = new Node(22, "eight", null);
18 Node node8 = new Node(23, "nine", null);
19
20 table[0] = node;
21 table[1] = node7;
22 table[2] = node6;
23 table[3] = node8;
24 }
25
26 public static void main(String[] args) {
27
28 NodeTest<Integer, String> nt = new NodeTest<>();
29
30 // 看看HashMap源码的resize方法的复制部分究竟搞什么飞机
31 nt.resize(nt.table, nt.newtab);
32 // 看看此时的newtab
33 nt.printTable(nt.newtab);
34
35 }
36
37 public void printTable(Node<K, V>[] newtab) {
38 Node<K, V> g, h;
39 for (int i = 0; i < newtab.length; i++) {
40 if ((g = newtab[i]) != null) {
41 if (g.next == null) {
42 System.out.println("newtab[" + i + "]"
43 + g.getKey() + ", " + g.getValue());
44 } else {
45 do {
46 h = g.next;
47 System.out.println("newtab[" + i + "]"
48 + g.getKey() + ", " + g.getValue());
49 } while ((g = h) != null);
50 }
51 }
52 }
53 }
54
55 public void resize(Node<K, V>[] table, Node<K, V>[] newtab) {
56 int oldcap = table.length;
57 for (int j = 0; j < oldcap; ++j) {
58 Node<K, V> e;
59 if ((e = table[j]) != null) {
60 table[j] = null;
61 if (e.next == null) {
62 newtab[j] = e;
63 } else { // preserve order
64 Node<K, V> loHead = null, loTail = null;
65 Node<K, V> hiHead = null, hiTail = null;
66 Node<K, V> next;
67 do {
68 next = e.next;
69 if ((e.key.hashCode() & oldcap) == 0) {
70 if (loTail == null) {
71 loHead = e;
72 } else {
73 loTail.next = e;
74 }
75 loTail = e;
76 } else {
77 if (hiTail == null) {
78 hiHead = e;
79 } else {
80 hiTail.next = e;
81 }
82 hiTail = e;
83 }
84 } while ((e = next) != null);
85
86 if (loTail != null) {
87 loTail.next = null;
88 newtab[j] = loHead;
89 }
90 if (hiTail != null) {
91 hiTail.next = null;
92 newtab[j + oldcap] = hiHead;
93 }
94 }
95 }
96 }
97 }
98
99 static class Node<K, V> implements Map.Entry<K, V> {
100
101 K key;
102 V value;
103 Node<K, V> next;
104
105 public Node(K key, V value, Node<K, V> next) {
106 this.key = key;
107 this.value = value;
108 this.next = next;
109 }
110
111 @Override
112
113 public K getKey() {
114 return key;
115 }
116
117 @Override
118 public V getValue() {
119 return value;
120 }
121
122 @Override
123 public V setValue(V value) {
124 return null;
125 }
126 }
127}
128/*
129newtab[0]5, five
130newtab[1]22, eight
131newtab[2]17, six
132newtab[2]11, two
133newtab[2]3, four
134newtab[3]23, nine
135newtab[6]21, seven
136newtab[6]15, one
137newtab[6]7, three
138*///:~
从输出可以看到，原table[2]的节点被拆分后分别放在newtab[2]和newtab[6]的桶里，并且节点的顺序没有变化
获取键值对 #
一般使用get(K key)方法获取映射中指定键的值，get方法相较putVal()要简单许多
public V get(Object key)
1public V get(Object key) {
2 Node<K,V> e;
3 //有key则返回对应value，否则返回null
4 return (e = getNode(hash(key), key)) == null ? null : e.value;
5}
6
7final Node<K,V> getNode(int hash, Object key) {
8 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
9 // 直接通过hash找到key值存放的桶
10 if ((tab = table) != null && (n = tab.length) > 0 &&
11 (first = tab[(n - 1) & hash]) != null) {
12 if (first.hash == hash && // always check first node
13 // 先从第一个节点查看，如key相等则返回此节点
14 // 积极处理，好的散列桶中只有一个元素
15 ((k = first.key) == key || (key != null && key.equals(k))))
16 return first;
17 if ((e = first.next) != null) {
18 // 否则查找链表中的其他节点
19 if (first instanceof TreeNode)
20 // 若已经树化
21 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
22 do {
23 if (e.hash == hash &&
24 // 遍历寻找
25 ((k = e.key) == key || (key != null && key.equals(k))))
26 return e;
27 } while ((e = e.next) != null);
28 }
29 }
30 return null;
31}
另外判断一个映射中是否存在某个键对应的值对应的方法
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
实际上也是调用的上面提到的getNode()方法
删除键值对 #
使用remove(K key)删除映射中的键值对
1public V remove(Object key) {
2 Node<K,V> e;
3 //返回null或对应key的value
4 return (e = removeNode(hash(key), key, null, false, true)) == null ?
5 null : e.value;
6}
7
8/**
9 * Implements Map.remove and related methods.
10 *
11 * @param hash hash for key
12 * @param key the key
13 * @param value the value to match if matchValue, else ignored
14 * @param matchValue if true only remove if value is equal
15 * @param movable if false do not move other nodes while removing
16 * @return the node, or null if none
17 */
18final Node<K,V> removeNode(int hash, Object key, Object value,
19 boolean matchValue, boolean movable) {
20 Node<K,V>[] tab; Node<K,V> p; int n, index;
21 // 直接定位存放键值对的桶
22 if ((tab = table) != null && (n = tab.length) > 0 &&
23 (p = tab[index = (n - 1) & hash]) != null) {
24 Node<K,V> node = null, e; K k; V v;
25 if (p.hash == hash &&
26 ((k = p.key) == key || (key != null && key.equals(k))))
27 // 若第一个节点就是，那就是它了
28 node = p;
29 else if ((e = p.next) != null) {
30 if (p instanceof TreeNode)
31 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
32 else {
33 // 遍历链表定位key
34 do {
35 if (e.hash == hash &&
36 ((k = e.key) == key ||
37 (key != null && key.equals(k)))) {
38 node = e;
39 break;
40 }
41 p = e;
42 } while ((e = e.next) != null);
43 }
44 }
45 // 调整链表
46 if (node != null && (!matchValue || (v = node.value) == value ||
47 (value != null && value.equals(v)))) {
48 if (node instanceof TreeNode)
49 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
50 else if (node == p)
51 // 第一个节点
52 tab[index] = node.next;
53 else
54 // 非第一个节点
55 // else语句快的do循环保证了p一定是node的前一个节点
56 p.next = node.next;
57 ++modCount;
58 --size;
59 // LinkedHashMap用到
60 afterNodeRemoval(node);
61 return node;
62 }
63 }
64 return null;
65}
