Loading... ## HashMap 底层实现与扩容机制解析 ### 1. HashMap 概述 `HashMap` 是 Java 中非常常用的数据结构,用于存储键值对。它的底层通过**哈希表**(Hash Table)实现,能够在平均情况下提供 **O(1)** 的时间复杂度进行数据的查找、插入和删除操作。在性能和使用上的高效,使得 `HashMap` 在 Java 应用程序中被广泛应用。 本文将从 HashMap 的底层数据结构、Hash 算法、扩容机制等多个方面详细解析其实现原理。 ### 2. HashMap 的底层结构 #### 2.1 数组 + 链表 + 红黑树 `HashMap` 的底层由一个数组(`Node[] table`)构成,数组的每个元素是一个链表(在一定条件下会转化为红黑树)。每个链表上的节点都存储着一个键值对。HashMap 的底层结构可以表示为: - 数组:用于存储多个链表的引用,每个数组槽位对应一个 `bucket`。 - 链表:当多个键值对的哈希值相同时,HashMap 将这些值存储在同一个链表中,形成**哈希冲突**。 - 红黑树:为了优化链表中查找效率,在链表长度超过一定阈值时(默认是 8),链表会转换为红黑树,以提高查找效率。 #### 2.2 `Node` 节点结构 每个 `Node` 节点用来存储键值对,其内部结构如下: ```java static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // 用于链表指向下一个节点 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } ``` 每个 `Node` 节点包含四个主要字段: - **hash**:键的哈希值,用于快速查找节点。 - **key**:键值。 - **value**:键对应的值。 - **next**:指向下一个节点的引用,用于处理哈希冲突时的链表结构。 ### 3. Hash 算法 HashMap 通过键的 `hashCode()` 方法生成哈希值,决定键值对存放在数组中的哪个位置。 ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` #### 3.1 Hash 函数的设计 Hash 函数通过高位和低位的异或操作,将哈希值的高位和低位混合在一起,从而使哈希值更加分布均匀,减少哈希冲突。 - `key.hashCode()`:生成对象的原始哈希值。 - `h ^ (h >>> 16)`:将哈希值的高 16 位与低 16 位进行异或操作,增强分布性。 最终,HashMap 根据数组的长度(`length`)和哈希值,通过 `index = (n - 1) & hash` 计算出数据在数组中的位置。 ### 4. Hash 冲突解决 当多个键的哈希值相同,导致它们被映射到数组中的同一个位置时,会发生哈希冲突。HashMap 采用**链表法**(即拉链法)和**红黑树**来处理这种冲突。 - 当发生冲突时,HashMap 会在数组中对应位置形成链表,将冲突的元素串在一起。 - 当链表长度超过一定阈值(默认为 8)时,链表会转换为红黑树,以提高性能,避免在链表中过长的查找时间。 ### 5. 扩容机制 HashMap 的扩容是为了避免过多的哈希冲突和性能下降。当 HashMap 中的元素数量超过容量的负载因子(`loadFactor`)时,就会触发扩容。默认情况下,HashMap 的初始容量为 16,负载因子为 0.75。 #### 5.1 触发扩容的条件 当 HashMap 中的元素数量超过 `threshold = capacity * loadFactor` 时,HashMap 会进行扩容。默认的 `loadFactor` 是 0.75,即当 HashMap 的填充度超过 75% 时,便会触发扩容。 #### 5.2 扩容过程 扩容过程中,HashMap 会将当前容量扩大为原来的两倍,并将所有现有元素重新散列到新的数组中。具体步骤如下: 1. **扩容**:将 HashMap 的容量扩展为原来的两倍。 2. **重新计算位置**:对所有已有的键值对重新计算哈希值,并根据新的数组大小重新分配它们在数组中的位置。 3. **复制元素**:将原数组中的元素复制到新的数组中。如果链表或红黑树较长,则需要逐个复制,并重新调整链表或红黑树结构。 ```java void resize() { Node<K,V>[] oldTable = table; int oldCap = (oldTable == null) ? 0 : oldTable.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 如果容量已经达到最大值,则不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 否则将容量翻倍 newCap = oldCap << 1; newThr = oldThr << 1; } else { // 如果是空表,则使用默认容量 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 创建新数组并重新分配元素 Node<K,V>[] newTable = (Node<K,V>[])new Node[newCap]; table = newTable; threshold = newThr; for (Node<K,V> e : oldTable) { while (e != null) { Node<K,V> next = e.next; int i = e.hash & (newCap - 1); e.next = newTable[i]; newTable[i] = e; e = next; } } } ``` #### 5.3 扩容对性能的影响 扩容过程中需要重新计算每个元素的哈希值,并将其放置到新数组中,因此扩容是一个相对耗时的操作。在实际开发中,应尽量避免频繁触发扩容,可以通过合理设置初始容量来减少扩容次数。 ### 6. HashMap 的容量与负载因子 - **初始容量**:默认情况下,HashMap 的初始容量为 16,可以通过构造函数指定初始容量。 - **负载因子(loadFactor)**:负载因子是决定何时扩容的关键因素。默认值为 0.75,表示当 HashMap 的填充度超过 75% 时触发扩容。通过调整负载因子,可以在空间和时间之间做出权衡。 ### 7. 线程安全性 `HashMap` 是非线程安全的。如果在多线程环境中使用,可能会导致数据不一致、死循环等问题。因此,在多线程环境中,建议使用 `ConcurrentHashMap`,它是线程安全的版本,并且通过分段锁机制提高了并发性能。 ### 8. 总结 `HashMap` 通过数组、链表、红黑树的组合来实现高效的键值对存储和查找。它使用哈希函数将键映射到数组位置,采用链表和红黑树处理冲突,同时通过动态扩容机制保证性能。了解 `HashMap` 的底层实现,可以帮助我们在实际开发中更好地使用它,避免不必要的性能问题。 在大规模数据处理和多线程场景下,合理配置 `HashMap` 的初始容量、负载因子,并选择适合的线程安全版本(如 `ConcurrentHash Map`),是确保高效运行的关键。 最后修改:2024 年 09 月 18 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏