1. 散列简介¶
1.1. 引言¶
散列（hashing）是一种从数据库中存储和检索记录的方法。 它允许你根据查找键值来插入、删除和查找记录。 若实现得当，这些操作都可以在常数时间内完成。 事实上，一个调校良好的散列系统对于每次查找、插入或删除操作， 通常只会查看一两条记录。 这远优于在 \(n\) 条记录的有序数组上 做二分查找所需的 \(O(\log n)\) 平均代价， 也优于在二叉搜索树上做一次操作所需的 \(O(\log n)\) 平均代价。 然而，尽管散列基于一个非常简单的思想， 要正确实现它却出奇地困难。 设计者需要仔细关注实现散列系统所涉及的所有细节。
散列系统把记录存储在一个称为 散列表 的数组中，
我们将其记作 HT 。
散列的工作方式是：对查找键 K 执行某种计算，
以确定 HT 中存放键为 K 的那条记录的位置。
执行这一计算的函数称为
散列函数 ，
用字母 h 表示。
由于散列方案以满足地址计算需要为准则、以任意顺序放置记录，
所以记录并不是按值排序的。
散列表中的一个位置也称为一个 槽 。
散列表 HT 中槽的数量用变量 \(M\) 表示，
槽编号从 0 到 \(M-1\) 。
散列系统的目标是做出这样的安排：
对任意键值 K 和某个散列函数 \(h\) ，
\(i = \mathbf{h}(K)\) 是表中的一个槽，满足
\(0 <= i < M\) ，
并且存储在 HT[i] 处记录的键等于 K 。
对于允许多条具有相同键值的记录存在的应用，散列并不合适。
散列也不是回答范围查找的好方法。
换句话说，我们无法轻易找出所有键值落在某个范围内的记录（如果有的话）。
我们也无法轻易找出键值最小或最大的记录，或按键顺序访问记录。
散列最适合回答这样的问题："哪条记录（如果有的话）具有键值 K ？"
这称为 精确匹配查询 。
对于所有查找都通过精确匹配查询完成的应用，
散列是首选的查找方法，因为正确实现时它极为高效。
然而，正如本教程所示，散列有许多不同的实现途径，
很容易设计出低效的实现。
散列既适用于内存中的查找，也适用于基于磁盘的查找，
并且是用于组织存储在磁盘上的大型数据库的两种最广泛使用的方法之一
（另一种是 B 树）。
作为散列的一个简单（尽管不现实）的例子，
考虑存储 \(n\) 条记录，每条记录都有一个 0 到 \(n-1\) 范围内的唯一键值。
键为 k 的记录可以存储在 HT[k] 中，
因此散列函数为 \(\mathbf{h}(k) = k\) 。
要查找键值为 k 的记录，查看 HT[k] 即可。
在大多数应用中，键范围内的值远多于散列表中的槽数。 举一个更现实的例子，假设键可以取 0 到 65,535 范围内的任意值 （即键是一个双字节无符号整数）， 并且我们预计在任意时刻大约存储 1000 条记录。 在这种情况下，使用一个具有 65,536 个槽的散列表是不切实际的， 因为那样绝大多数槽都会被空置。 取而代之，我们必须设计一个能把记录存储到小得多表中的散列函数。 由于键范围大于表的长度， 至少有一些槽必须由多个键值映射而来。 给定散列函数 h 和两个键 \(k_1\) 与 \(k_2\) ，如果 \(\mathbf{h}(k_1) = \beta = \mathbf{h}(k_2)\) ， 其中 \(\beta\) 是表中的一个槽， 那么我们就说 \(k_1\) 和 \(k_2\) 在散列函数 h 下 在槽 \(\beta\) 处发生 冲突 。
在由散列组织的数据库中查找键值为 K 的记录，
遵循一个两步过程：
计算表位置 \(\mathbf{h}(K)\) 。
从槽 \(\mathbf{h}(K)\) 开始，使用（如有必要） 冲突消解 策略定位包含键
K的记录。
