【JAVA】HashMap深度剖析：哈希冲突与扩容机制（25）

核心知识点详细解释

Java中HashMap类的工作原理

HashMap 是 Java 集合框架中 Map 接口的一个实现类，它基于哈希表实现，用于存储键值对。其工作原理主要包括以下几个方面：

• 哈希函数：HashMap 使用哈希函数将键的哈希码映射到数组的索引位置。在 Java 中，键对象的 hashCode() 方法会返回一个哈希码，HashMap 会对这个哈希码进行进一步处理，以得到数组的索引。例如：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 数组和链表（或红黑树）：HashMap 内部维护一个数组，数组的每个元素称为一个桶（bucket）。当发生哈希冲突时，即不同的键映射到了同一个桶，HashMap 会使用链表或红黑树来存储这些键值对。在 Java 8 及以后版本中，当链表长度达到一定阈值（默认为 8）且数组长度达到 64 时，链表会转换为红黑树，以提高查找效率。

哈希冲突的解决方法

链地址法

HashMap 使用链地址法来解决哈希冲突。当发生哈希冲突时，新的键值对会被添加到对应桶的链表（或红黑树）中。例如，当插入一个键值对时，如果该键的哈希值对应的桶已经有元素，新的键值对会被插入到链表的头部（在 Java 8 之前）或尾部（在 Java 8 及以后）。

红黑树优化

在 Java 8 及以后版本中，为了提高在哈希冲突较多时的查找效率，当链表长度达到 8 且数组长度达到 64 时，链表会转换为红黑树。红黑树是一种自平衡的二叉搜索树，其查找、插入和删除操作的时间复杂度为 O(log n)，比链表的 O(n) 要快。当树的节点数减少到 6 时，红黑树会转换回链表。

扩容机制的实现细节

扩容条件

当 HashMap 中的元素数量超过负载因子（默认值为 0.75）乘以数组容量时，HashMap 会进行扩容操作。例如，初始数组容量为 16，负载因子为 0.75，当元素数量达到 16 * 0.75 = 12 时，会触发扩容。

扩容过程

扩容时，HashMap 会创建一个新的数组，其容量是原数组的两倍。然后，会将原数组中的所有键值对重新哈希到新数组中。这个过程称为 rehash。以下是 resize 方法的部分源码：

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

实际业务场景中的应用案例

缓存系统

在缓存系统中，HashMap 可以用于存储缓存数据。通过键快速查找对应的值，提高数据的访问速度。例如，在一个简单的用户信息缓存系统中：

import java.util.HashMap;
import java.util.Map;class UserCache {private Map<String, String> cache = new HashMap<>();public void putUser(String userId, String userInfo) {cache.put(userId, userInfo);}public String getUser(String userId) {return cache.get(userId);}
}

统计词频

在文本处理中，HashMap 可以用于统计单词的出现频率。以单词作为键，出现次数作为值，通过 HashMap 可以方便地进行统计。例如：

import java.util.HashMap;
import java.util.Map;public class WordFrequency { public static void main(String[] args) { String text = "hello world hello java"; String[] words = text.split(" "); Map<String, Integer> frequencyMap = new HashMap<>(); for (String word : words) { frequencyMap.put(word, frequencyMap.getOrDefault(word) == null ? 1 : frequencyMap.get(word) + 1); } for (Map.Entry<String, Integer> entry : frequencyMap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } 
}

常见面试问题与解答思路

问题 1：什么是哈希冲突？HashMap 是如何解决哈希冲突的？

解答思路：哈希冲突是指不同的键通过哈希函数计算得到了相同的哈希值，从而映射到了数组的同一个索引位置。HashMap 使用链地址法解决哈希冲突，当发生冲突时，新的键值对会被添加到对应桶的链表（或红黑树）中。在 Java 8 及以后版本中，当链表长度达到 8 且数组长度达到 64 时，链表会转换为红黑树，以提高查找效率。

问题 2：HashMap 的扩容机制是怎样的？

解答思路：当 HashMap 中的元素数量超过负载因子乘以数组容量时，会触发扩容。扩容时，会创建一个新的数组，其容量是原数组的两倍，然后将原数组中的所有键值对重新哈希到新数组中。

问题 3：HashMap 在多线程环境下是否线程安全？如果不是，如何保证线程安全？

解答思路：HashMap 在多线程环境下不是线程安全的。在多线程环境下，可能会出现数据不一致、死循环等问题。可以使用 ConcurrentHashMap 来保证线程安全，ConcurrentHashMap 是线程安全的哈希表实现，它采用分段锁或 CAS 操作来保证并发访问的安全性。

相关技术点的性能优化建议

合理设置初始容量和负载因子

在创建 HashMap 时，可以根据实际情况合理设置初始容量和负载因子。如果初始容量设置过小，会导致频繁扩容，影响性能；如果设置过大，会浪费内存。负载因子默认值为 0.75，一般情况下不需要修改，但在某些特殊场景下，可以根据实际情况进行调整。例如：

import java.util.HashMap;
import java.util.Map;public class HashMapInitialization { public static void main(String[] args) { Map<String, String> map = new HashMap<>(16, 0.75f); } 
}

重写键对象的 hashCode() 和 equals() 方法

为了保证 HashMap 的性能，键对象应该重写 hashCode() 和 equals() 方法。hashCode() 方法用于计算键的哈希码，equals() 方法用于比较两个键是否相等。如果不重写这两个方法，可能会导致哈希冲突增加，影响查找效率。例如：

import java.util.HashMap;
import java.util.Map;class Person { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public int hashCode() { return name.hashCode() + age; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null || getClass() != obj.getClass()) return false; Person person = (Person) obj; return age == person.age && name.equals(person.name); } 
}public class Main { public static void main(String[] args) { Map<Person, String> map = new HashMap<>(); Person person = new Person("John", 25); map.put(person, "Info"); } 
}

避免在多线程环境下使用 HashMap

如果需要在多线程环境下使用哈希表，建议使用 ConcurrentHashMap 而不是 HashMap，以避免线程安全问题。

思考题

1. 如果键对象的 hashCode() 方法总是返回相同的值，会对 HashMap 产生什么影响？
2. 如何手动触发 HashMap 的扩容操作？
3. 在 Java 8 中，HashMap 链表转换为红黑树的阈值为什么是 8？