散列表

散列表（hash table）是实现字典操作的一种有效的数据结构。当关键字的全域 \(U\) 比较小时，基于数组的直接寻址简单而有效。但如果全域 \(U\) 很大时，散列表需要的存储空间比直接寻址表小得多。

在直接寻址表中，具有关键字 \(k\) 的元素被放在槽 \(k\) 中。在散列表中，该元素则放在槽 \(h(k)\) 中，即利用散列函数(hash function) \(h\)，计算关键字 \(k\) 对应的槽的位置。函数 \(h\) 为全域 \(U\) 到散列表 \(T[0..m-1]\) 的映射：

\[ h:U\rarr\{0,1,\cdots,m-1\} \]

随之而来的问题是，两个关键字可能映射到同一个槽中，即发生冲突。一种简单的冲突解决方法是链表法，将散列到同一个槽中的所有元素放在一个链表中。

对于一个能存放 \(n\) 个元素、具有 \(m\) 个槽位的散列表，其装载因子（load factor） \(\alpha\) 定义为 \(n/m\)，即一个链的平均存储元素数。

散列函数

一个好的散列函数应（近似地）满足简单均匀散列假设：每个关键字都被等可能地散列到 \(m\) 个槽位中的任何一个，并与其他关键字已散列到哪个槽位无关。假定关键字的全域为自然数集 \(N=\{0,1,2,\cdots\}\)，如果不是，则需要找到一种方法将其转换为自然数。

除法散列法

通过取余，将关键字 \(k\) 映射到 \(m\) 个槽位上，即散列函数为：

\[ h(k)=k \bmod m \]

在应用除法散列法时，\(m\) 通常取一个不太接近 \(2\) 的整数幂的素数。

乘法散列法

用关键字 \(k\) 乘以常数 \(A(0\lt A\lt 1)\)，并取其小数部分，然后乘以 \(m\)，并向下取整，即散列函数为：

\[ h(k)=\lfloor m(kA-\lfloor{kA\rfloor})\rfloor \]

参考

• Cormeo T H, et al. 算法导论. 原书第 3 版. 第 11 章.