HashMap 底层原理浅析

发表于 阅读次数： 评论数： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

HashMap 底层源码

Put 方法的具体实现

在 HashMap 中，put 方法的具体实现流程和底层源码如下：

jdk-hashmap-put-function

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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
	HashMap.Node<K, V>[] tab;
	HashMap.Node<K, V> p;
	int n, i;
	// 1.如果table为空或者长度为0，即没有元素，那么使用resize()方法扩容
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	// 2.计算插入存储的数组索引i，此处计算方法同 1.7 中的indexFor()方法
	// 如果数组为空，即不存在Hash冲突，则直接插入数组
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
		// 3.插入时，如果发生Hash冲突，则依次往下判断
	else {
		HashMap.Node<K, V> e;
		K k;
		// a.判断table[i]的元素的key是否与需要插入的key一样，若相同则直接用新的value覆盖掉旧的value
		// 判断原则equals() - 所以需要当key的对象重写该方法
		if (p.hash == hash &&
				((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
			// b.继续判断：需要插入的数据结构是红黑树还是链表
			// 如果是红黑树，则直接在树中插入 or 更新键值对
		else if (p instanceof HashMap.TreeNode)
			e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
			// 如果是链表，则在链表中插入 or 更新键值对
		else {
			// i .遍历table[i]，判断key是否已存在：采用equals对比当前遍历结点的key与需要插入数据的key
			//    如果存在相同的，则直接覆盖
			// ii.遍历完毕后任务发现上述情况，则直接在链表尾部插入数据
			//    插入完成后判断链表长度是否 > 8：若是，则把链表转换成红黑树
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					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;
			}
		}
		// 对于i 情况的后续操作：发现key已存在，直接用新value覆盖旧value&返回旧value
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	// 插入成功后，判断实际存在的键值对数量size > 最大容量
	// 如果大于则进行扩容
	if (++size > threshold)
		resize();
	// 插入成功时会调用的方法（默认实现为空）
	afterNodeInsertion(evict);
	return null;
}

扩容操作的具体实现

在 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
/**
 * 该方法有两种使用情况：1.初始化哈希表；2.当前数组容量过小，需要扩容
 */
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) {
		// 针对情况2：若扩容前的数组容量超过最大值，则不再扩容
		if (oldCap >= MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		// 针对情况2：若没有超过最大值，就扩容为原来的2倍（左移1位）
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				oldCap >= DEFAULT_INITIAL_CAPACITY)
			newThr = oldThr << 1; // double threshold
	}

	// 针对情况1：初始化哈希表（采用指定或者使用默认值的方式）
	else if (oldThr > 0) // initial capacity was placed in threshold
		newCap = oldThr;
	else {               // zero initial threshold signifies using defaults
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}

	// 计算新的resize上限
	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) {
		// 把每一个bucket都移动到新的bucket中去
		for (int j = 0; j < oldCap; ++j) {
			Node<K, V> e;
			if ((e = oldTab[j]) != null) {
				oldTab[j] = null;
				if (e.next == null)
					newTab[e.hash & (newCap - 1)] = e;
				else if (e instanceof TreeNode)
					((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
				else { // preserve order
					Node<K, V> loHead = null, loTail = null;
					Node<K, V> hiHead = null, hiTail = null;
					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;
}

HashMap 底层原理

HashMap 的底层数据结构

JDK 1.7 中的实现

在 JDK 1.7 中，HashMap 采用数组 + 链表作为底层的数据结构，其中使用链表是为了解决哈希冲突。当发生哈希冲突时，即多个键被映射到了同一个哈希桶（数组的位置），HashMap 会将这些键值对存储在同一个哈希桶对应的链表中。具体来说，在 JDK 1.7 中，HashMap 的每个哈希桶（数组的位置）实际上是一个链表，每个链表存储了哈希值相同的键值对。当执行 Put 操作时，HashMap 首先会计算键的哈希值，然后确定该键应该存储在数组的哪个位置。如果该位置已经存在了链表，HashMap 就会遍历该链表，检查是否已经存在相同键的键值对。如果存在相同的键，则 HashMap 会更新相应的值；如果不存在相同的键，则 HashMap 会将新的键值对添加到链表的末尾。链地址法的优点是它能够处理哈希冲突，并且在一定程度上保持了 HashMap 的性能。然而，在负载因子较高的情况下，即链表较长的情况下，查询键值对的效率可能会降低，因为需要遍历链表来找到目标键值对。

JDK 1.8 中的实现

在 JDK 1.8 之后，HashMap 采用数组 + 链表 + 红黑树作为底层的数据结构，之所以引入红黑树来替代链表，是为了改善在负载因子较高时的性能，这种结构称为 “链表与红黑树混合实现”。当哈希冲突发生时，如果链表的长度超过一定阈值（默认为 8），HashMap 会将链表转换为红黑树。这样做的目的是为了在链表长度较长时提高查询、修改和删除操作的效率，因为红黑树的时间复杂度更稳定，为 O (log n)。而当链表长度较短时，仍然保持使用链表结构，因为在较短的链表中，链表的遍历效率更高。值得一提的是，当红黑树中元素个数小于一定数量时，会转换回原来的链表结构，JDK 设置这个默认数量为 6 个。

JDK 11+ 中的实现

在 JDK 11、JDK 17 等高版本的 JDK 中，HashMap 的实现仍然基于数组 + 链表 + 红黑树混合实现（如下图所示）。因此，处理哈希冲突的方式与 JDK 1.8 中相似，只是可能会对一些细节进行了优化或改进，比如会引入树化优化、移位优化等。比如树化优化指的是在进行树化操作时，会先判断当前链表长度是否大于等于 8，如果不是，则不会进行树化操作，以节省资源。这个优化主要是为了解决在一些场景下，链表长度虽然超过了阈值，但树化操作并不能带来性能提升的问题。

　提示

无论在哪个版本的 JDK 里面，HashMap 使用的链表都是单向链表。

HashMap 的特点如何实现

HashMap 是一种可以快速存储和快速存储的键值对容器，那么 JDK 是如何实现 HashMap 的快速存储和快速查找呢？

三种常见的数据结构

这里首先从数组、链表、二叉查找树这三种常见的数据结构说起。

数组

数组是连续的内存空间，利用二分查找法，数组的时间复杂度最低可以低到 O (1)，可见数组的查询效率是非常高的。但是由于数组的内存必须是连续的，空间复杂度很高，所以数组的插入、删除效率都非常低。

链表

链表的内存空间比较分散，空间复杂度较低，执行插入和删除操作的效率较高。但是由于链表的内存空间过于分散，导致查询效率大大降低。

二叉查找树

二叉查找树的别名是二叉搜索树，或者叫二叉排序树，在查询效率上和排序后数组的二分查找法效率完全相同，从根节点开始到下面的分支节点，左边的节点永远比父节点的要小，右边的节点永远比父节点大，如下图所示：

上图中一共 12 个元素，如果按顺序查找，可能最多需要查找 12 次才能查到目标元素；但是通过使用二叉查找树后，查找 43 这个元素，只需要判断 4 次就可以。由此可以看出二叉查找树在查询效率上和排序后的数组二分查找法效率是一样的。但是由于二叉树的元素过于分散，导致空间复杂度过大，执行插入和删除操作时会非常低效。为了解决这个问题，JDK 使用了红黑树这种数据结构，而红黑树在时间复杂度上可以做到 O (log n) 的高效率。

HashMap 实现快速存储

快速存储是链表和红黑树的优势。HashMap 中数组的索引是通过哈希值（hashCode）与其右移 16 位后的结果进行异或运算，然后按位与运算（取模）来获得的，底层源码如下：

1
2
3
4
5
static final int hash(Object key) {
    int h;
    // 调用 key.hashCode() 生成初步哈希值，然后对哈希值进行扰动处理
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
// 使用按位与运算替代取模运算（这样更高效），n 是 HashMap 底层数组的长度（总是 2 的幂），hash 是经过扰动处理后的哈希值
int index = (n - 1) & hash

通过这样的计算可以保证数组索引的分散。但是分散并不代表不会出现相同的索引，也就是索引冲突（哈希冲突）。在遇到哈希冲突的时候，HashMap 会在该索引的位置生成一个单向链表，将元素放置到尾部。虽然链表这种数据结构的插入效率比较高，但是在查询上效率却非常低，所以 HashMap 在链表元素数量大于 8 的时候，会自动将链表转成红黑树，以达到查询高效，插入也高效的目的。当然，在红黑树中元素个数小于一定数量时，会转换回原来的链表结构，JDK 设置这个默认数量为 6 个。这样不管是在外围 “数组” 上，还是在 “链表” 上，以及转换成 “红黑树” 这种数据结构，HashMap 都能做到快速存储。

总结

HashMap 底层的数组在查找效率上绝对有保证。当发生哈希冲突时，会使用链表存储冲突的元素，元素数量仅仅只有 8 个的链表，查询效率不需要考虑。大于 8 个元素后，链表会转换成红黑树，而红黑树的查询效率与数组相当，这点也不需要质疑。综合考虑，当发生哈希冲突时，HashMap 在查询方面也做到了快速查找的特性。

HashMap 什么时候会扩容

HashMap 在内部会维护一个负载因子（Load Factor），默认的负载因子是 0.75，也就是当 HashMap 中的元素数量达到容量的 75% 时，会触发扩容操作。扩容操作会创建一个新的更大的数组，通常是 当前容量的两倍，然后将原有的元素重新散列到新的数组中。这个过程需要重新计算每个元素的哈希值，并将其放置到新的数组中。由于这个过程涉及到重新哈希，可能会导致元素的重新排列，因此在扩容过程中，HashMap 的性能可能会受到影响。

提示

HashMap 的默认初始容量是 16，最大容量为 2^30，每次扩容后的容量都是之前容量的两倍。

HashMap 底层的哈希算法

在 HashMap 中，哈希算法的核心是调用对象（键对象）的 hashCode() 方法生成一个初步的哈希值，然后通过一系列处理（扰动处理）使这个哈希值分布得更加均匀，以减少哈希冲突。下面是 Java 8 中 HashMap 底层源码中用于计算哈希值的代码：

1
2
3
4
5
static final int hash(Object key) {
    int h;
    // 调用 key.hashCode() 生成初步哈希值，然后进行扰动处理
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • key.hashCode()：调用键对象的 hashCode() 方法，生成初步的哈希值 h。
  • h >>> 16：将初步哈希值 h 向右无符号移动 16 位，目的是为了引入哈希值的高位信息。
  • h ^ (h >>> 16)：将初步哈希值 h 和其右移 16 位后的结果进行异或操作。这样做是为了混合哈希值的高位和低位，以生成一个更加随机和均匀分布的哈希值。

上述步骤生成的哈希值，将用于确定键在 HashMap 中存储的位置，即哈希桶的位置（数组的位置）。具体位置的计算方式如下：

1
2
// 使用按位与运算替代取模运算，这样更高效
int index = (n - 1) & hash

其中，n 是 HashMap 底层数组的长度（总是 2 的幂），hash 是经过扰动处理后的哈希值。(n - 1) & hash 通过按位与运算将哈希值限制在数组的索引范围内。

总结

HashMap 底层的哈希算法通过键对象的 hashCode() 方法生成初步哈希值，并通过扰动处理（即将哈希值与其右移 16 位后的结果进行异或运算）使哈希值分布更加均匀，从而有效减少哈希冲突，提升整体性能。这是 HashMap 在 Java 中实现高效键值对存储和检索的关键机制。

HashTable 底层原理

HashTable 如何实现线程安全

HashTable 使用同步方法来保证线程安全，也就是所有关键操作方法（如 get()、put()、remove() 等）都使用了 synchronized 关键字进行同步，确保同一时刻只有一个线程可以执行这些方法，这也就保证了线程安全。

ConcurrentHashMap 底层原理

为什么需要 ConcurrentHashMap

思考

为什么已经有 HashTable 了，JDK 还会提供 ConcurrentHashMap 这个线程安全的类呢？

首先 HashTable 本身是个容器，这也就说明了 HashTable 本身可以不断的变大，试想一下，HashTable 如果本身存储 1000 个元素，那么在调用 get() 方法时，就会将这 1000 个元素完全锁住，期间其他任何线程都得等待。这样就会造成容器越大，对容器数据操作的效率就越低。为了解决这个问题，JDK 提供了 ConcurrentHashMap 类，其实 ConcurrentHashMap 的底层也是通过 synchronized 关键字来实现线程安全的，不同于 HashTable 的是 ConcurrentHashMap 在线程同步上更加细分化，它不会像 HashTable 那样一次性将所有数据都锁住，而是采用 “分段锁” 思想。

ConcurrentHashMap 如何实现线程安全

思考

这里需要知道，ConcurrentHashMap 底层数据结构的实现其实和 HashMap 没有多大区别，都是数组 + 链表 + 红黑树。那怎么将 HashMap 的数据结构使用分段锁的思想使其在线程同步上更加细分化呢？

JDK 1.7 中的实现

在 JDK 1.7 及以前，是这样实现的。比如容器 HashMap 中存在 1000 个元素，各个元素都放置到 HashMap 数组的链表或者红黑树中，最后得到的数组大小可能只有 128。ConcurrentHashMap 会根据这 128 个数组元素对其分段，比如以 16 个数组元素为一段，可以分为 8 段。在实际获取和添加元素时，首先会根据哈希算法计算得到元素的索引，然后找到该元素所处的段位，然后只将该段位锁住，并不影响其他段位的数据操作。这样，如果按照 HashTable 的效率为基本单位来计算，ConcurrentHashMap 在 JDK 1.7 及以前的效率会提高 8 倍，当然数据量越大，提高的效率将越多。

JDK 1.8 中的实现

在 JDK 1.8 及以后，ConcurrentHashMap 依旧使用分段锁的思想来实现线程安全，但不同于 JDK 1.7 及以前的实现，JDK 1.8 将锁的粒度更加细分化，以每个数组索引为锁来进行实现。比如 HashMap 中数组的长度为 128，那么就会存在 128 个锁将每个数组元素锁住，这样在并发效率上有了很大的提升。