第 12 章哈希¶

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

12.1 第一次尝试¶

目前所学结构的问题¶

到目前为止，我们已经学习了几种能够高效判断元素是否存在的数据结构：先是二叉搜索树，随后又用 2-3 树让它保持平衡。

不过，这些结构仍然存在限制——即使 2-3 树也不例外：

元素必须能够比较。向 BST 中插入元素时，必须回答“它比根结点小还是大？”对于某些对象，这个问题根本没有意义。
操作复杂度为 \(\Theta(\log N)\)。这已经很好，但也许还能更快。

第一次尝试：`DataIndexedIntegerSet`¶

我们先只解决第二个问题，把复杂度从 \(\Theta(\log N)\) 降到 \(\Theta(1)\)；暂时不处理“元素是否可比较”。事实上，我们目前只考虑存储和查询 int。

一种直接的想法是：创建一个长度为 20 亿的 boolean 数组，所有位置初始都是 false。

add(int x)：把数组第 x 个位置设为 true，耗时 \(\Theta(1)\)。
contains(int x)：直接返回数组第 x 个位置的值，同样耗时 \(\Theta(1)\)。

public class DataIndexedIntegerSet {
    private boolean[] present;

    public DataIndexedIntegerSet() {
        present = new boolean[2000000000];
    }

    public void add(int x) {
        present[x] = true;
    }

    public boolean contains(int x) {
        return present[x];
    }
}

看起来问题已经解决了，但实际上还有两个明显缺陷：

极其浪费空间。 若一个 boolean 占 1 字节，则每个实例都需要约 2 GB 内存，而用户可能只插入寥寥几个元素。
只能处理整数。 如果用户想插入 String，甚至 Dog，应该怎么办？

12.2 插入单词¶

DataIndexedIntegerSet 只能存整数。现在我们希望把字符串 "cat" 放进去，并把新结构称为 DataIndexedEnglishWordSet。

一个疯狂但自然的想法是：给每个字符串分配一个整数。例如 cat -> 1、dog -> 2、turtle -> 3。插入 cat 时把 present[1] 设为 true；查询时再把 cat 转成 1，并检查该位置。

问题是，我们无法提前手工为所有可能的单词编号。必须设计一种通用规则，将任意字符串转换成整数。

策略一：只使用首字母¶

可以把首字符转换为数字，例如：

cat -> c -> 3
dog -> d -> 4
drum -> d -> 4

dog 与 drum 被映射到相同整数。两个不同输入得到相同结果，称为一次冲突（collision）。我们暂时还不会处理冲突，因此先尝试避免冲突。

策略二：使用进位制避免冲突¶

十进制四位数 5149 可以写成：

\[5\cdot10^3+1\cdot10^2+4\cdot10^1+9\cdot10^0\]

任意四个十进制数字都能以这种方式得到唯一结果。这里的底数 10 非常关键，因为十进制恰好有十个数字 0 到 9。

若错误地使用底数 2，就会发生冲突：

\[1\cdot2^3+1\cdot2^2+1\cdot2^1+1\cdot2^0=15\]

\[0\cdot2^3+3\cdot2^2+1\cdot2^1+1\cdot2^0=15\]

英文字母表有 26 个小写字母。令 a=1, b=2, ..., z=26，就可以把小写英文单词写成 26 进制数。

例如：

\[\text{cat}=3\cdot26^2+1\cdot26^1+20\cdot26^0=2074\]

快速检查：你会如何表示 dog？

这种方法为每个仅由小写英文字母组成的单词给出唯一整数，就像十进制为每个数提供唯一表示一样，因此不会产生冲突。

`DataIndexedEnglishWordSet`¶

public class DataIndexedEnglishWordSet {
    private boolean[] present;

    public DataIndexedEnglishWordSet() {
        present = new boolean[2000000000];
    }

    public void add(String s) {
        present[englishToInt(s)] = true;
    }

    public boolean contains(String s) {
        return present[englishToInt(s)];
    }
}

辅助方法如下：

public static int letterNum(String s, int i) {
    /** 把字符串第 i 个字符转换为字母编号：
      * 'a' -> 1, 'b' -> 2, ..., 'z' -> 26。 */
    int ithChar = s.charAt(i);
    if (ithChar < 'a' || ithChar > 'z') {
        throw new IllegalArgumentException();
    }
    return ithChar - 'a' + 1;
}

public static int englishToInt(String s) {
    int intRep = 0;
    for (int i = 0; i < s.length(); i += 1) {
        intRep = intRep * 26;
        intRep += letterNum(s, i);
    }
    return intRep;
}

当前进展¶

最初的目标包括：

比 \(\Theta(\log N)\) 更快。对于整数和小写英文单词，我们已经做到了。
支持不可比较的对象。虽然目前只处理整数和单词，但算法从未依赖大小比较，因此方向是正确的。
支持任意字符串，包括空格、其他语言和 emoji。
解决巨大的空间浪费问题。

后两个问题仍然没有解决。

12.3 插入任意字符串与整数溢出¶

超越单个英文单词¶

ASCII 字符表

ASCII 为每个字符分配了整数编号，最大编码大约为 126。因此，可以把任意 ASCII 字符串看成以 126 为底的数字：

public static int asciiToInt(String s) {
    int intRep = 0;
    for (int i = 0; i < s.length(); i += 1) {
        intRep = intRep * 126;
        intRep = intRep + s.charAt(i);
    }
    return intRep;
}

若要支持中文，字符编号范围会更大，底数也必须相应增大。

仅仅存储一个三个汉字的词，理论上就可能需要超过 39 万亿 个数组位置。这显然不可行。

整数溢出与哈希码¶

溢出问题¶

Java int 的最大值是 2,147,483,647，最小值是 -2,147,483,648。最大值再加 1 会回绕到最小值。

即使只处理 ASCII，数值也很快超过 int 的范围。例如：

\[\text{omens}_{126}=28,196,917,171\]

但 asciiToInt("omens") 实际会返回溢出后的负数。

更糟糕的是，不同字符串可能因为溢出得到同一个结果。例如某些完全不同的长字符串会被映射到相同整数。于是插入其中一个后，查询另一个也可能错误地返回 true。

无法逃避的事实¶

Java 中一共只有 \(2^{32}=4,294,967,296\) 个不同的 int 值，但能够创建的对象数量远远超过这个数。因此，不论转换算法多么聪明，冲突都不可避免。

我们必须正面处理冲突。

一个细微但重要的区别¶

问题并不是“溢出本身使我们无法把字符串转成整数”。溢出之后，我们仍然得到了一个整数。真正的问题是：溢出导致不同对象产生相同整数，而我们目前不会处理这种冲突。

哈希码¶

在计算机科学中，把一个对象转换为整数的过程称为计算对象的哈希码（hash code）。

对于其他对象，通常有两种做法：

使用 Java 为所有对象提供的 .hashCode() 方法。
为自己的类重写 hashCode()。例如，可以组合 Dog 的名字、年龄和品种来计算哈希码。

哈希码的性质¶

一个有效的哈希码必须满足：

结果是整数。
对同一个未改变的对象多次调用 .hashCode()，结果必须相同。
若两个对象通过 .equals() 被认为相等，则它们必须拥有相同哈希码。

一个好的哈希函数还应尽量让不同对象均匀分布到不同整数上。

到这里，我们已经能够为任意对象计算哈希码，而不再局限于字符串。

尚未解决的问题¶

空间仍然过于庞大。
已经证明冲突不可避免，但还没有真正处理它。

12.4 处理冲突¶

现在正面处理冲突。核心思路是：数组的每个位置不再只存一个元素，而是存放一个元素列表，例如 LinkedList。

数组最初全部为空。若新元素的哈希码为 \(h\)：

若索引 \(h\) 处为空，就创建一个新的 LinkedList，并把元素加入其中。
若索引 \(h\) 已经有列表，就先在列表中检查该元素是否存在；不存在时再追加。集合不能包含重复元素，因此不能跳过这次检查。

这种做法称为拉链法（separate chaining）。

具体流程¶

`add(item)`¶

计算元素的哈希码，也就是目标索引。
若该索引为空，创建列表并加入元素。
若已有列表，遍历检查元素是否已存在；不存在时加入。

`contains(item)`¶

计算元素的哈希码。
若对应索引为空，返回 false。
否则遍历该索引上的列表；找到元素则返回 true。

运行时间¶

若目标桶中的链表长度为 \(Q\)，那么 contains 需要检查最多 \(Q\) 个元素，耗时 \(\Theta(Q)\)。

add 也需要 \(\Theta(Q)\)。虽然链表头插只需 \(\Theta(1)\)，但插入前仍必须确认元素没有重复。

有得有失¶

冲突问题已经解决。
空间问题还没有解决。
最坏情况下，所有元素可能拥有相同哈希码，全部落入一个长度为 \(N\) 的链表，因此操作仍可能退化为 \(\Theta(N)\)。

解决空间问题¶

既然我们已经能够处理冲突，就没有必要保留几十亿个数组位置。可以只创建一个较小的数组，例如长度 100，然后把哈希码取模：

int index = Math.floorMod(item.hashCode(), 100);

这样，任意哈希码都会被压缩到 0 到 99。冲突会增加，但我们已经有链表来处理它。

代价是：原本分布在数十亿个索引上的元素现在被压缩到 100 个桶，桶中的链表会更长。

当前状态¶

空间问题：已解决。
冲突问题：已解决。
性能问题：仍需改善，因为桶中的链表可能很长。

12.5 哈希表与性能修正¶

最终结构：`HashTable`¶

目前构造出的数据结构就是哈希表：

哈希函数把输入对象转换为整数哈希码。
对哈希码取模，得到合法数组索引。
把元素放入该索引对应的链表，并用链表处理冲突。

contains 的过程类似：计算索引，然后在对应桶的链表中查找元素。

处理运行时间问题¶

假设哈希表有 5 个桶、100 个元素：

最理想时，元素均匀分布，每个桶约有 20 个元素。
最坏时，所有元素都进入同一个桶，该桶有 100 个元素。

可以从两个方向改善：

动态扩容哈希表。
设计更好的哈希函数。

动态扩容¶

设桶数为 \(M\)，元素数为 \(N\)，定义负载因子（load factor）为：

\[\text{load factor}=\frac{N}{M}\]

若 \(M\) 固定而 \(N\) 不断增长，负载因子也会不断增大。常见策略是设置一个负载因子阈值；超过阈值后，把桶数扩大一倍。

扩容步骤：

创建一个拥有 2M 个桶的新哈希表。
遍历旧表中的所有元素，逐个重新插入新表。

必须重新插入，而不能直接复制桶，因为模数变了，元素对应的索引也可能改变。例如哈希码 13：

在 4 个桶中：\(13\bmod4=1\)
在 8 个桶中：\(13\bmod8=5\)

在元素近似均匀分布的前提下，每个桶约有 \(N/M\) 个元素，操作时间为 \(\Theta(N/M)\)。由于负载因子被一个常数阈值限制，因此：

\[\Theta(N/M)=\Theta(1)\]

扩容本身需要重新处理 \(N\) 个元素，所以耗时 \(\Theta(N)\)。不过扩容并不会每次插入都发生；结合几何扩容，其平均摊还成本仍可保持常数级。

重新散列时，我们已经知道旧表中不存在重复元素，因此可以省略“是否已存在”的检查，直接把元素插入桶头。

更好的哈希码¶

上述常数时间分析依赖于一个关键假设：元素能够较均匀地分布在桶中。若哈希函数很差，所有元素仍可能进入同一个桶，操作就会退化为 \(\Theta(N)\)。

设计哈希函数的一些经验：

使用与前文类似的“进位制”累积策略。
底数通常选择较小的质数。
像 126 这样的底数可能与整数溢出的周期产生不良规律，让许多不同字符串得到同样的哈希码。
质数有助于减少这类规律性冲突，同时较小的质数计算成本低。

总结¶

我们从零逐步构造出了哈希表：

哈希码把任意对象映射为整数。
取模控制数组大小。
拉链法处理冲突。
动态扩容控制负载因子。
良好的哈希函数让元素尽可能均匀分布。

在合理假设下，哈希表的插入和查询可达到摊还 \(\Theta(1)\)。

下一步可完成课程作业 HW3。

第 12 章 哈希¶