散列表 算法导论

说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！

在很多应用中，都要用到一种动态集合结构，它仅支持INSERT、SEARCH、DELETE字典操作。实现字典的一种有效数据结构为散列表。在最坏情况下，在散列表中，查找一个元素的时间与在链表中查找一个元素的时间相同，在最坏情况下都是Θ(n)，但在实践中，散列技术的效率是很高的。在一些合理的假设下，在散列表中查找一个元素的期望时间为O(1)。

散列表是普通数组概念的推广，因为可以对数组进行直接寻址，故可以在O(1)时间内访问数组任意元素。1节进一步讨论直接寻址问题：如果存储空间允许，我们可以提供一个数组，为每个可能的关键字保留一个位置，就可以使用直接寻址技术。

当实际存储的关键字数比可能的关键字总数小时，采用散列表就会较直接数组寻址更为有效，因为散列表通常采用的数组尺寸与所要存储的关键字数是成比例的，而数组此时使用数组会浪费空间。在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标，即散列函数。2节介绍这种技术的主要思想，着重介绍解决“碰撞”的“链接”技术。所谓碰撞，就是指多个关键字映射到同一个数组下标位置。3节介绍如何利用散列函数，根据关键字计算数组的下标；另外，还将讨论散列技术的几种变形。4节介绍“开放寻址法”，它是处理碰撞的另一种方法。5节解释当待排序的关键字集合是静态的（即当关键字集合一旦存入后不再改变），“完全散列”如何能够在O(1)最坏情况时间内支持关键字查找。

散列表是一种及其有效和实用的技术：基本的字典操作只需要O(1)的平均时间。

散列表的主要思想就是寻址，1--3节使读者全面认识散列表，但它是直接寻址思想下的散列表；4节介绍另一种寻址思想：开放寻址，然后4--5节使读者认知开放寻址思想下的散列表。需要注意的是不同的寻址方式，其处理碰撞的方式是不同的。==>这是我对本章的认知。

1、直接寻址表

当关键字的全域U比较小时(因为全域U很大时数组占用栈空间太大)，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都取自全域U= { 0， 1， …，m- 1 }，并假设元素的关键字各不相同。

可以用数组（或称直接寻址表）T[ 0 ..m- 1 ]表示动态集合，其中每个位置（或称槽）对应全域U中的一个关键字。下图说明了这个方法；槽k指向集合中关键字为k的元素。如果该集合中没有关键字为k的元素，则T[k] = NIL 。

几个字典操作也很简单：

DIRECT-ADDRESS-SEARCH(T, k)

1 return T[k]

DIRECT-ADDRESS-INSERT(T, x)

1 T[x.key] = x

DIRECT-ADDRESS-DELETE(T, x)

1 T[x.key] = NIL

显而易见，这些操作执行起来只需O( 1 )的时间。

2、散列表

直接寻址技术有一个明显的问题：如果全域U很大，那么在内存中存储大小为 |U| 的一张表T就有点不实际，甚至是不可能。还有，实际要存储的关键字集合K相对于U来说可能很小，那么因而分配给T的大部分空间都要浪费掉。

当存储在字典中的关键字集合K比所有可能的关键字域U要小很多时，散列表需要的存储空间要比直接寻址表少很多。特别地，在保持仅需O( 1 )时间即可在散列表中查找一个元素的好处的情况下，存储要求可以降至Θ( |K| )。唯一的问题是这个界是针对平均时间的，而对直接寻址来说，它对最坏情况也成立。

在直接寻址方式下，具有关键字k的元素被存放在槽k中。在散列方式下，该元素处于h(k)中，亦即，利用散列函数h，根据关键字k计算出槽的位置。函数h将关键字域U映射到散列表T[ 0 ..m- 1 ]的槽位上：

h:U→ { 0， 1， …，m- 1 }

这时，可以说一个具有关键字k的元素被散列到槽h(k)上，或者说h(k)是关键字k的散列值。下图给出了形象的说明。采用散列函数的目的就在于缩小需要处理的下标范围，即我们要处理的值从 |U| 降到m了，从而相应地降低了空间开销。

这样做有一个问题：两个关键字可能映射到同一个槽上。这种情形称为碰撞（collision）。当然，最理想的解决方案是完全避免碰撞。要做到这一点，可以考虑选用合适的散列函数h。在选择时的一个主导思想，就是使h尽可能的“随机”，从而避免或者最小化碰撞。实际上，术语“散列”即体现了这种精神。（当然，一个散列函数h必须是确定的，即某一给定的输入k应始终产生相同的结果h(k)。）但是，由于 |U| >m，故必然有两个关键字的散列值相同，所以想要完全避免碰撞时不可能的。那么，我们一方面可以通过精心设计的随机散列函数来尽量减少碰撞，另一方面仍需要有解决有可能出现的碰撞的办法。

本节余下部分介绍一种最简单的碰撞解决技术，称为链接法。第4节介绍另一种碰撞解决办法，称为开放寻址法。

2.1、链接法解决碰撞

链接法是一种最简单的碰撞解决技术。在链接法中，把散列到同一槽中的所有元素都放在一个链表中。如下图所示，槽j中有一个指针，它指向由所有散列到j的元素构成的链表的头：如果不存在这样的元素，则j中为 NIL 。

相应操作如下：

CHAINED-HASH-INSERT(A, x)

1 insert x at the head of list T[h(x.key)]

CHAINED-HASH-SEARCH(T, k)

1 search for an element with key k in list T[h(k)]

CHAINED-HASH-DELETE(T, x)

1 delete x from the list T[h(x.key)]

插入操作的最坏情况运行时间为O(1)。插入过程要快一些，因为假设要插入的元素x没有出现在表中；如果需要，在插入前执行搜索，可以检查这个假设(付出额外代价)。查找操作的最坏情况运行时间与表的长度成正比。如果问题中的链表是双向链表，则删除一个元素x的操作可以在O(1)时间内完成(注意，此时CHAINED-HASH-DELETE以元素x而不是它的关键字k作为输入，所以无需先搜索x。如果表是单链表，用元素x而不是关键字k作为输入，将不会有很大帮助。我们依然必须寻找T[h(x.k))中的x，所以通过适当的设置x的前趋next链，把x排除在连接之外。在这种情况下，搜索和插入的运行时间基本相同。

2.2、链接法散列的分析

给定一个能存放n个元素的，具有m个槽位的散列表T，定义T的装载因子（load factor）α为n / m，即一个链中平均存储的元素数。我们的分析以α来表达，α可以小于，等于或大于 1 。

用链接法散列的最坏情况性能很差：所有的n个关键字都散列到同一个槽中，从而产生出一个长度为n的链表。这时，最坏情况下查找的时间为Θ(n)，再加上计算散列函数的时间，这么一来就和用一个链表来链接所有的元素差不多了。显然我们并不是因为散列表的最坏情况性能才用它的。(第5节中介绍的完全散列能够在关键字集合为静态时，提供比较好的最坏情况性能。)

散列方法的平均性态依赖于所选取的散列函数h，在一般情况下将所有的关键字分布在m个槽位上的均匀程度。第3节散列函数中讨论了这些问题，此时我们先假设任何元素散列到m个槽中每一个槽的可能性都是相同的，且与其他元素已被散列到什么位置上是独立无关的。称这个假设为简单一致散列（simple uniform hashing）。

对于j= 0， 1， …，m- 1，列表元素T[j]所指向的链表的长度用nj表示，这样有：

n=n0+n1+ … +nm1

nj的平均值为E[nj] =α=n / m。

假定可以在O( 1 )时间内算出散列值h(k)，从而查找具有关键字k的元素的时间线性地依赖于表T[h(k)]的长度nh(k)(说明，此处h(k)为n的下标)。先不考虑计算散列函数和寻址槽h(k)的O( 1 )时间，只看为比较元素的关键字是否为k而检查的表T[h(k)]中的元素数。共有两种情况：查找成功，即表中没有一个元素的关键字为k；查找不成功，即表中具有关键字为k的元素。

定理：对一个用链接技术来解决碰撞的散列表，在简单一致散列的情况下，一次不成功查找的期望时间为Θ( 1 +α)。

定理：在简单一致散列的假设下，对于用链接技术解决碰撞的散列表，平均情况下一次成功的查找需要Θ( 1 +α)。

这一结论说明，如果散列表中槽数至少与表中的元素数成正比，则有n=O(m)，从而α=n / m=O(m) /m=O( 1 )。即平均来说，查找操作需要常量时间。又知道插入操作和删除操作在最坏情况下都需要O( 1 )时间。因而，全部的字典操作平均情况下都可以在O( 1 )时间内完成。

2.3、散列函数：根据关键字计算下标

本节我们要讨论一些有关如何设计出好的散列函数的问题，并介绍三种设计方案。其中两种方案(用除法进行散列、用乘法进行散列)从本质上来看，都是启发式的方式(启发式意味着就是启发读者学习的，实用性不大)。第三种方案(全域散列)则利用了随机化的技术，来提供可证明的良好性能。

一个好的散列函数应（近似地）满足简单一致散列的假设：每个关键字都等可能地散列到m个槽位的任何一个之中去，并与其他的关键字已被散列到哪一个槽位中无关。不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。

    有时，我们偶尔也能知道关键字的概率分布。例如，如果已知各关键字都是随机的实数k，他们独立、一致地分布于范围0<=k<1中，那么散列函数h(k)=⎣km⎦就能满足简单一致散列这一假设条件。

    在实践中，常常可以运用启发式技术来构造性能好的散列函数。在设计过程中，可以利用有关关键字分布的限制性信息。例如，一个编译器的符号表中，关键字都是字符串，表示程序中的标示符。在同一个程序中，经常会出现一些很相近的符号，如pt和pts。一个好的散列函数应能最小化将这些相近符号散列到同一个槽中的可能性。

一种好的做法是以独立于数据中可能存在的任何模式的方式导出散列值。例如，“除法散列”用一个特定的质数来除所给的关键字，所得到的余数即为该关键字的散列值。假定所选则的质数与关键字分布中的任何模式都是无关的。这种方法常常可以给出很好的效果。

    最后请注意，散列函数的某些应用可能会要求比简单一致散列更强的性质。例如，我们可能希望某些很近似的关键字具有截然不同的散列值(当使用第4节中将定义的线性探查技术时，这一性质是特别有用的)。2.3.3节将介绍的全域散列通常能够提供这些性质。

2.3.0、将关键字解释为自然数

多数散列函数都假定关键字域为自然数集N={ 0， 1， … }。如果所给关键字不是自然数，则必须有一种方法来将他们解释为自然数。例如，一个字符串关键字可以被解释为按适当的基数记号表示的整数。这样，标示符pt可以被解释为十进制整数对(112,116)，因为在ASCII字符集中，p=112，t=116.然后，按128为基数来表示，pt即为112*128+116=14 452。在任一给定的应用中，通常都比较容易设计出类似的方法，来将每个关键字解释为一个(可能很大)自然数。在后面的内容中，假定所给的关键字都是自然数。

2.3.1、除数散列法

在用来设计散列函数的除数散列法中，通过取k除以m的余数，来将关键字k映射到m个槽的某一个中去。亦即，散列函数为：h(k) =kmodm

当应用除数散列时，要注意m的选择。例如，m不应是2的幂，因为如果m等于2的p次幂，则h(k)就是k的p个最低位数字。除非我们事先知道光剑子的概率分布使得k的各种最低p位的排列形式的可能性相同，否则在设计散列函数时，最好考虑关键字的所有位的情况。

可选的m值通常是与 2 的整数幂不太接近的质数。

2.3.2、乘法散列法

构造散列函数的乘法散列法包含两个步骤。第一步，用关键字k乘上常数A（0 <A< 1），并抽取出k A的小数部分。然后，用m乘以这个值，再取结果的底（floor）。散列函数为：

h(k) = FLOOR(m(k Amod 1 ))

乘法方法的一个优点是对m的选择没有什么特别的要求，一般选择它为 2 的幂（m=2p，p为某个整数）。

    虽然乘法散列对任何的A值都适用，但某些值效果更好。最佳的选择与待散列的数据的特征有关，不过Knuth认为A=0.618 033 988 7...就是个比较理想的值。

2.3.3、全域散列

任何的散列函数都可能出现最坏情况性态，即n个关键字都散列到同一个槽中，使得平均的检索时间为Θ(n)：唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字，这种方法称作全域散列（universal hashing）。不管面对什么情况，其平均性态都很好。

全域散列的基本思想是在执行开始时，就从一族仔细设计的函数中，随机地选择一个作为散列函数。就像在快速排序中一样，随机化保证了没有哪一种输入会始终导致最坏情况性态。同时，随机化使得即使是对同一个输入，算法在每一次执行时的性态也是不一样的。这样就可以确保对于任何输入，算法都具有良好的平均情况性态。再来看看编译器中符号表的例子，我们发现在全域散列方法中，程序员对标示符的选择就不会一致的导致较差的散列性能了。仅当编译器选择了一个随机的散列函数，使得标示符的散列效果较差时，才会出现较差的性能，但是，出现这种情况的概率很小，并且这一概率对任何相同大小的标示符集来说都是一样的。

设H为有限的一组散列函数，它将给定的关键字域U映射到{ 0， 1， …，m- 1 }个槽中。这样的一组函数称为是全域的（universal），如果对任意一组不同的关键字k，l∈U，从H中选定某一hash函数h，映射到同一个slot中，即满足h(k) =h(l)的散列函数h∈H的个数至多为 |H| /m。换言之，如果从H中随机选择一个散列函数，此时概率为1 / |H|，当关键字k≠l时，这个散列函数h使两个元素发生碰撞的概率最大为(1 / |H|) * (|H| /m)，即碰撞的概率不大于 1 /m。

定理：如果h选择一组全域的散列函数，并用于将n个关键字散列到一个大小为m的，用链接法解决碰撞的表T中。如果关键字k不在表中，则k被散列至其中的链表的期望长度E[nh(k)]至多为α。如果关键字k在表中，则包含关键字k的链表的期望长度E[nh(k)]至多为 1 +α。注意α=n / m

推论：对于一个具有m个槽位的表，利用全域散列和链接法解决碰撞，需要Θ(n)的期望时间来处理任何包含了n个 INSERT ， SEARCH ， DELETE 操作的操作序列，该序列中包含了O(m)个 INSERT 操作。

    说明：刚开始看的时候我还以为每次插入一个关键字时都要随机选择函数，但是这样就没法查找关键字了，想了一个晚上想不出来，怀疑智商了，看了网上的代码，发现在最初执行的时候，从散列集合中随机选取一个散列函数h后，就把固定使用h函数作为散列函数了....

3、开放寻址法

在开放寻址法（open addressing）中，所有的元素都存放在散列表中。亦即，每个表项或包含动态集合的一个元素，或包含 NIL 。当查找一个元素时，要检查所有的表项，直到找到所需的元素，或最终发现该元素不在表中。不像在链表法中，这没有链表，也没有元素存放在散列表外。在这种方法中，散列表可能会被填满，以至于不能插入任何新的元素，但该方法的装载因子α绝对不会超过 1 。

当然，也可以将用作链接的链表存放在散列表未用的槽中，但开放寻址法的好处就在于它根本不用指针，而是计算出要存取的各个槽。这样一来由于不用存储指针而节省了空间，从而可以用同样的空间来提供更多的槽，其潜在的效果就是可以减少碰撞，提高查找速度。

在开放寻址法中，当要插入一个元素时，可以连续地检查（或称探查）散列表的各项，直到找到一个空槽来放置待插入的关键字为止。检查的顺序不一定是 0， 1， …，m- 1 （这种顺序下的查找时间为Θ(n)），而是要依赖于待插入的关键字。为了确定要探查哪些槽，应该将散列函数的参数加以扩充，除关键字外，将探查号（从 0 开始）作为第二个输入参数。这样，散列函数就变为：

h:Uⅹ { 0， 1， …，m- 1 } → { 0， 1， …，m- 1 }

对开放寻址法来说，要求对每一个关键字k，探查序列

<h(k， 0 )，h(k， 1 )， …，h(k，m- 1 ) >

必须是< 0， 1， …，m- 1 >的一个排列，使得当散列表逐渐填满时，每一个表位最终都可以被视为用来插入新关键字的槽。在下面的伪代码中，假设关键字k就是带插入的元素：

HASH-INSERT(T, k)

1  i = 0

2  repeat  j = h(k, i)

3      if T[j] == nil

4          T[j] == k

5          return j

6      else

7          i = i + 1

8 until i == m

9 error "hash table overflow"

    查找关键字k的算法的探查序列与将k插入时的插入算法是一样的。当在查找的过程中碰到一个空槽时，查找算法就停止，因为如果k确实在表中的话，也应该在该处，而不是探查序列的稍后位置上(之所以这么说，是因为我们假定了关键字不会被删除)。过程HASH-SEARCH的输入为一个散列表T和一个关键字k，如果槽j中包含关键字k，则返回j；如果k不在表T中，则返回nil。

HASH-SEARCH(T, k)

1 i = 0

2 repeat   j = h(k, i)

4     if T[j] == k

5         return j

6     i = i + 1

7 until T[j] == NIL or i == m

8 return NIL

在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将 NIL 置于其中来标识它为空。否则就会有个问题：在插入某关键字k的探查过程中，发现i被占用了，则k被插入到后面的位置上。在将槽i中的关键字删除后，就无法检索关键字k了。有一个解决的办法就是在槽i中置一个特定的值 DELETED ，而不用 NIL 。这样要对过程 HASH-INSERT 作相应的修改，使之将这样的一个槽当作一个空槽，从而仍然可以插入新的元素。对HASH-SEARCH无需做什么改动，因为它在搜索时会绕过DELETED标识。但是，当使用特殊值 DELETED 时，查找时间就不再依赖于装载因子α了，因此，在必须删除关键字的应用中，往往采用链接法来解决碰撞！！！！！！！！！！！。而且，我认为删除多次以后，大多元素都不在h(k， i)初始计算出的位置上，查找速度会越来越慢，所以“在必须删除关键字的应用中，往往采用链接法来解决碰撞”这个结论我认为很正确！！！

在我们的分析中，作了一个一致散列的假设，即假设每个关键字的探查序列是< 0， 1， …，m- 1 >的m!种排列中的任一种的可能性是相同的。一致散列将前面定义过的简单一致散列的概念加以一般化，推广到散列函数的结果不只是一个数，而是一个完整的探查序列的情形。然而，真正的一致散列是很难实现的，在实践中，常常采用它的一些近似方法，如下面介绍的线性探查，二次探查，以及双重散列。

在实践中，常用三种技术来计算开放寻址法中的探查序列：线性探查，二次探查，以及双重散列。这几种技术都能保证对每个关键字k，<h(k， 0 )，h(k， 1 )， …，h(k，m- 1 ) >都是< 0， 1， …，m- 1 >的一个排列。但是这些技术都不能实现一致散列的假设，因为他们能产生的不同探查序列数都不超过m*m个。在这三种技术中，双重散列能产生的探查序列最多，因而能给出最好的结果。

3.1、线性探查

给定一个普通的散列函数h' :U→ { 0， 1， …，m- 1 }（称为辅助散列函数），线性探查（linear probing）方法采用的散列函数为：h(k，i) = (h'(k) +i) modm，i= 0， 1， …，m- 1

给定一个关键字k，第一个探查的槽是T[h'(k) ]，亦即，由辅助散列函数所给出的槽。接下来探查的是槽T[h' (k) + 1 ]， …，直到槽T[m- 1 ]，然后又卷绕到槽T[ 0 ]，T[ 1 ]， …直到最后探查槽T[h' (k) - 1 ]。在线性探查方法中，初始探查位置确定了整个序列，故只有m种不同的探查序列。

线性探查方法很容易实现，但它存在一个问题，称作一次群集（primary clustering）。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。群集现象很容易出现，这是因为当一个空槽前有i个满的槽时，该空槽作为下一个将被占用槽的概率是(i+ 1 ) /m。连续被占用槽的序列将会越来越长，因而平均查找时间也会随之增加。

3.2、二次探查

二次探查（quadratic probing）采用如下形式的散列函数：h(k，i) = (h' (k) +c1 i+c2 i2) modm   。其中h'是一个辅助散列函数，c1和c2为辅助常数（不等于0），i= 0， 1， …，m- 1。初始的探查位置为T[h'(k) ]，后续的探查位置要在此基础上加上一个偏移量，该偏移量以二次的方式依赖于探查号i。这种探查方法的效果要比线性探查好很多，但是，如果两个关键字的初始探查位置相同，那么他们的探查序列也是相同的，这是因为h(k1， 0 ) =h(k2， 0 )蕴含着h(k1，i) =h(k2，i)。这一性质可导致一种程度较轻的群集现象，称为二次群集（secondary clustering）。二次探查也只有m个不同的探查序列。

3.3、双重散列

双重散列是用于开放寻址法的最好方法之一，它采用如下形式的散列函数：h(k，i) = (h1(k) +i h2(k) ) modm

其中h1和h2为辅助散列函数。初始探查位置为T[h1(k) ]，后续的探查位置在此基础上加上偏移量h2(k)模m。

为能查找整个散列表，值h2(k)要与表的大小m互质。确保这个条件成立的一种方法是取m为 2 的幂，并设计一个总产生奇数的h2。另一种方法是取m为质数，并设计一个总是产生较m小的正整数的h2。

双重散列法中用了Θ(m2)中探查序列。

3.4对开放寻址散列的分析

对开放寻址散列的分析也是以散列表的装载因子α=n / m来表达的。在开放寻址法中，由于每个槽中至多只有一个元素，因而n<=m，这意味着α<= 1 。

现在假设采用的是一致散列法。在这种理想的方法中，用于插入或查找每一个关键字k的探查序列<h(k， 0 )，h(k， 1 )， …，h(k，m- 1 ) >为< 0， 1， …，m- 1 >的任一中排列的可能性是相同的。当然，每一个给定的关键字有唯一确定的探查序列。我们这里想说的是，考虑到关键字空间上的概率分布及散列函数函数施于这些关键字上的操作，每一种探查序列都是等可能的。

    下面就来分析一下在一直散列的假设下，用开放寻址法进行散列时预期的探查数。分析结果为如下几个定理。

定理：给定一个装载因子为α=n / m< 1 的开放寻址散列表，在一次不成功的查找中，期望的探查数至多为 1 / ( 1 -α)。假设散列是一致的。==>我认为该定理的前提是该散列上没有删除操作。

如果α是一个常数，根据上述定理，一次不成功查找的运行时间为O( 1 )。

推论：平均情况下，向一个装载因子为α的开放寻址散列表中插入一个元素时，至多需要做 1 / ( 1 -α)次探查。假设散列是一致的。

定理：给定一个装载因子为α< 1 的开放寻址散列表，一次成功查找中的期望探查数至多为：( 1 /α) ln ( 1 / ( 1 -α))。假定散列是一致的，且表中的每个关键字被查找的可能性是相同的。

4、完全散列

人们之所以使用散列技术，主要是因为它有着出色的期望性能。其实，当关键字集合是静态的时，散列技术还可以用来获得出色的最坏情况性能(我认为这句话的意思是：最坏情况的性能也非常好)。所谓静态是指关键字集合中关键字就那么多，不是变化的。有些应用很自然的有着静态的关键字集合，如一门程序设计语言中的保留字集合，或者一张CD-ROM上的文件名集合等。如果某一种散列技术在进行查找时，其最坏情况内存访问次数为O( 1 )的话，则称为完全散列(perfect hashing)。

设计完全散列方案的基本思想是比较简单的：我们利用一种两级的散列方案，每一级上都采用全域散列。具体来讲，存在待查找的元素key，经过一次散列，该元素被存放在槽hash(key)处，然而其他元素也有可能被散列至该处，因此对散列至该槽的元素继续进行散列，所得到的值hash'(key)即为元素key的确切存储位置。其中外层hash过程称为一级散列，内层hash'过程称为二级散列。

这个策略会存在几个问题，首先二级散列之后可能还会存在碰撞问题，是否需要进行三级散列甚至更多级的散列？其次，某个槽对应的二级散列函数应如何选取？最后，一级散列中某个槽所对应的二级散列表的尺寸应该如何设置？这三个问题其实可以一并解决。首先对于是否需要更多级的散列，因为外层的一级散列已经将原集合分为一系列子集，若我们将一级散列表设置为与原集合尺寸相近的大小，同时合理的选取一个散列函数，那么在每个槽中发生碰撞的元素个数将在一个可控范围内，此时如果为了少部分元素再设置三级散列的话，不仅增加了整个结构的复杂性以及对于内存的要求，而且还要再次为三级散列选取合理的散列函数，成本相对较大。接着来看解决二级散列函数的选取问题，我们发现在全域散列法中，只需设置不同的参数，即能生成特定于某个槽的散列函数，若生成的散列函数导致二级散列表中发生碰撞，那么重新从全域散列函数簇中选取，直至不发生碰撞为止即可。另外，只需合理设置二级散列表的大小，这种重新选取的概率将变得极低，一个可行的指导原则是将二级散列表Sj的大小Mj设置为外层散列至该槽的元素个数Nj的平方。Mj对Nj的这种二次依赖关系看上去可能使得总体存储需求很大，但是通过证明我们发现：通过适当的选取第一次散列函数，预期使用的总存储空间仍然为O(n)。

    完全散列的分析更形象化的说明上图所示。第一级与带链接的散列基本上是一致的：利用从某一全域散列函数簇中仔细选出的一个散列函数h，将n个关键字散列到m个槽中。然后，对散列到槽j中的关键字建立一个链表Sj，对应的散列函数为hj（j是下标）。通过仔细选取散列函数hj，可以确保在第二级上不出现碰撞。

最后要说明的一点是，这种通过两次散列的方法虽然提供了高效的搜索，但代价是花费了更多的内存空间，同时因为插入操作有可能导致在二级散列表中发生碰撞，因此这种方法只适用于静态关键字集合中，“静态”意指该集合一旦确定，便不再发生动态变化，即不发生插入或是删除操作。

    下面的定理说明两个问题。首先，要确定如何才能确保二次散列表中不出现碰撞。其次，要说明期望使用的总体存储空间(即主散列表和所有的二次散列表所占的空间)为O(n)。

    定理11.9：如果利用从一个全域散列函数类中随机选出的散列函数h，将n个关键字存储在一个大小为m=n2的散列表中，那么出现碰撞的概率小于1/2.====>通过定理我们知道，在m=n2的全域散列表中更大的可能是不发生碰撞。给定待散列的包含n个关键字的集合K（注意K是静态的），只需几次随机的尝试，即能比较容易的找出一个没有碰撞的散列函数h。但是当n比较大时，一个大小m=n2的散列表还是很大的。因此我们采用二次散列的方法，并利用定理11.9中所述的方法，对每个槽中的关键字进行仅一次散列。一个外层的（或称一级的）散列函数h用于将各关键字散列到m=n个槽中。那么，如果有nj（j为下标）个关键字被散列到槽j中的话，可以用一个大小mj = nj2的二次散列表Sj来提供无碰撞的常亮时间查找。

    下面的定理说明如何确保期望使用的总体存储空间(即主散列表和所有的二次散列表所占的空间)为O(n)。

    定理11.10：如果从某一个全域散列函数类中随机选出散列函数hh，用它将nn个关键字存储在一个大小为m=nm=n的散列表中，则有E[∑m−1j=0n2j]<2nE[∑j=0m−1nj2]<2n，这里njnj为散列到槽jj中的关键字数。

推论11.11：如果从某一全域散列函数类中随机选出散列函数hh，用它将nn个关键字存储在一个大小m=nm=n的散列表中，并将每一个二级散列表的大小设置为mj=n2j(j=0,1,...,m−1)mj=nj2(j=0,1,...,m−1)，则在一个完全散列方案中，存储在所有二次散列表中所需的存储总量的期望值小于2n2n。

推论11.12：如果从某一个全域散列函数类中随机选出散列函数hh，用它将nn个关键字存储到一个大小为m=nm=n的散列表中，并将每个二级散列表的大小置为mj=n2j(j=0,1,...,m−1)mj=nj2(j=0,1,...,m−1)，则用于存储所有二级散列表的存储总量等于或大于4n4n的概率小于1/21/2。===>从推论2中可以看出，只需从全域散列函数类中随机选出几个散列函数，尝试几次就可以快速地找到一个所需存储量较为合理的函数。===>完全散列最坏存储为4n，期望为2n，我认为有一点空间换时间的味道。

作者：黑夜0411

链接：https://www.jianshu.com/p/7a8005b3dc75

来源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。