1.3　散列表

散列表是一种字典数据结构，由长度为m的无序关联数组组成。其条目称为桶，并使用{0,1,…,m-1}范围内的键作为索引。要将元素插入散列表中，需要一个散列函数用于计算键，该键用于选择适当的桶对元素进行存储。

通常，包含所有输入元素的全集的规模要比散列表的容量m大得多。因此，键的碰撞是不可避免的。另外，当散列表中元素的数量增加时，碰撞的数量也会增加。

散列表的关键概念是负载因子α，即已使用键的数量n与表的总长度m之比：

负载因子是散列表的填充程度的一种度量，并且由于n不能超过散列表的容量，因此它的上限为1。当α接近其最大值时，碰撞的可能性会大大增加，这可能需要增加散列表的容量。

所有散列表的实现都需要解决碰撞问题，并提供有关如何处理冲突的策略。主要有两种技术：

·封闭寻址——将碰撞的元素存储在辅助数据结构中的相同键下。

·开放寻址——将碰撞的元素存储在首选位置以外的其他位置，并提供一种寻址方法。

封闭寻址技术是解决碰撞的最简单的方法。封闭寻址有许多不同的实现方法，例如，在链表中存储碰撞元素的分离链接法，使用特殊散列函数和不同长度的辅助散列表的完美散列法。

除了以任何一种形式创建辅助数据结构外，还可以通过将碰撞的元素存储在主表中的其他位置并设计相关寻址算法来解决碰撞。由于在一开始该存储元素的地址是未知的，因此该技术被称为开放寻址，又称开放定址。

现在，我们将介绍在本书列出的概率数据结构中两个有用的开放寻址实现方法。

（1）线性探测

使用开放寻址的最直接的散列表实现方法之一是线性探测算法，该算法由Gene Amdahl、Elaine M.McGraw和Arthur Samuel于1954年提出。Donald Knuth于1963年对其进行分析。线性探测算法的思想是将碰撞元素放入下一个空桶中。它的名称源于如下事实：因为我们一个接一个地探查另一个桶，所以元素的最终位置为以首选桶为起点的线性偏差。

线性探测散列表可以看作将索引值存储在桶中的环形数组。要想插入一个新元素x，我们使用一个散列函数h计算其密钥k=h(x)。如果对应于该键的桶非空，并且包含不同的值（即发生碰撞），则我们将继续沿顺时针方向查看下一个桶，直到找到可以索引元素x的可用空间。通过检查散列表的负载因子可以保证我们肯定会在某个时候找到可用空间。

类似地，当我们要查找某个元素x时，我们使用相同的散列函数h计算其密钥k，并开始顺时针检查桶。从首选桶开始，键为k=h(x)，直到找到所需元素x，否则若出现第一个空桶，则表明该元素不在散列表中。

例1.1　线性探测

考虑下述的线性探测场景，散列表的长度m=12，散列函数是将全域映射到{0,1,…,m-1}范围的32比特MurmurHash3：

假定要将以red开始的不同颜色的名字存储在散列表中。当前元素对应的散列函数的值计算如下：

h=h(red)=2 352 586 584 mod 12=0

由于起初线性探测的散列表是空的，键k=0的桶不包含任何元素，因此我们就仅仅将元素进行下述的索引：

接下来我们考虑元素green，其散列值为：

h=hash(green)=150 831 125 mod 12=5

由于键k=5对应的桶是空的，所以将其存储在该桶中。

现在考虑元素white，其散列值为

h=h(white)=16 728 905 mod 12=5

该元素的首选桶是键k=5的桶。该桶目前已被其他的元素占用，这意味着出现了碰撞。在这种情况下，我们采用线性探测算法，并尝试从首选桶开始以顺时针方向寻找下一个空桶。幸运的是，下一个键k=6的桶是空的，所以将white元素存储在此处。

当我们在线性探测散列表中查找元素white时，首先会查询该元素的键k=5对应的桶。由于该首选桶包含的元素和待查询元素white不同，所以我们沿顺时针方向从键为k+1=6的桶出发开始探测。幸运的是，键k=6的桶包含了所需查询的元素white，所以我们可以得到元素white存在于散列表中的结论。

只要线性探测散列表未被填满（负载因子严格小于1），该算法的每次操作就只需要O(1)的时间复杂度，并且线性探测的最长探测序列的期望长度的复杂度为O(logn)。

线性探测算法对散列函数h的选择非常敏感，因为它必须提供理想的均匀分布才能达到预期性能。但是实际上，这是不可能的，并且算法的性能会随着实际分布的发散而迅速降低。为了解决该问题，多种增加随机化的技术被广泛采用。

（2）布谷散列

开放寻址的另一种实现方法是布谷散列，它由Rasmus Pagh和Flemming Friche Rodler于2001年提出，并于2004年发布［Pa04］。该算法的主要思想是使用两个而不是一个散列函数。

布谷散列表是一个桶数组，其中的每个元素由两个不同的散列函数分别定位到两个候选桶，而不像线性探测或是其他算法中那样仅包含一个候选桶。

要想在布谷散列表中为新元素x建立索引，我们使用散列函数h1和h2计算两个候选桶的键。如果这两个候选桶中至少有一个为空，则将该新元素添加到空桶中。否则，我们将随机选择其中一个桶，并将元素x存储在该桶中，同时将存储在该桶中的旧元素移动至其另一个候选桶中。重复上述过程，直到找到一个空桶对元素进行存储，或是达到最大移动次数时算法停止。如果没有空桶，则散列表被视为已满。

尽管布谷散列算法可能会执行一系列的移动操作，但是它仍然可以在常数时间复杂度O(1)内完成。

查找过程则比较直接，并可以在常数时间复杂度内完成。我们只需要通过计算输入元素的散列值h1和h2就可以确定该元素的候选桶，最终检查这两个桶中是否存在待查元素。删除过程则可以以类似的方式执行。

例1.2　布谷散列

考虑下述条件，布谷散列表的长度m=12，以及输出键的取值范围在{0,1,…,m-1}的两个32比特的散列函数MurmurHash3、FNV1a：

与例1.1类似，以元素red开始，我们在散列表中为颜色的名字建立索引。通过散列函数得到的两个候选桶的键为：

h1(red)=23 525 865 848 mod 12=0

h2(red)=1 089 765 596 mod 12=8

当前布谷散列表为空，所以我们使用候选桶的其中一个即可，例如在键k=h1(red)=0的桶中为元素建立索引。

接下来，我们对元素black建立索引，其对应的候选桶的键分别为h1(black)=6和h2(black)=12。由于键k=0的桶中已存储其他元素，因此只能在键k=6的空桶上为black元素建立索引。

类似地，我们将元素silver添加到散列表中。该元素对应的候选桶的键分别为h1(silver)=5和h2(silver)=0。因为键k=0对应的桶已满，则只能将silver元素添加到键k=5的空桶中进行存储。

接下来分析元素white的添加过程。该元素对应的散列值分别为：

h1(white)=16 728 905 mod 12=5

h2(white)=3 724 674 918 mod 12=6

此时，元素white对应的两个候选桶中均存在其他元素，所以我们需要根据布谷散列算法机制进行移动操作。首先，随机挑选两个候选桶中的一个，比如键k=5的桶。然后将元素white添加到该桶中进行存储。接下来需要对原本存储在键k=5的桶中的元素silver进行移动操作，将其移动至其键k=0的候选桶中。此时，键k=0的桶也非空，因此在键k=0的桶中存储silver，并将原本存储的元素red移动至其另一个候选桶中。幸运的是，red键k=8的候选桶是空的，所以将red添加到该桶中。至此，元素white的添加过程完毕。

例如，当我们想对元素silver进行查询时，需要先根据散列函数得到其候选桶，分别是键k=5和键k=0的桶。由于在这个例子中，键k=0的桶包含待查询元素silver，所以可以得出元素silver在布谷散列表中的结论。

布谷散列能够保证较高的空间占用率，但要求其散列表的长度略大于存储所有元素所需的长度。我们将在下一章中详细介绍布谷过滤器，这是布谷散列算法在概率数据结构上的变体。