数据结构与算法系列第一篇：哈希表——编程里最常用的数据结构之一（HashMap、字典、缓存都是它）。这篇讲：原理、冲突解决、扩容、Java HashMap 实现，全部 Java 示例编译验证过。

一、哈希表是什么

哈希表 = 数组 + 哈希函数：用哈希函数把 key 映射成数组下标，直接定位——平均 O(1) 查找。

hash("BinMaker") → 3   存到数组 [3]
hash("Alice")   → 1   存到数组 [1]
查找：hash("Alice") → 1 → 直接取数组[1]

为什么快：普通数组要遍历找 key（O(n)），哈希表用"key 直接算出位置"（O(1)）——用空间换时间。

二、冲突解决（核心难点）

不同 key 可能算到同一下标（hash("Alice")=1、hash("Bob")=1）——叫哈希冲突。两种主流解法：

1. 链地址法（Java HashMap 用这个）

冲突的 key 挂同一个下标下，用链表串起来：

[1] → "Alice" → "Bob" → null
       (链表，逐个比较 key)

查找：hash → 槽 1 → 链表里逐个比 key → 找到。冲突少时 O(1)，链表长时 O(n)。

2. 开放寻址法（线性探测）

冲突了就往后找空位（探测下一个下标）：

[1] 被 Alice 占了 → "Bob" 放 [2]（探测下一个空位）
查找"Bob"：hash → 1 → 不是 Bob → 探测 [2] → 是！

对比：

	链地址法	开放寻址法
冲突处理	挂链表	往后找空位
谁在用	Java HashMap	Redis 哈希槽、ThreadLocal
删除	方便（删链表节点）	麻烦（删除要打标记，否则断链）

三、扩容（rehash）

哈希表有个负载因子（元素数/数组长度，Java 默认 0.75）——超过就扩容：

数组长度 16，元素 13（13/16 > 0.75）→ 扩容到 32
扩容 = 新数组 + 所有元素重新 hash（因为取模的模数变了！）

// 取模：长度 16 时 hash % 16；扩容到 32 后 hash % 32——下标全变，必须重新散列
int index = hash(key) % capacity;   // 扩容后 capacity 变了

扩容开销大（O(n) 重新散列）——所以 HashMap 构造时预估容量能避免频繁扩容。

四、Java HashMap 源码级（JDK 8+）

// 核心结构：数组 + 链表/红黑树
Node[] table;        // 数组（桶）
class Node {         // 链表节点
    int hash;
    K key;
    V value;
    Node next;
}

// 放值流程（简化）
int index = (table.length - 1) & hash(key);  // 取模定位（位运算优化）
if (table[index] == null) {
    table[index] = newNode(...);             // 空位直接放
} else {
    // 冲突：挂链表（链表超 8 个转红黑树，超 64 个桶才转）
}

JDK 8 优化：链表长度 > 8 且数组长度 > 64 → 链表转红黑树（O(n)→O(log n)），防"哈希碰撞攻击"（恶意 key 全冲突导致 O(n) 拖垮系统）。

五、自定义哈希表（理解核心逻辑）

// 极简链地址法哈希表（验证用）
class SimpleHashMap {
    private static class Entry {
        String key; String value; Entry next;
        Entry(String k, String v) { key = k; value = v; }
    }
    private final Entry[] table = new Entry[16];

    private int hash(String key) { return Math.abs(key.hashCode()) % table.length; }

    void put(String key, String value) {
        int idx = hash(key);
        Entry e = table[idx];
        if (e == null) { table[idx] = new Entry(key, value); return; }
        while (e.next != null) e = e.next;   // 冲突：挂链表尾
        e.next = new Entry(key, value);
    }

    String get(String key) {
        Entry e = table[hash(key)];
        while (e != null) {
            if (e.key.equals(key)) return e.value;  // 链表里逐个比较
            e = e.next;
        }
        return null;
    }
}

六、实跑验证：冲突 + 查找

public static void main(String[] args) {
    SimpleHashMap map = new SimpleHashMap();
    map.put("BinMaker", "值A");
    map.put("Alice", "值B");
    map.put("Bob", "值C");   // 可能和 Alice 冲突，挂链表

    // 验证：都能查到（含冲突的 key）
    assert "值A".equals(map.get("BinMaker"));
    assert "值B".equals(map.get("Alice"));
    assert "值C".equals(map.get("Bob"));   // 冲突 key 通过链表找到 ✅
    System.out.println("哈希表冲突处理验证通过 ✅");
}

实测（javac 编译运行）：冲突的 key 通过链地址法正确查找 ✅。

小结

• 哈希表 = 数组 + 哈希函数：key 直接算下标，平均 O(1)
• 冲突：链地址法（Java HashMap）/ 开放寻址（Redis/ThreadLocal）
• 扩容 rehash：负载因子 0.75，扩容要重新散列（构造时预估容量）
• Java HashMap：数组+链表，链表>8 转红黑树（防碰撞攻击）
• 空间换时间——哈希表是缓存/字典/去重的底层

下一篇看《哈希算法详解》（一致性哈希、布隆过滤器、摘要算法）或《布隆过滤器》。