一、从C语言到Java HashMap：一场数据结构进化史

说实话，我最早接触哈希表是在C语言里。那时候自己手写链地址法，malloc、free用得飞起。后来转到Java开发，第一次看到HashMap源码时，我愣住了——这玩意儿怎么这么复杂？

但仔细一想，Java HashMap本质上还是那个哈希表。只不过它站在了巨人的肩膀上，把C语言里那些需要手撸的细节，都封装成了优雅的API。今天我就带你看看，这个工业级哈希表到底是怎么设计的。

二、Java HashMap的核心实现

2.1 数据结构：数组+链表+红黑树

Java 8之后的HashMap，底层结构长这样：

// 简化版源码示意
public class HashMap<K,V> {
    // 核心数组，每个元素是链表头或红黑树根
    Node<K,V>[] table;
    
    // 链表节点
    static class Node<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    
    // 红黑树节点
    static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;
    }
}

嗯，这里要注意：数组的每个槽位，要么是null，要么是链表头，要么是红黑树根。判断依据是链表长度——超过8就转红黑树。

2.2 put操作流程

我当年面试时，被问过不下十次HashMap的put流程。其实说白了就这几步：

1. 计算key的hash值（高16位参与异或）
2. 定位到数组槽位（(n-1) & hash）
3. 如果槽位为空，直接插入
4. 如果槽位不为空，遍历链表或红黑树
5. 找到相同key就覆盖，没找到就插入
6. 插入后检查是否需要扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent) {
    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 {
        // 处理哈希冲突...
    }
}

三、红黑树优化：为什么是8和6？

你可能会问：为什么链表长度到8才转红黑树？为什么退化阈值是6而不是7？

我个人理解是这样的：

• 8这个阈值：来自泊松分布的计算。在理想随机哈希下，链表长度达到8的概率已经小于千万分之一。如果真到了8，说明哈希函数有问题或者数据分布极不均匀，这时候用红黑树来兜底。
• 6和8差2：这是为了避免频繁转换。如果阈值设成7和8，那链表长度在7和8之间反复横跳时，就会不停地树化、退化，性能反而更差。

四、扩容机制：最耗时的操作

HashMap的扩容，说白了就是重新分配一个更大的数组，然后把所有元素重新哈希。这个过程的时间复杂度是O(n)，所以如果你能预估数据量，最好在初始化时指定容量。

4.1 扩容触发条件

if (++size > threshold)
    resize();

threshold = capacity * loadFactor。默认16*0.75=12，也就是说存到第13个元素时就会扩容。

4.2 扩容过程

扩容到原来的两倍，元素重新分布。这里有个巧妙的设计：元素在新数组中的位置，要么在原位置，要么在原位置+旧容量。为什么？因为容量是2的幂，扩容后hash值多了一位参与运算。

// 判断元素在新数组中的位置
if ((e.hash & oldCap) == 0) {
    // 位置不变
} else {
    // 位置 = 原位置 + oldCap
}

五、并发问题：HashMap不是线程安全的

这个问题我必须重点强调：HashMap不是线程安全的。我在生产环境见过太多次因为并发put导致死循环的案例了——虽然Java 8修复了头插法导致的死循环问题，但数据丢失、size不准确等问题依然存在。

5.1 并发场景下的替代方案

方案	特点	适用场景
Hashtable	全表加锁，性能差	基本不用
Collections.synchronizedMap	包装类，也是全表锁	简单场景
ConcurrentHashMap	分段锁/CAS+锁，性能好	高并发首选

5.2 ConcurrentHashMap的原理

Java 8的ConcurrentHashMap采用了CAS+synchronized的组合拳：

• 读操作：基本无锁，靠volatile保证可见性
• 写操作：对数组槽位加锁，锁粒度很细
• 扩容：支持多线程协同扩容

六、知识体系总览

下面这张图，是我梳理的HashMap知识体系。你可以把它当作复习提纲：

七、总结

Java HashMap的设计，说白了就是用空间换时间，用复杂度换稳定性。从C语言的手动管理内存，到Java的自动扩容和红黑树优化，底层逻辑没变，但工程实现上做了大量权衡。

我个人觉得，理解HashMap最好的方式，就是把它和C语言的哈希表对比着看。你会发现，那些看似复杂的优化——红黑树、2的幂容量、高16位异或——其实都是为了解决实际工程问题。

---