3.4 Hash Tables：散列函数、碰撞策略与负载控制

3.4 · Hash Tables覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“3.4 · Hash Tables”如何从 hashCode/equals 合同、均匀散列假设、拉链法与线性探测推导负载控制
  • 能逐项核对 散列表、散列函数、均匀散列假设、拉链法、线性探测、散列表扩缩容，并区分作者站内容与本页独立补充
  • 能按“拉链平均链长 α=N/M；线性探测命中/未命中成本随 α→1 急剧上升”手算一个最小输入，逐步检查“equals 相等的键必须有相同 hashCode；所有键可由当前表容量和探测规则重新找到”
  • 能注入“键入表后发生可影响 hashCode 的变更，或删除线性探测槽位却不重建后续簇”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“3·4 · Hash Tables”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“3·4 · Hash Tables”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“3·4 · Hash Tables”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：3.4 · Hash Tables

  • 1. 散列表：在本页通过“计算一致哈希”连接解释、交互状态和练习验收。
  • 2. 散列函数：在本页通过“映射到桶或槽”连接解释、交互状态和练习验收。
  • 3. 均匀散列假设：在本页通过“处理碰撞”连接解释、交互状态和练习验收。
  • 4. 拉链法：在本页通过“按负载扩缩容”连接解释、交互状态和练习验收。
  • 5. 线性探测：在本页通过“核对全部键值”连接解释、交互状态和练习验收。
  • 6. 散列表扩缩容：在本页通过“计算一致哈希”连接解释、交互状态和练习验收。

从“直接算出地址”开始

前两节search tree通过comparison逐层排除范围；散列表（hash tables）尝试直接算出key应从哪个array位置开始查。理想情况一次indexing命中，但key universe通常远大于M个slots，所以不同keys映射到同一index的collision不可避免。

先预测两个keys得到相同hashCode时，table是否可以把它们视作相等。不能。Hash equality只说明它们进入同一collision-resolution区域；仍必须调用 equals() 区分。反过来，若 a.equals(b) 为true，两者hashCode必须相同，否则lookup会去另一个bucket，连比较a与b的机会都没有。

Hashing由两个独立部分组成：

  1. Hash function把任意key压缩成0到M减1的array index。
  2. Collision policy在同一index容纳多个distinct keys，本节比较separate chaining与linear probing。

3.4.1 Hash functions：从object到array index

散列函数（hash functions）既依赖key type，也依赖table size M。Positive integer常取mod M；String可按radix R逐character滚动：

hi=(Rhi−1+si) mod Mh_i=(R h_{i-1}+s_i)\bmod M

Java String 使用31生成32-bit hashCode()。User-defined compound key也应把每个field混入，而不是只取看似方便的一段。Official textbook index conversion是：

private int hash(Key key) {
    return (key.hashCode() & 0x7fffffff) % M;
}

Mask sign bit比 Math.abs(hashCode()) 安全，因为32-bit minimum integer的absolute value仍无法表示为positive。Current algs4 code在power-of-two capacity上还会xor-shift高bits到低bits，再执行 h & (m - 1)，以减轻poor low-bit hashCode对bucket选择的影响。

Hash function有三个要求：deterministic；计算快；uniformly distribute实际keys。第一项是correctness contract，后两项决定performance。Constant hashCode在Java语义上可以合法，因为equal keys当然同hash，但它把所有operations退化成collision list或long probe cluster。

Java contract必须精确理解：

  • a.equals(b) 为true，必须有 a.hashCode()==b.hashCode()。
  • HashCode相同不推出equals；collision后仍要equals。
  • 参与hashCode与equals的fields在key位于table期间不能改变，否则association留在old bucket，new hash从别处开始。
  • equals(Object) 必须真正override，而不是只写一个parameter type更窄的overload。

3.4.2 Uniform hashing assumption：性能前提不是事实

均匀散列假设（uniform hashing assumption）是官方Assumption J：hash function把keys均匀分布在M个indices。它让average analysis可计算，却不提供adversarial worst-case guarantee。

若N个keys进入M个buckets，平均load为：

α=NM\alpha=\frac{N}{M}

但平均值不能证明每个bucket都短。Under Assumption J，chain length以极高概率接近N/M；若input fields与hash缺陷相关，某一bucket仍可能装下N个keys。验收不能只跑random UUID，还应测sequential IDs、common prefixes、low-bit patterns、known collisions与constant-hash test double。

Hash table expected O(1)的完整条件是：hash计算本身bounded；distribution接近uniform；load受控；collision policy正确。Very long key若每次重新计算hash，key hashing成本也可能主导operation；immutable object可缓存hash，但必须保持equals/hash consistency。

3.4.3 Separate chaining：array of small symbol tables

拉链法（separate chaining）使用M个 SequentialSearchST。Get/put/delete先hash到唯一chain，再把association operation委托给该chain：

private SequentialSearchST<Key, Value>[] st;
 
public Value get(Key key) {
    int i = hash(key);
    return st[i].get(key);
}
 
public void put(Key key, Value val) {
    if (n >= 10 * m) resize(2 * m);
    int i = hash(key);
    if (!st[i].contains(key)) n++;
    st[i].put(key, val);
}

Separate-chaining load factor N/M是average chain length，可以大于1。Under uniform hashing，search与insert equality tests proportional to N/M；M越大，chains越短但empty-list objects与array references占更多memory。

Duplicate put必须覆盖value而不增加N。Delete只有key存在才decrement N。Current implementation在average chain length达到10时double chains，降到2以下且capacity大于initial时halve；不同threshold形成hysteresis，避免N在boundary附近让table来回resize。

Separate chaining容忍较高load，delete简单，也允许table不预留empty slots；代价是pointer chasing、per-node allocation与cache locality较差。它不提供ordered operations，iteration order也不是key order或insertion order contract。

3.4.4 Linear probing：empty slot同时是storage与stop signal

线性探测（linear probing）把keys与values直接放在parallel arrays中。它从home index开始有三种结果：

  1. Slot key equal query：hit或覆盖value。
  2. Slot为null：miss，put可在此insert。
  3. Slot是different key：probe next index并在M处wrap到0。
public void put(Key key, Value val) {
    if (n >= m / 2) resize(2 * m);
    int i;
    for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
        if (keys[i].equals(key)) {
            vals[i] = val;
            return;
        }
    }
    keys[i] = key;
    vals[i] = val;
    n++;
}

Open-addressing load factoralpha=N/M是occupied fraction，必须小于1。Consecutive occupied slots形成cluster；任何hash落入cluster start到end的key都会延长cluster，称primary clustering。Array locality很好，但clusters让probe成本随load非线性增长。

Under uniform hashing，官方Proposition M给average probes：

E[hit]∼12(1+11−α)E[\mathrm{hit}]\sim\frac{1}{2}\left(1+\frac{1}{1-\alpha}\right) E[miss/insert]∼12(1+1(1−α)2)E[\mathrm{miss/insert}]\sim\frac{1}{2}\left(1+\frac{1}{(1-\alpha)^2}\right)

当alpha为0.5，hit约1.5 probes，miss/insert约2.5；当alpha逼近1，denominator趋近0，miss成本爆发。Current implementation在50% full之前double table，主动用space换稳定probe count。

3.4.5 Linear-probing deletion：不能在cluster中间留null

Linear probing的null不只是“unused”，还是get判定search miss的证据：从home到目标之间若出现null，目标不可能位于更后方。因此直接把deleted slot设null会切断cluster，让后续仍存在的keys变成unreachable。

正确delete先找到target置null，然后向右扫描同一continuous cluster；每个后继association先取出、slot清空、N减1，再调用put从其home重新insert。最后再为target本身减N：

keys[i] = null;
vals[i] = null;
 
i = (i + 1) % m;
while (keys[i] != null) {
    Key keyToRehash = keys[i];
    Value valToRehash = vals[i];
    keys[i] = null;
    vals[i] = null;
    n--;
    put(keyToRehash, valToRehash);
    i = (i + 1) % m;
}
n--;

Delete scan看似可能很长，但在load受控与uniform assumption下expected cost仍constant。Worst case所有keys形成一个cluster时仍可linear；这再次说明hash table不是balanced BST那种comparison-based worst-case guarantee。

3.4.6 Hash-table resizing：capacity改变就必须rehash

散列表扩缩容（hash-table resizing）不能用array copy完成，因为index formula包含M。原来 hash % 8 的位置不一定等于 hash % 16；linear-probing placement还受new collision order影响。

Resize创建new empty table，逐key调用put，再替换arrays与M。Doubling的总搬移成本形成geometric series：

N+N2+N4+⋯<2NN+\frac{N}{2}+\frac{N}{4}+\cdots < 2N

所以一段N次insert的rehash总额linear，amortized expected insert仍constant。Shrink不能与grow使用同一threshold，否则一次delete与put可反复搬全表。Linear probing在50% grow、12.5% shrink，形成大hysteresis；separate chaining则按average chain thresholds控制。

Resize验收应检查每个old key在new table仍get到same value、N不变、duplicate association未复制、probe reachability成立。Concurrent implementation还要规定migration期间read/write可见性；本书single-thread code不能直接推导thread safety。

3.4.7 选择与验收：速度来自受控前提

Separate chaining适合delete频繁、load可大于1、实现简单的场景；linear probing适合cache locality重要且可维持低load的场景。两者都只支持unordered ST；需要min/max、rank、range或sorted iteration时，应使用red-black BST。

Hash table测试至少分五层：

  • Contract：equal keys同hash、distinct collision仍分开、key immutable。
  • Distribution：bucket histogram、max chain、probe-distance percentiles。
  • Operations：duplicate put、missing get/delete、null policy、wrap-around。
  • Structural：linear table每个key从home起在遇null前reachable；N等于actual associations。
  • Resize：跨grow/shrink后与reference map执行长random sequence差分。

Expected O(1)不能只用wall-clock证明；要记录equals count、probe count、load与rehash events。Bad distribution可能在small test看起来快，却在production key family上集中爆发。

统一验收：把hash、collision与load分开验证

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“3.4 · Hash Tables”的两个最小情境间切换，再逐项选择正式概念。预测“拉链平均链长 α=N/M；线性探测命中/未命中成本随 α→1 急剧上升”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

3.4 · Hash Tables：对象、操作与不变量

从 hashCode/equals 合同、均匀散列假设、拉链法与线性探测推导负载控制

选择最小情境

切换正式概念

输入合同操作证书algs4-3.4 · 先给前提，再执行，再验收当前概念：1/6
拉链碰撞
让 A、K、U 映射到同一桶
当前观察
hash tables：桶内仍用 equals 区分键，碰撞不会覆盖不同键
拉链平均链长 α=N/M；线性探测命中/未命中成本随 α→1 急剧上升

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 散列表：在实验 1 中指出对应状态，并写出一个通过条件。
  • 散列函数：在实验 2 中指出对应状态，并写出一个通过条件。
  • 均匀散列假设：在实验 3 中指出对应状态，并写出一个通过条件。
  • 拉链法：在实验 1 中指出对应状态，并写出一个通过条件。
  • 线性探测：在实验 2 中指出对应状态，并写出一个通过条件。
  • 散列表扩缩容：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“拉链平均链长 α=N/M；线性探测命中/未命中成本随 α→1 急剧上升”不是孤立结论？

问题 3：故障恢复。 怎样证明“键入表后发生可影响 hashCode 的变更，或删除线性探测槽位却不重建后续簇”已经修复？

本章回顾

  1. Hashing由index compression与collision resolution两部分组成，collision不可避免。
  2. Equal keys必须同hashCode，同hashCode的keys仍需equals消歧，key fields应immutable。
  3. Uniform hashing assumption支撑expected analysis，但不是对adversarial inputs的保证。
  4. Separate chaining把collision keys放入per-index linked ST，成本取决于N/M。
  5. Linear probing以null作为miss stop signal，成本对occupied fraction alpha极敏感。
  6. Cluster中间直接置null会让后继keys失联，official deletion会重新insert连续cluster。
  7. Capacity改变会改变index，resize必须rehash所有keys；hysteresis避免thrashing。
  8. Hash table提供expected constant unordered operations，不替代有worst-case log guarantee与ordered API的red-black BST。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…