晦涩难懂的hashmap源代码-put方法解析

在我的分类专栏’hash’中，有关于位运算、hash计算、红黑树的文章，
如果这些还不太了解，可以去看看： hash。

jdk版本：jdk1.8.0_171。

hashmap是用于key-value键值对处理的数据类型。

底层数组

hashmap底层是一个数组，
数组的特点是随机访问的效率高。

hashmap通过散列函数将key转换为索引，即数组下标，
来确定元素在数组中的存放位置。

hash冲突

散列函数计算得到的hash值，可能会存在重复的情况，
这个时候该怎么办呢？

链表节点

什么是链表节点？就是下图这样子：

hashmap是一个数组，数组中存放的是链表节点node，也叫桶即bucket。

put的时候，
会对key进行hash计算得到一个index，再根据index确定数组中的位置，
如果位置上已经有了元素，即hash冲突的时候，
就插入到该链表尾部节点的next引用上。

红黑树

如果在某个位置上的链表的长度超过了7，
会转换为红黑树。

太长会影响查询效率。

计算数组下标

如何根据key计算数组下标？

1、
得到扰动后的key的hashcode，h：
(h = key.hashCode()) ^ (h >>> 16);
将hashcode与hashcode>>>16进行异或运算，
hashcode>>>16是为了将高低位的特征混合，实现更均匀的散列，减少碰撞的几率。

/**
 * 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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2、
取模：
i = (n - 1) & hash
n是hashmap底层数组的长度，hash是上一步得到的h，
((n - 1) & hash) = (hash % (n - 1))，前提需要n=2的x次方，
用位移运算是因为效率更高，
这也是为什么hashmap的容量必须得是2的幂。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

1
2
3
4
5

put源代码

都在注释里。

put

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with key, or
 *         null if there was no mapping for key.
 *         (A null return can also indicate that the map
 *         previously associated null with key.)
 */
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

返回null或被覆盖的value

/**
 * 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
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	// table如果为null、为空，则调用resize()扩容，这个table就是hashmap的底层数组。
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	// 根据key计算得到的数组下标位置上没有元素，通过newNode创建一个Node放在这个位置上。
	// hash是(h = key.hashCode()) ^ (h >>> 16)扰动后的hashcode，(n - 1) & hash]是取模。
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	// 下标上存在元素
	else {
		// e：旧元素
		Node<K,V> e; K k;
		// 旧元素hash等于新元素hash，且旧key等于新key。
		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);
					// 链表长度超过了7，转换为红黑树。
					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;
			}
		}
		// map中key重复
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			// onlyIfAbsent传进来的是false，意思是允许覆盖旧值或旧值为null。
			if (!onlyIfAbsent || oldValue == null)
				// 覆盖旧元素
				e.value = value;
			// hashmap的实现这一步什么都没有做
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	// 是否要扩容
	if (++size > threshold) // threshold = 数组长度 * 负载因子（0.75）
		resize();
	// hashmap的实现，这一步什么都没有做。
	afterNodeInsertion(evict);
	return null;
}

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

顺便提一下，
rehash就是重新计算map中的index下标。

Refs：
冰棍hfv：我用两万字详细总结HashMap(JDK1.8)底层原理
Code_BinBin：JDK1.8HashMap底层实现原理
码农小白猿：通俗易懂Hashmap源码解析