一、HashMap 底层实现详解
1. 核心数据结构
HashMap 在 JDK 8 中的底层结构是 数组 + 链表 + 红黑树，其核心成员变量包括：
transient Node<K,V>[] table;：哈希桶数组transient int size;：实际键值对数量int threshold;：扩容阈值（capacity * loadFactor）final float loadFactor;：负载因子（默认 0.75f）
2. 哈希函数与定位原理
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
该哈希函数通过高 16 位与低 16 位异或，减少哈希冲突概率。最终桶位置计算方式为：(n - 1) & hash，其中 n 为数组长度。
3. 扩容机制源码分析
当 size > threshold 时触发扩容，每次扩容为原容量的 2 倍：
final Node<K,V>[] resize() {
// ... 省略部分代码
newCap = oldCap << 1; // 容量翻倍
// ...
// 重新计算哈希位置
for (int j = 0; j < oldTab.length; ++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 { // 链表拆分逻辑
// ...
}
}
}
return newTab;
}
4. 链表转红黑树条件
当链表长度达到 8 且数组长度超过 64 时，链表转换为红黑树：
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
二、LinkedHashMap 源码级解析
1. 双向链表结构
通过继承 HashMap.Node 实现双向链表：
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
2. 访问顺序实现
构造函数中 accessOrder 参数控制访问顺序：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
每次访问元素后，通过 afterNodeAccess 方法将节点移至链表尾部：
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
三、TreeMap 红黑树实现原理
1. 红黑树特性
TreeMap 基于红黑树实现，每个节点包含 5 个属性：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
// ...
}
2. 插入平衡过程
插入新节点后通过 fixAfterInsertion 方法维持红黑树平衡：
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
// 情况1：父节点和叔节点均为红色
// ...
} else {
if (x == rightOf(parentOf(x))) {
// 情况2：父节点为红色，叔节点为黑色，且当前节点为右子节点
// ...
}
// 情况3：父节点为红色，叔节点为黑色，且当前节点为左子节点
// ...
}
} else {
// 镜像情况
// ...
}
}
root.color = BLACK;
}
3. 范围查询实现
TreeMap 支持高效的范围查询，例如：
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
底层通过红黑树的有序性快速定位边界节点。
四、ConcurrentHashMap 并发控制演进
1. JDK 7 分段锁机制
JDK 7 采用分段锁（Segment）设计，每个 Segment 继承 ReentrantLock：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
// ...
}
默认 16 个 Segment，最多支持 16 个线程并发写。
2. JDK 8 CAS + synchronized
JDK 8 放弃分段锁，采用 CAS + synchronized 实现更细粒度的锁：
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // 初始化表，使用 CAS
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, // CAS 插入新节点
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { // 对单个桶加锁
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
// ...
}
}
else if (f instanceof TreeBin) {
// ...
}
}
}
// ...
}
}
addCount(1L, binCount);
return null;
}
3. 读操作无锁设计
读操作通过 volatile 关键字保证可见性，无需加锁：
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
五、性能对比与调优建议
1. 插入性能对比测试
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class MapPerformanceTest {
private static final int SIZE = 1000000;
public static void main(String[] args) {
testInsert(new HashMap<>());
testInsert(new LinkedHashMap<>());
testInsert(new TreeMap<>());
testInsert(new ConcurrentHashMap<>());
}
private static void testInsert(Map<Integer, Integer> map) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < SIZE; i++) {
map.put(i, i);
}
long endTime = System.currentTimeMillis();
System.out.println(map.getClass().getSimpleName() + " 插入 " + SIZE + " 元素耗时: " + (endTime - startTime) + "ms");
}
}
典型测试结果（单位：ms）：
| Map 类型 | 插入 100 万元素 |
|---|---|
| HashMap | 250 |
| LinkedHashMap | 320 |
| TreeMap | 850 |
| ConcurrentHashMap | 420 |
2. 遍历性能对比
private static void testTraversal(Map<Integer, Integer> map) {
// 预热
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// 空循环
}
long startTime = System.currentTimeMillis();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// 空循环
}
long endTime = System.currentTimeMillis();
System.out.println(map.getClass().getSimpleName() + " 遍历耗时: " + (endTime - startTime) + "ms");
}
3. 调优建议
- HashMap：预估元素数量，避免频繁扩容
// 示例：预估存储1000个元素，初始容量设为1000/0.75≈1334 Map<String, Integer> map = new HashMap<>(1334); - TreeMap：大量插入操作时，按序插入性能更优
- ConcurrentHashMap：多线程写操作时，合理设置
initialCapacity减少扩容
六、高级应用场景
1. LRU 缓存实现
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
};
this.capacity = capacity;
}
public static void main(String[] args) {
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
System.out.println(cache); // 输出: {A=1, B=2, C=3}
cache.get("A");
System.out.println(cache); // 输出: {B=2, C=3, A=1}
cache.put("D", 4);
System.out.println(cache); // 输出: {C=3, A=1, D=4}
}
}
2. 频率统计
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.Collectors;
public class FrequencyCounter {
public static void main(String[] args) {
List<String> words = Arrays.asList("apple", "banana", "apple", "cherry", "banana", "apple");
// 使用 HashMap 统计词频
Map<String, Integer> frequencyMap = new HashMap<>();
for (String word : words) {
frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
}
System.out.println("词频统计: " + frequencyMap);
// 按频率排序
List<Map.Entry<String, Integer>> sortedEntries = frequencyMap.entrySet()
.stream()
.sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
.collect(Collectors.toList());
System.out.println("按频率排序: " + sortedEntries);
// 多线程环境下的词频统计
Map<String, Integer> concurrentFrequencyMap = new ConcurrentHashMap<>();
words.parallelStream().forEach(word -> {
concurrentFrequencyMap.compute(word, (k, v) -> v == null ? 1 : v + 1);
});
System.out.println("并发词频统计: " + concurrentFrequencyMap);
}
}
3. 范围查询场景
import java.util.TreeMap;
public class RangeQueryExample {
public static void main(String[] args) {
TreeMap<Integer, String> scoreMap = new TreeMap<>();
scoreMap.put(85, "Alice");
scoreMap.put(92, "Bob");
scoreMap.put(78, "Charlie");
scoreMap.put(95, "David");
scoreMap.put(88, "Eve");
// 查询分数在 80-90 之间的学生
System.out.println("分数在 80-90 之间的学生:");
scoreMap.subMap(80, true, 90, true).forEach((score, name) -> {
System.out.println(name + ": " + score);
});
// 查询分数高于 90 的学生
System.out.println("分数高于 90 的学生:");
scoreMap.tailMap(90, false).forEach((score, name) -> {
System.out.println(name + ": " + score);
});
}
}
七、常见误区与注意事项
HashMap 的 null 键处理
- null 键总是存储在 table [0] 位置
- 仅允许一个 null 键
TreeMap 的排序问题
// 错误示例：Key 类型未实现 Comparable 接口 Map<Person, String> treeMap = new TreeMap<>(); treeMap.put(new Person("Alice", 25), "Engineer"); // 抛出 ClassCastException // 正确示例：指定 Comparator Map<Person, String> treeMap = new TreeMap<>(Comparator.comparingInt(Person::getAge));ConcurrentHashMap 的弱一致性
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(); map.put("A", 1); map.put("B", 2); // 迭代器创建后，新增元素可能不会被遍历到 Iterator<String> iterator = map.keySet().iterator(); map.put("C", 3); while (iterator.hasNext()) { System.out.println(iterator.next()); // 可能不会输出 "C" }
八、总结与选型指南
| 特性 | HashMap | LinkedHashMap | TreeMap | ConcurrentHashMap |
|---|---|---|---|---|
| 底层结构 | 哈希表 | 哈希表 + 双向链表 | 红黑树 | 哈希表 + CAS + 锁 |
| 时间复杂度 (插入 / 查询) | O(1) | O(1) | O(log n) | O(1) |
| 顺序性 | 无 | 插入 / 访问顺序 | 键有序 | 无 |
| 线程安全 | 否 | 否 | 否 | 是 |
| null 键 / 值支持 | 支持 | 支持 | 仅值支持 | 不支持 |
| 适用场景 | 通用场景 | LRU 缓存 | 范围查询 | 高并发环境 |
通过深入理解各类型 Map 的底层实现和特性，开发者可以根据具体业务场景做出最优选择，避免常见陷阱，充分发挥不同 Map 实现的性能优势。