HashMap 源码详解

Java 基础
Word count: 3.7k   |   Reading time≈ 16 min

本文所有内容基于Jdk1.8版本

HashMap 最早出现在JDK 1.2中，底层基于散列算法实现。HashMap 允许 null 键和 null 值, null 键只允许存在一个，在计算键的哈希值时，null 键的哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。

HashMap 数据结构分析

在 Jdk1.8 版本中 HashMap 最大的一个变化就是将数据结构变成了 数组 + 链表 + 红黑树，这样做的目的是为了保证 HashMap 的查询性能，在 hash 冲突严重的情况下，将链表结构转换为红黑树结构。

  • 数组：Node<K,V>[] table是一个类型为Node<K,V> 结构的数组，数组中的每一个节点称为 bin，也叫做桶
  • 链表：Node<K,V> 结构的链表，链表并不需要连续的内存空间，每个链表的 next 指向下一个链表
  • 红黑树：TreeNode<K,V>结构的红黑树

HashMap 数据结构图如下所示:

image-20200615230214687

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
// 默认初始化容量16，初始化容量必须是2的次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转换为红黑树，节点的长度必须大于等于8
static final int TREEIFY_THRESHOLD = 8;

// 红黑树退化为链表，节点的长度小于等于6
static final int UNTREEIFY_THRESHOLD = 6;

// 链表转换为红黑树，table数组的长度必须大于64
static final int MIN_TREEIFY_CAPACITY = 64;

// HashMap 中存储的 key-value 数量
transient int size;

// 修改次数，如果 hashmap 遍历过程中发生修改操作，会触发 fast-fail
transient int modCount;

// 下一次扩容阈值 
int threshold;

// 负载因子
final float loadFactor;

HashMap 为啥容量都是2的次幂

容量是2的幂时，tab[i = (n - 1) & hash]) 确定位置时碰撞概率会比较低，因为容量为 2 的幂时，减 1 之后的二进制数为全1，这样与运算的结果就等于 hasｈ值后面与 1 进行与运算的几位。

下面是个例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(99)  = 0110 0011‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0011
# 计算得到位置是 3
hash HEX(101)  = 0110 0101‬
n-1  HEX(15)   = 0000 1111
--------------------------
         结果   = 0000 0101
# 计算得到位置是 5

如果是其他的容量值，假设是9，进行与运算结果碰撞的概率就比较大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
hash HEX(97)  = 0110 0001‬
n-1  HEX(09)  = 0000 1001
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1

hash HEX(99)  = 0110 0011‬
n-1  HEX(09)  = 0000 1001
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1

hash HEX(101)  = 0110 0101‬
n-1  HEX(09)   = 0000 1001
--------------------------
         结果   = 0000 0001
# 计算得到位置是 1

另外，每次都是 2 的幂也可以让 HashMap 扩容时可以方便的重新计算位置。

1
2
3
4
5
6
7
8
9
10
11
hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
    
hash HEX(97)  = 0110 0001‬
n-1  HEX(31)  = 0001 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1

HashMap put 方法详解

将指定的值与此map中指定键相关联。如果map已经包含了key的映射，则旧的值将会被替换

put 方法的大致思路是这样的：

  • 根据 key 找到 map 中的映射（如果存在返回Node，如果不存在创建新的Node）
  • 替换映射中原有的旧值，并将旧值返回

put方法图解

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
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

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为空,调用 resize() 方法初始化
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
    
	// 计算 hash 值所在桶的位置，如果为空，执行 newNode() 方法
	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 {
            // 链表结构
			// 遍历链表，索引从0开始
			for (int binCount = 0; ; ++binCount) {
				// p.next == null, 已经到达链表尾部，尾插法添加新 Node
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表的长度大于等于8，调用 treeifyBin() 方法
                        // 链表长度大于等于8只是转换为红黑树条件之一
                        // 就还需要 table 大小 >64
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		// e不为空，表示map 中存在key的映射，则替换旧的 value 并直接返回
		if (e != null) { // existing mapping for key
			// 去除当前节点的值,赋值给 oldValue
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	// put 过程中创建新的 Node，那么modCount 和 size 都加1
	++modCount;
	if (++size > threshold)
        // 达到扩容阈值，执行 resize() 方法扩容
		resize();
	afterNodeInsertion(evict);
	return null;
}

HashMap get 方法详解

如果map映射中包含key的映射并且符合如下查询条件 (key==null ? k==null : key.equals(k))},那么该方法返回key对应的value结果；或者返回值为null。

返回值为null并不表示map中不包含关于key的映射，也有可能value本身就是null

get 方法本身思路非常简单：

  • 第一步：根据 key 算出的 hash 值确定 key 在 HashMap 中的位置
  • 第二步：如果 HashMap 中存在 key 的映射，返回 value 结果，否则返回 null

image-20200617141956896

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
public V get(Object key) {
	Node<K,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	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))))
            // 1、桶的首节点就是想要的结果直接返回
			return first;
        
		if ((e = first.next) != null) {
            
			if (first instanceof TreeNode)
                // 2、红黑树结构，调用 getTreeNode() 方法查询 Node
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            
			do {
                // 2、链表结构，遍历链表中查询 Node
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

HashMap remove 方法详解

移除map中关于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
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
public V remove(Object key) {
	Node<K,V> e;
	// 移除map中关于key的映射并返回key关联的value
	return (e = removeNode(hash(key), key, null, false, true)) == null ?
		null : e.value;
}

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;
    
	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;

		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
            // 1、如果桶的首节点就是想要的结果
			node = p;
		else if ((e = p.next) != null) {
			if (p instanceof TreeNode)
                // 2、红黑树结构，调用 getTreeNode() 方法查询 Node
				node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
			else {
				do {
                    // 2、链表结构，遍历链表中查询 Node
					if (e.hash == hash &&
						((k = e.key) == key ||
						 (key != null && key.equals(k)))) {
						node = e;
						break;
					}
					p = e;
				} while ((e = e.next) != null);
			}
		}
        // 获取到 key 映射的 node 节点
		if (node != null && (!matchValue || (v = node.value) == value ||
							 (value != null && value.equals(v)))) {
			if (node instanceof TreeNode)
                // 红黑树类型，调用 removeTreeNode() 移除 node节点
				((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
			else if (node == p)
                // 如果node是首节点，从table数组中移除该节点
				tab[index] = node.next;
			else
                // 将p的下一个Node指向修改为node的下一个Node
				p.next = node.next;
            
            // 
			++modCount;
			--size;
			afterNodeRemoval(node);
			return node;
		}
	}
	return null;
}

HashMap hash 方法详解

hash 方法作用是算出 key 的 hash 值，是整个 HashMap 的灵魂，下面就带大家深入了解hash方法的思想

hash 方法要求结果尽量的减少碰撞，并且要保证计算的速度、效率和质量，减小计算散列函数给系统带来的损耗，下面看看具体的执行过程：

1
2
3
4
5
6
7
8
static final int hash(Object key) {
	int h;
    // 计算key的hash值，将hash值右移16位后与hash值做异或运算
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 确定 hash 结果在 table 中的位置
tab[i = (n - 1) & hash])

这里可能会有同学对 hash ^ (hash >>> 16) 有疑惑，很好奇为什么这里要拿 hash 值异或上 hash 值无符号右移 16 位呢？下面通过一个例子演示其中道理所在。

假设 hash 值是 0001 0100 1100 0010 0110 0001‬ 0010 0000，当前容量是 16。

1
2
3
4
5
6
7
8
9
hash        = 0001 0100 1100 0010 0110 0001‬ 0010 0000  ---
                                                         | 与或计算
hash >>> 16 = 0000 0000 0000 0000 0001 0100 1100 0010  ---
------------------------------------------------------ 
hash 结果    = 0001 0100 1100 0010 0111 0101 1110 0100 ---
                                                         | & 与运算
容量 -1      = 0000 0000 0000 0000 0000 0000 0000 1111 ---
------------------------------------------------------
# 得到位置    = 0000 0000 0000 0000 0000 0000 0000 0100 得到位置是 4

如果又新增一个数据，得到 hash 值是 0100 0000 1110 0010 1010 0010‬ 0001 0000 ，容量还是16，计算它的位置应该是什么呢？

1
2
3
4
5
6
7
8
9
hash        = 0100 0000 1110 0010 1010 0010‬ 0001 0000  ---
                                                         | 与或计算
hash >>> 16 = 0000 0000 0000 0000 0001 0100 1100 0010  ---
------------------------------------------------------ 
hash 结果    = 0100 0000 1110 0010 1011 0110 1101 0010 ---
                                                         | & 与运算
容量 -1      = 0000 0000 0000 0000 0000 0000 0000 1111 ---
------------------------------------------------------
# 得到位置    = 0000 0000 0000 0000 0000 0000 0000 0010 得到位置是 2

上面两个例子，得到位置一个是 4，一个是 2，上面只是我随便输入的两个二进制数，那么这两个数如果不经过 hash ^ (hash >>> 16) 运算，位置会有什么变化呢？

1
2
3
4
5
6
7
8
9
10
hash        = 0001 0100 1100 0010 0110 0001‬ 0010 0000
容量 -1      = 0000 0000 0000 0000 0000 0000 0000 1111
------------------------------------------------------
        结果 = 0000 0000 0000 0000 0000 0000 0000 0000
# 得到位置是 0 
hash        = 0100 0000 1110 0010 1010 0010‬ 0001 0000
容量 -1      = 0000 0000 0000 0000 0000 0000 0000 1111
------------------------------------------------------
        结果 = 0000 0000 0000 0000 0000 0000 0000 0000
# 得到位置是 0

可以发现位置都是 0 ，冲突概率提高了。可见 hash ^ (hash >>> 16) 让数据的 hash 值的高 16 位与低 16 位进行与或混合，可以减少低位相同时数据插入冲突的概率。

HashMap resize 方法详解

resize 方法核心就是 HashMap 扩容机制，主要解决以下问题：

初始化table数组或者扩容至当前table数组的两倍

如果table数组为空，则按照初始容量分配table数组的大小

否则，因为我们使用2的次幂扩容方式，保证每个bin中的元素必须保持在同一索引中，或者以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
final HashMap.Node<K,V>[] resize() {
  // 保存 table 副本，接下来 copy 到新数组用
  HashMap.Node<K,V>[] oldTab = table;
  // 当前 table 的容量，是 length 而不是 size
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  // 当前桶大小
  int oldThr = threshold;

  int newCap, newThr = 0;
  if (oldCap > 0) { 
    //如果当前容量大于 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; // double threshold
  }
  else if (oldThr > 0) 
    // 初始化的场景（给定默认容量），比如 new HashMap(32)
    newCap = oldThr; //将容量设置为 threshold 的值
  else {               // 无参数初始化场景，new HashMap()
    // 容量设置为 DEFAULT_INITIAL_CAPACITY
    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"})
  HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      HashMap.Node<K,V> e;
      //遍历 获得得到元素 赋给 e
      if ((e = oldTab[j]) != null) { //如果当前桶不为空
        oldTab[j] = null; // 置空回收
        if (e.next == null) 
          // 节点 next为空的话 最正常的节点，不是桶内链表，也不是红黑树，
          // 这样的节点会重新计算索引位置，然后插入
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof HashMap.TreeNode) //如果是树节点
          // 原理就是将红黑树拆分成两个 TreeNode 链表，
          // 然后判断每个链表的长度是否小于等于 6，
          // 如果是就将 TreeNode 转换成桶内链表，否则再转换成红黑树
          ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else {
          // 桶内链表，则将链表拷贝到新数组，保证链表的顺序不变
          HashMap.Node<K,V> loHead = null, loTail = null;
          HashMap.Node<K,V> hiHead = null, hiTail = null;
          HashMap.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;
}

扩容时候怎么重新确定元素在数组中的位置，我们看到是由 if ((e.hash & oldCap) == 0) 确定的。

1
2
3
4
5
6
7
8
9
10
11
hash HEX(97)  = 0110 0001‬
n    HEX(16)  = 0001 0000
--------------------------
         结果  = 0000 0000
# e.hash & oldCap = 0 计算得到位置还是扩容前位置
    
hash HEX(17)  = 0001 0001‬
n    HEX(16)  = 0001 0000
--------------------------
         结果  = 0001 0000
#  e.hash & oldCap != 0 计算得到位置是 扩容前位置+扩容容量

通过上面的分析也可以看出，只有在每次容量都是2的次方的情况下才能使用 if ((e.hash & oldCap) == 0) 判断扩容后的位置。

面试问题：

  1. 什么情况下会扩容，扩容的规则是什么？
  2. 插入键值对的时候如何确定索引，HashMap可不是按顺序插入的，那样不就真成了数组了吗。
  3. 如何确保 key 的唯一性？
  4. 发生哈希碰撞怎么处理？
  5. 拉链法是什么？
  6. 单桶内的链表如何转变成红黑树？
  7. 扩容后原来元素位置如何变化

参考资料：

最通俗易懂的 HashMap 源码分析解读

HashMap 源码详细分析(JDK1.8)

7000 字说清楚 HashMap，面试点都在里面了

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

请我喝杯咖啡吧~

支付宝
微信