第1章　散列

散列在概率数据结构中扮演着核心角色，因为这些数据结构使用散列对数据进行随机化和紧凑表示。散列函数通过生成体量更小（在大多数情况下为固定大小）的标识符来压缩任意大小的输入数据块。生成的标识符又被称为散列值，或简称为散列。

散列函数的选择对于避免偏差至关重要。尽管对于散列函数的选择主要基于输入和特定用例，但为了方便选择，散列函数应该满足某些通用属性。

散列函数会压缩输入。因此，两个不同的数据块具有相同散列值的情况是不可避免的。这种现象又称为散列碰撞。

1979年，J.Lawrence Carter和Mark Wegman提出全域散列函数，即使输入数据是从全域中随机选择的，其数学特性仍可以保证散列值的期望碰撞次数很少。

全域散列函数族H将全域中的元素映射到范围{0,…,m-1}中，并通过从函数族中随机挑选散列函数的方式保证发生散列碰撞的概率是有界的：

因此，从满足性质(1-1)的函数族中随机选择一个散列函数完全等价于均匀随机地选择一个元素。

一个被用于整数散列的重要的全域散列函数族被定义为：

其中k和q是随机生成的模p的整数，且k≠0。p是一个素数且p≥m。通常情况下，p可从已知的梅森素数中进行选择。例如，若m=109，则我们选择p=M31=231-1≈2·109。

许多应用也使用函数族(1-2)的简化版本：

尽管函数族(1-3)仅仅具备近似全域性质，但其期望的散列碰撞概率仍然小于2/m。

然而，上述所有的散列函数族仅适用于整数散列。这对许多需要对变长的向量进行散列，且需要既能满足特定属性又快速可靠的散列函数的实际应用来说是不够的。

在实际应用中有许多种类的散列函数，其选择主要取决于它们的设计和特定应用场景。在本章中，我们对常用的散列函数和各种概率数据结构中普遍存在的简单数据结构进行概述。