hash table - hash map - 哈希表 - 散列表 - Java

hash：散列，杂凑，哈希
hash table，hash map：哈希表，散列表
hash function：哈希函数，散列函数
key-value pair，KVP：键值对

如果所有的键 (key) 都是数值较小的整数，我们可以用一个数组来实现无序的符号表，将键作为数组的索引而数组中键 i i i 处储存的就是它对应的值 (value)。这样我们就可以快速访问任意键 (key) 的值 (value)。散列表使用这种简易方法的扩展并能够处理更加复杂的类型的键。我们需要用算术操作将键转化为数组的索引来访问数组中的键值对 (key-value pair)。

使用散列的查找算法分为两步。第一步是用散列函数将被查找的键转化为数组的一个索引。理想情况下，不同的键都能转化为不同的索引值。我们需要面对两个或者多个键都会散列到相同的索引值的情况。散列查找的第二步就是一个处理碰撞冲突的过程。两种解决碰撞的方法：拉链法和线性探测法。

散列表的核心问题

key：键
hash：散列值
value：值
collision [kə'lɪʒ(ə)n]：n. 抵触，碰撞 (或相撞) 事故
crux [krʌks]：n. 症结

散列表是算法在时间和空间上折中的经典例子。如果没有内存限制，我们可以直接将键作为 (可能是一个超大的) 数组的索引，那么所有查找操作只需要访问内存一次即可完成。但这种理想情况不会经常出现，因为当键很多时需要的内存太大。另一方面，如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。我们不必重写代码，只需要调整散列算法的参数就可以在空间和时间之间取舍。

使用散列表，你可以实现在一般应用中拥有 (均摊后) 常数级别的查找和插入操作的符号表。这使得它在很多情况下成为实现简单符号表的最佳选择。

1. 散列函数

散列函数将键转化为数组的索引。如果我们有一个能够保存 M M M 个键值对的数组，那么我们就需要一个能够将任意键转化为该数组范围内的索引 ( [ 0 , M − 1 ] [0, M-1] [0,M−1] 范围内的整数) 的散列函数。我们要找的散列函数应该易于计算并且能够均匀分布所有的键，即对于任意键， 0 0 0 到 M − 1 M-1 M−1 之间的每个整数都有相等的可能性与之对应 (与键无关)。

散列函数和键的类型有关。对于每种类型的键我们都需要一个与之对应的散列函数。如果键是一个数，比如社会保险号，我们就可以直接使用这个数；如果键是一个字符串，比如一个人的名字，我们就需要将这个字符串转化为一个数；如果键含有多个部分，比如邮件地址，我们需要用某种方法将这些部分结合起来。

一个社会保险号含有 9 9 9 位数字并被分为三个部分，例如 123 − 45 − 6789 123-45-6789 123−45−6789。第一组数字表示该号码签发的地区 (例如，第一组号码为 035 035 035 的社会保险号来自罗得岛州， 214 214 214 则来自马里兰州)，另两组数字表示个人身份。社会保险号共有 10 10 10 亿 ( 1 0 9 10^9 109) 个，但假设我们的应用程序只需要处理几百个，我们可以使用一个大小 M = 1000 M=1000 M=1000 的散列表。散列函数的一种实现方法是使用键 (社会保险号) 中的三个数字。用第三组中的三个数字似乎比用第一组中的三个数字更好 (因为我们的客户不太可能完全平均地分布在各个地区)，更好的方法是用所有 9 9 9 个数字得到一个整数，然后再考虑整数的散列函数。

1.1 正整数

将整数散列最常用方法是除留余数法。我们选择大小为素数 M M M 的数组，对于任意正整数 k k k，计算 k k k 除以 M M M 的余数。这个函数的计算非常容易 (在 Java 中为 k k % M k) 并能够有效地将键散布在 0 0 0 到 M − 1 M-1 M−1 的范围内。如果 M M M 不是素数，我们可能无法利用键中包含的所有信息，这可能导致我们无法均匀地散列散列值。例如，如果键是十进制数而 M M M 为 1 0 k 10^k 10k，那么我们只能利用键的后 k k k 位，这可能会产生一些问题。假设键为电话号码的区号且 M = 100 M=100 M=100。由于历史原因，美国的大部分区号中间位都是 0 0 0 或者 1 1 1，因此这种方法会将大量的键散列为小于 20 20 20 的索引，但如果使用素数 97 97 97，散列值的分布显然会更好 (一个离 100 100 100 更远的素数会更好)，如右侧所示。互联网中使用的 IP 地址也不是随机的，如果我们想用除留余数法将其散列就需要用素数 (特别地，不是 2 2 2 的幂) 大小的数组。

除留余数法

1.2 浮点数

如果键是 0 0 0 到 1 1 1 之间的实数，我们可以将它乘以 M M M 并四舍五入得到一个 0 0 0 至 M − 1 M-1 M−1 之间的索引值。尽管这个方法很容易理解，但它是有缺陷的，因为这种情况下键的高位起的作用更大，最低位对散列的结果没有影响。修正这个问题的办法是将键表示为二进制数然后再使用除留余数法。

1.3 字符串

除留余数法也可以处理较长的键，例如字符串，我们只需将它们当作大整数即可。例如，右侧的代码就能够用除留余数法计算 String S 的散列值：

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

散列字符串键

Java 的 charAt() 函数能够返回一个 char 值，即一个非负 16 16 16 位整数。如果 R 比任何字符的值都大，这种计算相当于将字符串当作一个 N N N 位的 R R R 进制值，将它除以 M M M 并取余。一种叫 Horner 方法的经典算法用 N N N 次乘法、加法和取余来计算一个字符串的散列值。只要 R R R 足够小，不造成溢出，那么结果就能够如我们所愿，落在 0 0 0 至 M − 1 M-1 M−1 之内。使用一个较小的素数，例如 31 31 31，可以保证字符串中的所有字符都能发挥作用。 Java 的 String 的默认实现使用了一个类似的方法。

1.4 组合键

如果键的类型含有多个整型变量，我们可以和 String 类型一样将它们混合起来。例如，假设被查找的键的类型是 Date，其中含有几个整型的域：day (2 个数字表示的日)，month (2 个数字表示的月) 和 year (4 个数字表示的年)。我们可以这样计算它的散列值：

int hash = (((day * R + month) % M ) * R + year) % M;

只要 R R R 足够小不造成溢出，也可以得到一个 0 0 0 至 M − 1 M-1 M−1 之间的散列值。在这种情况下我们可以通过选择一个适当的 M M M，比如 31 31 31，来省去括号内的 % M 计算。和字符串的散列算法一样，这个方法也能处理有任意多整型变量的类型。

References

Algorithms (4th Edition), Robert Sedgewick and Kevin Wayne
https://algs4.cs.princeton.edu/home/
算法 (第 4 版)，Robert Sedgewick, Kevin Wayne (著) 谢路云 (译)
https://www.ituring.com.cn/book/875/