第 5 章 散列

Hashing

这一章为什么重要

每天打开一个网页、访问一次缓存、编译一段程序、查询一个键值数据库，背后都可能发生一次散列查找。

散列表常见于：

  • 编程语言运行时的字典、对象属性表和符号表
  • 数据库、缓存系统和键值存储
  • 编译器的标识符表
  • 分布式系统中的分片、路由和一致性散列

本章路线图

学习目标

完成本章后，应能回答四个问题：

  • 为什么散列能把查找从“比较”变成“计算地址”
  • 为什么碰撞不可避免
  • 开放寻址和拉链法如何处理碰撞
  • 装载因子、删除和再散列如何影响真实性能

从查找问题开始

同样的数据，目标是查找 24：

\[ [10,\ 11,\ 12,\ 17,\ 24,\ 13] \]

散列表的基本图像

先插入 10，再插入 17。二者都有 \(H(key)=3\)，因此第二次插入必须沿着探测序列继续找空桶。查找 17 时，也必须走同一条路径。

演示：取余散列

设：

\[ H(x) = x \bmod 7 \]

碰撞不可避免：概率视角

桶数有限时，多个关键字落入同一桶是概率事件。这里使用 20 个桶：先播放前 10 次插入观察碰撞，再直接看 500 次插入后的涨落。

装载因子

装载因子：

\[ \alpha = \frac{n}{b} \]

其中 \(n\) 是元素个数，\(b\) 是桶数。

低装载因子：

  • 空桶更多
  • 探测更短
  • 空间开销更大

高装载因子：

  • 空间利用率更高
  • 碰撞更频繁
  • 更需要再散列

散列函数一：取余法

\[ H(key)=key \bmod M \]

常见做法是让 \(M\) 取不超过表长的较大质数。

质数不能消灭碰撞，但能减少某些周期性输入造成的集中分布。

为什么常选质数

散列函数二：平方取中法

平方取中法先计算 \(key^2\)，再取中间若干位作为地址。

\[ \begin{array}{r} \phantom{00000}101101 \\ \times\phantom{000}101101 \\ \hline \phantom{00000}101101 \\ \phantom{000}10110100 \\ \phantom{00}101101000 \\ 10110100000 \\ \hline 11111101001 \end{array} \qquad 11111101001 \Rightarrow 111\color{#1266d6}{1110}1001 \]

取中间 4 位得到 1110。竖式的意义是：平方后的中间位同时受原关键字的高位和低位影响，因此比“只取低位”更不容易继承输入模式。

它适合低位或高位分布不均的场景。核心目的不是平方本身，而是让关键字的多位信息共同影响地址。

散列函数三：乘法散列

\[ H(key)=\lfloor M \cdot ((A \cdot key) \bmod 1) \rfloor \]

其中 \(0<A<1\)。

常见选择之一是 \(A \approx 0.618\)。

它利用小数部分打散输入中的简单模式。

字符串散列：简单求和的问题

int hash_sum(const string& key, int table_size) {
    int h = 0;
    for (char ch : key) {
        h += static_cast<unsigned char>(ch);
    }
    return h % table_size;
}

如果所有关键字长度不超过 8，ASCII 字符最大约 127，则总和范围通常不超过 1016。表长为 10007 时，大量桶永远不会被使用。

字符串散列：多项式滚动

int hash_string(const string& key, int table_size) {
    long long h = 0;
    for (char ch : key) {
        h = 37 * h + static_cast<unsigned char>(ch);
        h %= table_size;
    }
    return static_cast<int>(h);
}

乘以 37 的作用是让字符的位置影响最终结果。

如果只把字符相加，所有长度不超过 8 的 ASCII 字符串大多落在很小的取值空间里。多项式滚动每读入一个字符就把已有结果乘大，再加入新字符，使不同位置的字符产生不同权重。

散列函数的多维分析

维度 问题 典型风险
均匀性 是否把 key 分散到不同桶 聚集、长探测链
速度 每次计算是否足够快 常数因子过大
稳定性 相同 key 是否稳定映射 难以复现或调试
抗模式 能否处理有规律的输入 周期性冲突
安全性 是否容易被构造碰撞 拒绝服务攻击

碰撞处理总览

开放寻址：

  • 元素仍然放在数组里
  • 冲突后继续探测
  • 典型方法：线性、二次、双散列

拉链法：

  • 桶中挂链表或容器
  • 冲突元素留在同一个桶
  • 删除更直接

本章重点比较开放寻址和拉链法。

线性探测

若 \(H(key)=d\)，且位置 \(d\) 已被占用，则依次检查：

\[ d+1, d+2,\ldots,m-1,0,1,\ldots,d-1 \]

线性探测的平均查找长度

插入序列：

\[ 10,\ 11,\ 12,\ 17 \]

成功查找比较次数：

\[ 1,\ 1,\ 1,\ 4 \]

\[ ASL_{succ}=\frac{7}{4}=1.75 \]

聚集问题

线性探测容易形成连续占用区。不同关键字的探测路径会合并，使之后的插入和查找越来越慢。

线性探测：11 桶插入动画

使用 \(H(k)=k\bmod 11\)，依次插入 80, 40, 65, 24, 58, 35。

线性探测：ASL 计算

先列出每个关键字的 home bucket：

\[ H(80)=3,\ H(40)=7,\ H(65)=10,\ H(24)=2,\ H(58)=3,\ H(35)=2 \]

线性探测后的成功查找比较次数是：

\[ 1,\ 1,\ 1,\ 1,\ 2,\ 4 \]

因此：

\[ ASL_{succ}=\frac{1+1+1+1+2+4}{6}=\frac{10}{6} \]

这个例子要观察的是：同义词并不只是“同一个 home bucket 的 key”。线性探测会把相邻冲突链合并，形成更大的 cluster。

字符串散列：只看首字母的风险

考虑一个只看首字母的散列函数：

\[ hash(key)=ord(key[0])-ord('A') \]

Burke、Broad、Blum 都落在 B；Attlee、Alton 都落在 A；Ekers、Ederly 都落在 E。

这说明一个重要工程原则：

  • 如果散列函数只看输入的一小部分，很多不同 key 会被压到少数桶里。
  • 即使桶很多，信息没有被充分使用，也会浪费地址空间。
  • 字符串散列要让每个字符的位置都影响结果，这就是多项式滚动散列的动机。

删除不能简单清空

如果删除探测链中间的元素时直接设为空，后面的元素可能再也查不到。

这里 \(H(11)=11\bmod 7=4\)。查找 11 必须沿着从 4 开始的探测链继续走，不能在 24 原来的位置提前停止。

工程主线：本章使用同一套 C++ 代码

这一节后半部分都围绕同一个工程展开：

hash-table-demo/
  CMakeLists.txt
  include/hash_tables.hpp
  src/main.cpp

最后一页提供完整 zip 文件。

代码 1：状态与表项定义

enum class SlotState {
    Empty,
    Occupied,
    Deleted
};

template <class Key>
struct Entry {
    Key key{};
    int value = 0;
    SlotState state = SlotState::Empty;
};

SlotState 把空桶、有效元素和墓碑分开。删除页之所以不能直接清空，原因就在这里。

key 是模板变量，便于替换为 int、string 或自定义类型；value 在本章工程中固定为 int，让演示聚焦在散列表结构本身。

代码 2：类接口

template <class Key, class Probe = LinearProbe, class Hash = std::hash<Key>>
class OpenAddressingHashTable {
public:
    explicit OpenAddressingHashTable(std::size_t capacity = 7, Probe probe = Probe{});

    bool insert(const Key& key, int value);
    std::optional<int> find(const Key& key) const;
    bool erase(const Key& key);

    double load_factor() const;
    void print() const;

private:
    std::size_t hash(const Key& key) const;
    std::size_t find_slot(const Key& key) const;
    void rehash();
};

模板参数把“key 类型、探测策略、哈希器”拆开；同一套表可以切换线性探测、二次探测和双散列。

对外接口只保留 insert、find、erase，所有散列表操作都落到这三个函数。

私有函数负责地址计算、探测链和扩容；使用者不需要知道内部如何解决碰撞。

代码 3：散列函数

std::size_t hash(const Key& key) const {
    return hasher_(key) % table_.size();
}

输入是任意 Key，因此先交给 hasher_ 转成整数型哈希值。

取余把哈希值压到桶下标范围内：0..table_.size()-1。

这就是 H(key)=key mod 7 在工程代码中的对应形式。

代码 4：寻找槽位

std::size_t find_slot(const Key& key) const {
    const std::size_t start = hash(key);
    std::size_t first_deleted = table_.size();

    for (std::size_t i = 0; i < table_.size(); ++i) {
        const std::size_t pos = probe_(start, i, table_.size(), static_cast<int>(hasher_(key)));
        const Entry<Key>& e = table_[pos];
        if (e.state == SlotState::Occupied && e.key == key) return pos;
        if (e.state == SlotState::Deleted && first_deleted == table_.size()) first_deleted = pos;
        if (e.state == SlotState::Empty) return first_deleted == table_.size() ? pos : first_deleted;
    }

    return first_deleted;
}

先计算 home bucket，并记录遇到的第一个墓碑位置。

探测策略由 probe_ 决定：线性、二次、双散列只替换这一行的公式。

如果遇到同 key，返回当前位置；如果遇到墓碑，先记下来但继续找，避免重复 key 被漏掉。

遇到真正的空桶才说明探测链结束；如果之前见过墓碑，就优先复用墓碑。

整张表都走完仍没有可用槽位时，返回 table_.size()；这是“插入找槽位失败”，不是普通查找失败。

代码 5：插入

bool insert(const Key& key, int value) {
    if (load_factor() > 0.85) rehash();

    const std::size_t i = find_slot(key);
    if (i == table_.size()) {
        rehash();
        return insert(key, value);
    }

    if (table_[i].state == SlotState::Occupied) {
        table_[i].value = value;
        return false;
    }

    table_[i] = Entry<Key>{key, value, SlotState::Occupied};
    ++size_;
    return true;
}

插入前先检查装载因子，避免探测链在表快满时急剧变长。

find_slot 既能找到已有 key，也能找到可插入位置；只有没有任何可用槽位时，才扩容后重试插入。

如果 key 已存在，更新 value，而不是插入重复项。

真正插入时写入 Entry<Key>，状态变为 Occupied，表中元素数加一。

代码 6：查找

std::optional<int> find(const Key& key) const {
    const std::size_t start = hash(key);

    for (std::size_t i = 0; i < table_.size(); ++i) {
        const std::size_t pos = probe_(start, i, table_.size(), static_cast<int>(hasher_(key)));
        const Entry<Key>& e = table_[pos];
        if (e.state == SlotState::Empty) return std::nullopt;
        if (e.state == SlotState::Occupied && e.key == key) return e.value;
    }

    return std::nullopt;
}

查找同样从 home bucket 开始。

每一步使用同一个探测公式，保证查找路径与插入路径一致。

遇到 Empty 才能断定不存在，因为插入时如果路径上出现过真正空桶，目标 key 不可能在后面。

遇到目标 key 就返回 value。

代码中没有 Deleted 的提前返回分支；墓碑不能终止查找，因为目标 key 可能在墓碑后面。

代码 7：删除

bool erase(const Key& key) {
    const std::size_t start = hash(key);

    for (std::size_t i = 0; i < table_.size(); ++i) {
        const std::size_t pos = probe_(start, i, table_.size(), static_cast<int>(hasher_(key)));
        Entry<Key>& e = table_[pos];
        if (e.state == SlotState::Empty) return false;
        if (e.state == SlotState::Occupied && e.key == key) {
            e.value = 0;
            e.state = SlotState::Deleted;
            --size_;
            return true;
        }
    }
    return false;
}

删除也必须沿着同一条探测链走。

遇到空桶表示 key 不在表中；遇到其他 key 或墓碑则继续探测。

找到目标后不清空桶，而是写入 Deleted，保持之后插入的 key 仍然可达。

遍历结束仍未找到，删除失败。

二次探测

二次探测让探测距离按平方变化：

\[ H_i(k)=(H(k)+i^2)\bmod m \]

二次探测的分析

维度 线性探测 二次探测
探测路径 连续相邻 跳跃式
主聚集 明显 缓解
缓存局部性 更好 稍弱
约束 简单 依赖表长和装载因子

二次探测不是“线性探测的无条件升级”，它换来了不同的约束。

双散列

双散列使用第二个散列函数决定步长：

\[ H_i(k)=(H_1(k)+i\cdot H_2(k))\bmod m \]

常见选择：

\[ H_2(k)=R-(k\bmod R) \]

双散列演示

\[ H_1(k)=k\bmod 7,\quad H_2(k)=5-(k\bmod 5),\quad H_i(k)=(H_1(k)+i\cdot H_2(k))\bmod 7 \]

双散列的约束

步长必须能够覆盖表中所有位置。

若 \(\gcd(H_2(k),m)\ne 1\)，探测序列可能只访问表的一部分。

因此表长常取质数，第二个散列函数的步长也要和表长互质。下面的 7 桶例子中，\(R=5\)，每个非零步长都能覆盖全表。

再散列

当装载因子过高时，散列表需要扩容，并对每个有效 key 重新计算新表地址。

代码 8：再散列

void rehash() {
    std::vector<Entry<Key>> old = std::move(table_);
    table_.assign(next_prime(old.size() * 2), Entry<Key>{});
    size_ = 0;

    for (const Entry<Key>& e : old) {
        if (e.state == SlotState::Occupied) {
            insert(e.key, e.value);
        }
    }
}

先保存旧表，创建更大的新表，并把当前元素数清零。

然后只取出 Occupied 的有效元素，调用 insert 重新计算它们在新表中的位置。

单次再散列是 \(O(n)\)，但合理扩容下插入的摊还代价仍可接近 \(O(1)\)。

拉链法

拉链法让每个桶保存一个链表或其他容器。

拉链法：C++ 结构

template <class Key, class Hash = std::hash<Key>>
class SeparateChainingHashTable {
public:
    explicit SeparateChainingHashTable(std::size_t bucket_count = 7)
        : buckets_(bucket_count) {}

    bool insert(const Key& key, int value) {
        auto& bucket = buckets_[hash(key)];
        for (auto& [k, v] : bucket) {
            if (k == key) {
                v = value;
                return false;
            }
        }
        bucket.push_front({key, value});
        return true;
    }

    std::optional<int> find(const Key& key) const;
    bool erase(const Key& key);

private:
    std::size_t hash(const Key& key) const {
        return hasher_(key) % buckets_.size();
    }

    std::vector<std::forward_list<std::pair<Key, int>>> buckets_;
    Hash hasher_{};
};

拉链法仍然使用桶数组，但每个桶保存一个 forward_list。

插入时只检查当前桶内链表：同 key 更新，否则头插。

查找和删除也只在对应桶内进行，不需要墓碑。

hash 仍然是“哈希值取余桶数”，区别在于碰撞元素不再继续找其他桶。

多维比较

维度 开放寻址 拉链法
存储结构 单个数组 桶数组 + 链表或容器
缓存局部性 通常较好 节点分散时较差
删除 需要墓碑或重排 链表删除直接
高装载因子 性能下降明显 可承受 \(\alpha>1\)
迭代稳定性 扩容会移动元素 扩容也会重分桶
工程风险 探测链变长 指针和内存分配开销

前沿连接：大规模系统中的散列

散列不仅用于单机查找，也用于分布式系统。

Redis key 查找、字典扩容、渐进式 rehash

PostgreSQL hash join、hash aggregate、索引访问

Kafka 按 key 分区，把消息路由到 partition

Python dict / set 是语言级核心结构

flowchart LR
  K["request key"] --> H["hash(key)"]
  H --> R["route to shard"]
  R --> S1["shard A"]
  R --> S2["shard B"]
  R --> S3["shard C"]

一致性散列、虚拟节点和分片迁移，都是把“key 到位置”的思想扩展到多台机器上。

前沿连接：安全与可靠性

散列表的平均 \(O(1)\) 依赖输入不是恶意构造。

在公开服务中，如果攻击者能制造大量碰撞，散列表可能退化为 \(O(n)\)。

现代运行时和框架通常会考虑：

  • 随机化哈希种子
  • 限制单桶长度
  • 碰撞过多时切换结构

小结

散列表快，是因为它把“查找”转化为“地址计算”。

它可靠，是因为工程实现同时处理了：

  • 散列函数质量
  • 碰撞策略
  • 装载因子
  • 删除语义
  • 再散列

代码 9：main 函数

int main() {
    OpenAddressingHashTable<int, LinearProbe, IdentityHash> linear(7);
    for (int key : {10, 17, 24, 11, 18, 25}) {
        linear.insert(key, key * 10);
    }
    linear.print("linear probing");

    OpenAddressingHashTable<int, QuadraticProbe, IdentityHash> quadratic(7);
    OpenAddressingHashTable<int, DoubleHashProbe, IdentityHash> double_hash(7, DoubleHashProbe{5});
    SeparateChainingHashTable<int, IdentityHash> chaining(7);
}

代码 10：CMakeLists.txt

cmake_minimum_required(VERSION 3.16)
project(hash_table_demo LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

add_executable(hash_table_demo
    src/main.cpp
)

target_include_directories(hash_table_demo PRIVATE include)

代码之后：统一分析框架

现在回到算法层面：一张散列表不能只问“平均是不是 \(O(1)\)”，还要同时问六个问题。

维度 关键问题 对应内容
正确性 插入、查找、删除是否沿同一条可达路径 find_slot、find、墓碑
平均性能 随机输入下探测长度多长 装载因子、ASL
最坏性能 能否退化到 \(O(n)\) 聚集、恶意碰撞
空间成本 桶、墓碑、链表节点是否浪费 开放寻址 vs 拉链法
局部性 CPU cache 是否友好 数组连续性、链表指针跳转
可维护性 扩容、泛型、异常路径是否清楚 rehash、模板参数

开放寻址：三种探测策略比较

线性探测

  • 公式最简单
  • cache locality 最好
  • 最容易产生 primary clustering

二次探测

  • 跳跃距离逐渐变大
  • 缓解 primary clustering
  • 依赖表长、装载因子和探测公式

双散列

  • 步长由第二个散列函数决定
  • 探测路径更像“伪随机排列”
  • 必须保证步长与表长互质

成功查找与失败查找

成功查找的代价来自“这个 key 插入时走了多远”。

失败查找的代价来自“从 home bucket 出发，要走到哪里才能确认不存在”。

开放寻址中：

  • 遇到 Occupied 且 key 不同：继续探测。
  • 遇到 Deleted：继续探测，因为目标可能在墓碑后面。
  • 遇到真正的 Empty：可以停止，说明插入时不可能越过这个空桶。

因此删除逻辑不是实现细节，而是查找正确性的一部分。

装载因子、再散列与摊还成本

一种常见经验是：当表项数超过表长的约 70% 时触发再散列。工程实现中阈值不是唯一答案：

  • 开放寻址通常选择较低阈值，例如 0.5 到 0.85，因为探测长度会随 \(\alpha\) 急剧上升。
  • 拉链法可以允许 \(\alpha>1\)，但链长或桶内结构会影响常数。
  • 一次 rehash 是 \(O(n)\)，但如果容量按比例增长，多次插入的摊还成本仍可接近 \(O(1)\)。

要注意：再散列必须对每个 key 重新计算地址，不能把旧桶原样搬过去。

散列函数质量：不仅是“均匀”

好的散列函数至少要考虑：

  • 均匀性：不同 key 是否尽量分散到不同桶。
  • 速度：计算 hash 的常数成本是否过高。
  • 稳定性：同一 key 在同一运行策略下是否可复现。
  • 抗模式：连续整数、相同前缀字符串、固定步长输入是否会集中。
  • 安全性：攻击者是否能构造大量碰撞。

入门例子常写 key mod m，但真实工程中会先把 key 混合成高质量哈希值，再映射到桶下标。

拉链法的多维分析

拉链法把“继续找下一个桶”改成“在同一个桶内部查找”。

优点：

  • 删除更直接，不需要墓碑。
  • 装载因子可以超过 1。
  • 表扩容前的性能退化更平滑。

代价：

  • 节点分散，cache locality 往往不如开放寻址。
  • 每个节点有额外指针或容器开销。
  • 如果单桶过长，仍然会退化，需要扩容、树化或安全哈希。

工程选型：什么时候用哪一种

场景 更常见选择 原因
小对象、读写频繁、追求 cache locality 开放寻址 数据连续，常数小
删除频繁、元素较大、装载因子波动大 拉链法 删除简单，扩容压力较低
面向公开输入的服务 带随机化或防御策略的实现 避免碰撞攻击
需要稳定迭代顺序 普通散列表不一定合适 扩容会改变桶位置
分布式分片 一致性散列或 rendezvous hashing 节点变化时减少迁移

可运行代码

配套完整 C++ 工程：

hash-table-demo.zip

构建命令：

cmake -S . -B build
cmake --build build

运行命令：

./build/Debug/hash_table_demo.exe

习题 1

给定输入：

\[ \{10, 17, 24, 11, 18, 25\} \]

散列函数：

\[ h(x)=x\bmod 7 \]

分别画出拉链法、线性探测、二次探测和双散列结果。双散列使用 \(h_2(x)=5-(x\bmod 5)\)。

习题 1 答案

线性探测：

习题 1 答案：二次探测

二次探测：

习题 1 答案：拉链与双散列

拉链法：

习题 1 答案：双散列

双散列：

双散列的每一步都在图上列出 H(key)、H2(key) 和当前探测公式。请注意：表长为 7 时，只要步长不是 7 的倍数，就能覆盖全表。

习题 2

设散列表为 HT[7]，散列函数：

\[ H(key)=key\bmod 7 \]

用线性开地址法解决冲突，插入关键码序列：

\[ 9, 16, 23, 2, 30, 37 \]

求散列表、成功查找 ASL，以及拉链法结构。

习题 2 答案

线性开地址散列表：

\[ ASL_{succ}=\frac{1+2+3+1+4+5}{6}=\frac{16}{6}\approx 2.67 \]

习题 2 答案：拉链法

拉链法结构：

习题 3

给定输入：

\[ \{4371,1323,6173,4199,4344,9679,1989\},\quad h(x)=x\bmod 10 \]

分别给出拉链法、线性探测、二次探测、双散列结果。双散列使用：

\[ h_2(x)=7-(x\bmod 7) \]

注意这个设置中的一个关键约束：表长是 10，不是质数；双散列步长可能与 10 不互质，因此不一定能访问全表。

习题 3 答案：拉链法

拉链法：

\[ 1:\ 4371;\quad 3:\ 1323\to6173;\quad 4:\ 4344;\quad 9:\ 4199\to9679\to1989 \]

习题 3 答案：线性探测

线性探测结果：

\[ [9679,\ 4371,\ 1989,\ 1323,\ 6173,\ 4344,\ empty,\ empty,\ empty,\ 4199] \]

习题 3 答案：二次探测

若采用 \(H_i=(h+i^2)\bmod 10\) 的二次探测：

\[ [9679,\ 4371,\ empty,\ 1323,\ 6173,\ 4344,\ empty,\ empty,\ 1989,\ 4199] \]

习题 3 答案：双散列

双散列中，1989 的 \(h_2=7-(1989\bmod 7)=6\)，而 \(\gcd(6,10)=2\)，探测序列不能覆盖全表。这说明双散列的表长与步长约束不能省略。

习题 4

设：

\[ HT[13],\quad H(key)=key\bmod 13 \]

插入序列：

\[ 12,23,45,57,20,03,78,31,15,36 \]

习题 4 答案：线性开放寻址

线性开放寻址结果：

\[ [78,\ empty,\ 15,\ 3,\ empty,\ 57,\ 45,\ 20,\ 31,\ empty,\ 23,\ 36,\ 12] \]

习题 4 答案：成功查找 ASL

成功查找比较次数：

\[ 1,1,1,1,1,1,1,4,1,2 \]

因此：

\[ ASL_{succ}=\frac{14}{10}=1.4 \]

习题 4 答案：拉链法

拉链法结果：

\[ 0:\ 78;\ 2:\ 15;\ 3:\ 3;\ 5:\ 57\to31;\ 6:\ 45;\ 7:\ 20;\ 10:\ 23\to36;\ 12:\ 12 \]

延伸阅读