【JAVA】 HashMap详解

HashMap

HashMap 是 Java 中非常常用的一种数据结构，它实现了 Map 接口，并基于哈希表（hash table）实现。HashMap 允许存储键-值对，并通过键来快速查找对应的值。下面是对 HashMap 的详细介绍：

1. 基本概念

• 键值对 (Key-Value Pair): HashMap 中的每一个元素都是一个键值对。键是唯一的，而值可以重复。通过键可以快速查找和获取对应的值。
• 哈希表 (Hash Table): HashMap 的底层实现是一个哈希表。哈希表通过一个哈希函数将键映射到数组中的一个索引位置，从而实现快速查找。

2. 特性

• 存储顺序: HashMap 不保证元素的存储顺序，也就是说，遍历 HashMap 时，元素的顺序可能与插入顺序不同。如果需要保持顺序，可以使用 LinkedHashMap。
• 线程不安全: HashMap 不是线程安全的。如果在多线程环境中使用，可能需要使用 Collections.synchronizedMap 方法来获取一个线程安全的 Map，或者使用 ConcurrentHashMap。
• 允许空键和空值: HashMap 允许一个空键（null）和多个空值（null）。

3. 工作原理

• 哈希函数 (Hash Function): 当你插入一个键值对时，HashMap 会调用键的 hashCode() 方法来计算键的哈希值，并将这个哈希值用来决定元素在数组中的索引位置。
• 冲突处理 (Collision Handling): 由于不同的键可能会有相同的哈希值（即哈希冲突），HashMap 通过链地址法（separate chaining）来处理冲突。在链地址法中，HashMap 的每个位置实际上是一个链表，所有哈希值相同的键值对都存储在这个链表中。
• 扩容 (Rehashing): 当 HashMap 中的元素数量超过一定阈值（通常是容量的 75%）时，它会自动扩容（将容量扩大为原来的两倍），并重新将所有元素映射到新的哈希表中。这一过程称为 rehashing。

4. 底层结构介绍

HashMap 是 Java 中非常重要的一个数据结构，其底层实现比较复杂，但也非常高效。下面我们深入探讨一下 HashMap 的底层结构和源码实现。

1. 基本结构

HashMap 的核心由一个数组和链表（在 Java 8 及以上版本中，还包含红黑树）构成。

• 数组 (Node<K, V>[] table): HashMap 的底层是一个数组，每个数组元素是一个 Node<K, V> 对象。这个数组称为“桶”（bucket）。
• 链表和红黑树: 在哈希冲突（不同的键计算出的哈希值相同）时，HashMap 会将相同哈希值的键值对存储在链表中。如果链表长度超过一定阈值（默认为 8），链表将转换为红黑树，以提高查找效率。

2. 核心类与字段

2.1 Node<K, V> 类

Node<K, V> 是 HashMap 中存储键值对的基本单元。它是一个静态内部类，定义如下：

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;}// 实现 Map.Entry<K, V> 的方法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;}
}

2.2 重要字段

• Node<K, V>[] table: 存储数据的数组（桶数组），默认大小为 16。
• int size: 当前存储的键值对的数量。
• int threshold: 扩容的阈值，等于 capacity * loadFactor。
• float loadFactor: 负载因子，默认是 0.75。
• int modCount: 结构修改次数的计数器，用于快速失败机制。

3. 核心方法

3.1 put(K key, V value) 方法

插入元素的主要方法 put(K key, V value)：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

put 方法的核心逻辑在 putVal 方法中：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K, V>[] tab; Node<K, V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;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 {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

流程概述：

1. 计算哈希值: 根据键的 hashCode() 计算出哈希值。
2. 确定索引: 使用 (n - 1) & hash 计算键在数组中的索引位置。
3. 插入节点: 如果对应的桶是空的，则直接插入；否则，遍历链表，处理哈希冲突。
4. 链表转红黑树: 如果链表长度超过阈值（默认 8），则将链表转换为红黑树。
5. 扩容: 如果当前元素数量超过阈值，则进行扩容。

3.2 resize() 方法

当 HashMap 中的元素数量超过阈值时，需要进行扩容。resize 方法的作用是将 HashMap 的容量扩大一倍，并重新分配所有的键值对。

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) {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) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = 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"})Node<K, V>[] newTab = (Node<K, V>[])new Node[newCap];table = newTab;if (oldTab != null) {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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;
}

流程概述：

1. 计算新容量和新阈值: 通常情况下，容量加倍，阈值也加倍。
2. 重新分配键值对: 遍历旧数组中的每个元素，并将其重新分配到新数组中。元素的位置可能会移动，但相对顺序保持不变。
3. 链表或红黑树的拆分: 对于链表或红黑树节点，resize 会根据哈希值重新分配这些节点到新的位置。

4. 总结

HashMap 的设计在追求性能和内存使用之间找到了一个很好的平衡。它的哈希算法和扩容机制使得 HashMap 在大多数情况下能够以接近 O(1) 的时间复杂度完成插入、删除和查找操作。在 Java 8 之后，引入了红黑树进一步优化了链表过长的情况，使得最坏情况下的性能得到了很大改善。
了解 HashMap 的底层结构和源码实现，能帮助你更好地理解它的行为特性和性能，以及在实际应用中正确地使用它。

5. 主要方法

• put(K key, V value): 将指定的键值对插入 HashMap。如果键已经存在，新的值会替换旧的值。
• get(Object key): 根据指定的键获取对应的值。如果键不存在，则返回 null。
• remove(Object key): 删除指定键的键值对。
• containsKey(Object key): 判断 HashMap 中是否包含指定的键。
• containsValue(Object value): 判断 HashMap 中是否包含指定的值。
• size(): 返回 HashMap 中的键值对数量。
• keySet(): 返回 HashMap 中所有键的集合。
• values(): 返回 HashMap 中所有值的集合。
• entrySet(): 返回 HashMap 中所有键值对的集合。

6. 使用场景

HashMap 非常适合在需要根据键快速查找、插入或删除元素的场景中使用。常见的使用场景包括缓存实现、计数器、查找表等。

7. 性能

HashMap 的查找、插入和删除操作在平均情况下的时间复杂度为 O(1)。但是，在最坏的情况下（所有键都映射到同一个位置），时间复杂度可能会退化为 O(n)。不过这种情况在实际应用中非常少见。

8. 面试题

1. 问题 1: HashMap 是如何解决哈希冲突的？请解释其工作原理。

答案：
HashMap 通过链地址法（Separate Chaining）来解决哈希冲突。在 HashMap 中，当两个不同的键计算出的哈希值相同时，它们会被映射到数组中的同一个索引位置。此时，HashMap 会将这些键值对以链表的形式存储在同一个桶（bucket）中。
具体步骤如下：

1. 计算哈希值：对于插入的键，首先通过 hashCode() 计算其哈希值，然后通过 (n-1) & hash 计算在数组中的索引。
2. 检查冲突：如果计算出的索引位置已经有元素存在，则发生哈希冲突。
3. 处理冲突：HashMap 会将新插入的键值对以链表节点的形式附加到已有元素之后。如果链表长度超过一定阈值（Java 8 及以上版本默认为 8），链表将转换为红黑树，以提高查找效率。

通过这种方式，HashMap 既能处理哈希冲突，又能保证高效的查找、插入和删除操作。

2. 问题 2: 为什么 HashMap 的数组长度通常是 2 的幂？这样设计的优点是什么？

答案：
HashMap 的数组长度通常设置为 2 的幂（如 16, 32, 64 等），这是为了提高哈希函数的效率和均匀性。
具体优点如下：

1. 快速计算索引：在 HashMap 中，数组索引通过 (n - 1) & hash 计算得出，这种位运算非常高效。假设 n 是 2 的幂，那么 n-1 就是一个低位全为 1 的数（如 15 或 31）。在这种情况下，位与运算 (n-1) & hash 能确保哈希值的低位位参与到索引计算中，减少冲突，保证键值对的均匀分布。
2. 减少空间浪费：将数组长度设置为 2 的幂可以减少空间的浪费。如果长度为任意值而非 2 的幂，可能会导致索引分布不均匀，从而增加哈希冲突的可能性。
3. 简单扩容计算：在扩容时，新的容量通常是原来的两倍，即新的容量依然是 2 的幂。这样，旧的哈希值计算出来的索引要么保持不变，要么变成原索引加上旧容量。这样做简化了扩容时重新分配元素的逻辑。

3. 问题 3: 你如何设计一个高效的缓存系统，使用 HashMap 作为基础数据结构？

答案：
可以使用 HashMap 结合双向链表（Doubly Linked List）来设计一个基于 LRU（Least Recently Used）策略的缓存系统。这种设计既可以提供快速的查找，又能高效地维护元素的访问顺序。
设计思路如下：

1. 数据结构：使用一个 HashMap 存储缓存中的键值对，键是缓存的键，值是链表节点（包含实际数据和指向前后节点的指针）。同时，用一个双向链表来维护元素的访问顺序，其中最近使用的元素放在链表头部，最久未使用的元素放在链表尾部。
2. 操作逻辑：
   • 查找：每次访问某个元素时，首先通过 HashMap 查找该元素。如果存在，将该元素移动到链表头部（表示最近访问）。如果不存在，则返回 null 或加载数据。
   • 插入：插入一个新元素时，首先检查缓存是否已满。如果已满，则删除链表尾部的元素（即最久未使用的元素），并在 HashMap 中移除对应的键。然后将新元素插入 HashMap，并将其放在链表头部。
   • 删除：删除元素时，通过 HashMap 找到对应的链表节点，并将其从链表和 HashMap 中同时删除。
3. 时间复杂度：
   • 查找、插入、删除操作：都可以在 O(1) 时间内完成，这得益于 HashMap 的快速查找能力和双向链表的高效操作。

这种设计可以保证缓存系统既能快速查找数据，又能自动维护缓存的使用顺序，确保最常用的数据保留在缓存中。