哈希表

哈希表用"键 → 下标"的直接映射，把查找从遍历 O(n) 降到平均 O(1)。它解决的痛点很具体：数组按下标访问是 O(1)，但业务里要按"用户名""订单号"这种键找值，直接遍历数组就是 O(n)。哈希表在数组上套一层哈希函数，把任意键换算成下标，让数组的随机访问能力复用给任意键。

提示

哈希表的本质是空间换时间：用一块足够大的连续内存，换取按键定位的时间。理解哈希表只需要抓住三件事——哈希函数怎么算、冲突怎么解决、满了怎么办。

核心机制

哈希表 = 数组 + 哈希函数 + 冲突解决。插入 key=value 时先算 hash(key) % 容量 得到槽位下标，存入该位置；查找时同样计算下标，直接取出。

以向容量 8 的表插入 ("apple", 5) 为例：假设 hash("apple") = 210，则 210 % 8 = 2，值存入下标 2。之后查 "apple"，同样算出 2，一次定位。整个过程只做一次取模运算，与表里已存了多少数据无关——这就是 O(1) 的来源。

哈希函数

哈希函数把任意长度的键压缩成固定范围的下标。质量要求是均匀：不同键尽量分散到不同槽位，减少碰撞。

// 取模是最基本的哈希方式
int index = Math.abs(key.hashCode()) % capacity;

Java 的 HashMap 更进一步：容量固定为 2 的幂时，用位运算 hash & (capacity - 1) 替代取模，速度更快（与取模结果等价）。扰动函数 hash = h ^ (h >>> 16) 让高 16 位也参与计算，缓解"键的哈希值低位相同"导致的聚集。

可变对象作键

键对象必须不可变（如 String、Integer）。可变对象作为键时，hashCode() 可能随内容变化：先插入键 "ab"，再把它改成 "abc"，再次查找时算出不同下标，数据就"丢失"了。这是哈希表最经典的误用。

冲突解决

不同键算出同一槽位称为冲突，两种主流解决策略：

链地址法

每个槽位挂一个链表，冲突的键依次串在链上：

class Node {
    String key;
    Object value;
    Node next;   // 冲突时挂在链上
}

class HashMap {
    Node[] buckets = new Node[16];
    Object get(String key) {
        int i = hash(key) % buckets.length;
        for (Node n = buckets[i]; n != null; n = n.next) {
            if (n.key.equals(key)) return n.value;  // 链上逐个找
        }
        return null;
    }
}

优点：实现简单，删除容易，负载因子可以超过 1
缺点：链表过长时查找退化为 O(n) 遍历
代表：Java HashMap（链表超长时升级为红黑树）

开放定址法

冲突后不挂链表，而是按探测序列继续找下一个空槽：

// 线性探测：冲突了就往下挪一格
Object get(String key) {
    int i = hash(key) % buckets.length;
    while (buckets[i] != null) {
        if (buckets[i].key.equals(key)) return buckets[i].value;
        i = (i + 1) % buckets.length;   // 探测下一个槽
    }
    return null;
}

优点：无指针开销，缓存友好（数据都在数组里）
缺点：删除需要标记（不能直接清空，否则断了探测链）；负载因子高时探测链变长、性能骤降
代表：Redis 的 dict、Python 的 dict

开放定址的三种探测方式

线性探测（+1、+2、+3……）实现最简单，但连续的键会聚成一团，形成聚集现象；二次探测（+1、+4、+9……）让探测步长递增，缓解聚集；双重哈希用第二个哈希函数决定步长，分布最均匀，但多一次哈希计算。实际选型中，线性探测因缓存友好在工程里最常见。

查找过程

一次成功的查找只经历三步，全部是常数时间操作：

负载因子与扩容

负载因子 = 已存元素数 / 槽位总数，衡量表的"拥挤程度"。它决定冲突概率：负载因子 0.5 时平均每个槽一半的概率被占用，冲突少但浪费一半空间；负载因子 1.0 时空间用满但冲突明显变多。常规取 0.75（HashMap 默认值）是时间与空间的折中。

触发扩容（rehash）时，容量翻倍并重新计算所有键的位置，因为 hash(key) % 容量 的结果随容量变化。以容量 8 的表为例，hash=210 的键原本落槽 2（210 % 8 = 2），容量扩到 16 后落在 210 % 16 = 2，而 hash=250 的键从 250 % 8 = 2 变为 250 % 16 = 10——旧槽位的键要重新散列到新位置。

扩容是 O(n) 操作：put 触发扩容时，这一次写入的耗时从 O(1) 变成 O(n)，但均摊到每次操作仍然接近 O(1)（每次扩容让容量翻倍，分摊下来每插入一个元素平均只需常数次搬运）。预估元素量时在构造时指定初始容量，可以避免频繁扩容。

复杂度分析

操作	平均	最坏	原因
查找	O(1)	O(n)	均匀分布时一次定位；全部冲突时退化为遍历链表
插入	O(1)	O(n)	同上；触发扩容时单次为 O(n)，均摊 O(1)
删除	O(1)	O(n)	定位后摘除节点

最坏情况不是理论空谈：攻击者可以构造大量哈希值相同的键（如精心挑选的字符串），把哈希表打成一长条链表，让查找退化到 O(n)——这就是哈希碰撞拒绝服务攻击。Java 8 的 HashMap 把链表转红黑树（长度 > 8 且容量 ≥ 64），正是工程上对这一攻击的兜底。

HashMap 的红黑树化细节

当某个槽位的链表长度超过 8 且表容量达到 64 时，链表转为红黑树，查找从 O(n) 降到 O(log n)。转回链表的阈值是 6（留出滞后带，避免反复横跳）。注意：这是"某个槽位"的局部优化，不是整个表的优化。

典型应用

场景	做法	实例
缓存	键是查询条件，值是结果	Redis 的哈希结构、本地缓存
去重	元素入表前先查是否存在	替代 O(n^2) 的两两比较
计数器	键是统计对象，值是计数	日志中的单词频次统计
索引加速	数据库等值查询索引	MySQL 哈希索引，详见索引

单词计数是最直白的应用——一个循环解决：

Map<String, Integer> count = new HashMap<>();
for (String word : words) {
    count.put(word, count.getOrDefault(word, 0) + 1);
}

布隆过滤器是哈希表的概率版变体：用多个哈希函数把键映射到同一个位数组的多个位置，判断"一定不存在"是 O(1)（存在则可能误判）。它用少量误判率换大量空间节省，常用于缓存穿透防护——判断"这个 key 一定不在数据库"，挡住恶意构造的无效查询。

与有序结构的取舍

哈希表不维护任何顺序，需要有序遍历、范围查询（如"大于 x 的所有键""前 10 大的值"）时必须用树结构：树的 O(log n) 是结构保证的，还能中序遍历输出有序序列；哈希表的 O(1) 是概率平均的，但完全无序。对应复杂度对比见数据结构的复杂度视角——哈希表赢在单点查找，树赢在有序性，两者的选择取决于是否需要"顺序"这个维度。