Perfect Hashing Function Principles and Practice

1.前言

在很多应用中，都要用到一种动态集合结构，它仅支持INSERT，SEARCH和DELETE字典操作。例如，计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键字值为任意字符串，与语言中的标示符对应。实现字典的一种有效数据结构为散列表(hash table)。在最坏情况下，在散列表中，查找一个元素的时间与在链表中查找一个元素的时间相同，在最坏情况下都是Θ(n)，但在实践中，散列技术的效率是很高的。在一些合理的假设下，在散列表中查找一个元素的期望时间为O(1)。散列表是对普通数组概念的推广。[CLRS] 由于其具有其他很多数据结构都不具有的优点，散列的应用甚为广泛，从信息安全（例如文件校验，数字签名，签权协议）到搜索引擎(eMule)再到现在人们广泛应用的各种高速下载软件，都能看到其身影。可以说，如果没有它，Google都是不可能实现的。毫无疑问，这种算法的探究具有重要意义。尽管前述各种方式看来在实现上似乎已经毫无问题，但是，我们要指出，完美散列仍然有一些问题没有解决，而这些问题也是在这种算法中最为重要的冲突。

2.正文

2.1 经典方法

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。

然而，直接寻址技术存在一个明显的问题，如果域很大，受内存的限制，这就有点不实际了。而且分配给表T的大部分空间都要浪费掉。1953年，H.P.Luhn[Luh53]首先提出了散列表这一技术，以及用于解决碰撞的链接(chaining)方法。我们利用hash function h，根据关键字k计算出槽的位置： h：U→{0，1，…，m-1} 从而降低了空间开销。

这样做又有一个小问题：两个关键字可能映射到同一个槽上，我们称这种情形为发生了碰撞(collision)。我们需要采取有效的方法来避免碰撞。

2.1.1

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

2.1.2

在差不多同一时间，G.M.Amdahl首先提出了开放寻址法的思想。在开放寻址法(open addressing)中，所有的元素都存放在散列表里。亦即，每个表项或包含动态集合的一个元素，或包含NIL。当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现该元素不在表中。不像chaining，没有链表，没有元素存放在散列表外。Open addressing 的好处在于它根本不用指针，而是计算出要存取的各个槽。有三种技术常用来计算open addressing中的探查序列：线性探查(linear probing)，二次探查(quadratic probing)，以及双重散列(double hashing)。线性探查：给定一个普通的散列函数h’：U→{0，1，…，m-1}，linear probing采用的散列函数为：h ( k ， i )=( h’(k)+ i )mod m， i=0，1，…m-1。线性探查方法比较容易实现，但它存在一个问题，称为一次群集(primary clustering)。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加二次探查：quadratic probing采用如下形式的的散列函数： h( k ， i ) = ( h’(k)+c1i+c2i2)mod m 初始的探查位置为T[h’(k)]，后续的探查位置要在此基础上加上一个偏移量，该偏移量以二次的方式依赖于探查号i。这种探查方法的效果要比线性探查好很多。双重散列：double hashing是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择的排列的许多特性。它采用如下的散列函数： h( k ， i )=( h1(k)+ih2(k))mod m 与线性探查或二次探查不同的是，这里的探查序列以两种方式依赖于关键字k，因为初始探查位置、偏移量都可能发生变化。如图所示，给出了一个用双重散列法进行插入的例子。此处，散列表的大小为13，h1(k) = k mod 13，h2(k) = 1+(k mod 11)。因为14≡1(mod 13)，且14≡3(mod 11)，故在探查了槽1和槽5，并发现它们已被占用后，关键字14被插入到空槽9中。

2.1.3

任何一个特定的散列函数都可能出现某种最坏情况形态：所有的关键字全部散列到同一个槽中。唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字。这种方法称作全域散列(universal hashing)。全域散列的基本思想是在执行开始时，就从一族仔细设计的函数中，随机地选择一个作为散列函数。就像在quick sort中，随机化保证了没有哪一种输入会始终导致最坏情况形态。同时，随机化使得即使是对于同一个输入，算法在每一次执行时的形态也都不一样。这样就可以确保对于任何输入，算法都具有较好的平均情况性态。

2.1.4

算法导论中介绍的版本，假设了一个理想的散列函数（hash function），是一个完全随机的函数.这个假设叫Simple Uniform Hash Assumption (SUHA或者UHA)，认为经其散列后完全没有碰撞。对这些经典方法的分析都建立在对hash function理想的假设前提下。SUHA为分析提供了方便，经典的结果例如TAOCP，算法导论等，都是基于这个假设。这是一个过于理想的假设，实际中可以实现的散列函数是k-wise independent的，而k往往是一个常数。例如常用的linear congruential function (ax+b)mod n，它只是pair- wise independent，即2-wise。这已经成为了现实研究的一个瓶颈。

2.2 现代方法

2.2.1

如果某一种散列技术在进行查找时，其最坏情况内存访问次数为O(1)的话，则称其为完美散列(perfect hashing)。设计完全散列的基本想法是比较简单的。我们利用一种两级的散列方案，每一级采用全域散列，可以实现静态的部分功能。

perfect hashing是一个数据结构，它解决的问题是查找一个集合中元素的存在性.这也是计算机科学最经典的问题之一，Knuth的《计算机程序设计的艺术》第三卷《sorting and searching》的searching就是关于这个问题。这个问题的经典解法，二分查找和查找树等[Knu71]，时间复杂度都是O(log n)。而 perfect hashing在线性的O(n)空间复杂度上达到了常数级的时间复杂度。这是历史上第一次达到这样的解.在此之前人们甚至不太相信我们可以同时在时间和空间上达到最优。无论对于多么庞大的数据集，要查找一个数据对象，只需要读三次即可，这是非常惊人的。可以说如果没有发现这个解，Google都是不可能实现的。基于SUHA，数学上可以证明，O(1)时间复杂度下至少需要O(n2)的空间复杂度，这显然不能令人满意。

人类的愿望有两点： 1. O(1)时间O(n)空间(时、空复杂度同时最优) 2. 将理想的hash function假设转变为现实的假设。

2.2.2

第一点，人们一直以为不可能实现，人们以为二分查找的O(log n)复杂度对于线性空间已经最优了。直到Yao1981[Yao81]和Tarjan&Yao1979[TY79]提出了O(1)时间和O(n)空间的可能，但它们二者都对hash function的定义域提出了不符合现实的假设，前者需要假设hash function的定义域极大，后者却假设太小。这两个方法都不是现实中可以使用的方法，但却为实现perfect hashing的梦想开启了一扇门，使人们意识到这是可能的。 1984年，基于Yao的工作，由三位数学家Fredman ，Komlos和Szemeredi提出的FKS perfect hashing[FKS84]，可以使每次查询只需要常数级的时间，而且数据结构的空间复杂度仍然只有线性的O(n)。 FKS算法的思路是把hash table分散到两级： In the first level, n items are hashed to n buckets by a 2-universal hash function h. Let Bi be the set of items hashed to the it h bucket. In the second level, construct a | Bi | 2-size perfect hashing for each bucket Bi. The data structure can be stored in a table. The first few entries are reserved to store the primary hash function h. To help the searching algorithm locate a bucket, we use the next n entries of the table as the "pointers" to the bucket: each entry stores the address of the first entry of the space to store a bucket. In the rest of table, the n buckets are stored in order, each using a | Bi | 2 space as required by perfect hashing.

26年过去了，这个漂亮的理论结果对计算机理论研究产生了深远的影响。在实际应用中，Linux下的CMPH library实现了基于FKS思想的一系列数据结构。然而CMPH library只针对静态的情况，即数据集不会改变。FSK算法只是静态的，而实际应用中往往需要更新(update)。 1994年，数据集中的元素被动态的添加（insert）和删除（delete）在理论上已经得到常数级的解[DKM+94]。然而这个结果在现实中仍然缺乏很好的实现，目前还没有任何标准库实现了这一功能。其原因是它所利用的散列函数（hash function）的计算需要很多的乘法运算，这在理论模型中是被忽略的，但在苛刻的现实条件中，cpu做乘法被认为是及其低效的。这个结果还有个缺陷，不是最坏时间复杂度O(1)而是amortized time complexity，平摊时间复杂度是O(1)。原因在于FKS的hash function的分配并不平均。

2.2.3

第二点，由理想的simple uniform hash assumption转为Carter-Wegman[CW79]的universal classes of hash functions。universal classes of hash functions可以被视为一条链接理论和现实的辅助线。从理论的角度而言，它是更弱的随机性假设。从现实的角度，它是可以有效实现的随机性保证。因此，从universal hashing的假设出发，可以严格的证明(而不是基于理想的假设)hash table的效率。Carter-Wegman原始的universal hash function的构造是基于多项式，效率不够好（因为需要乘法和模运算）。[DHKP97]提出了新的universal hash function的构造，非常高效，因此在实践中大量使用。这个函数甚至可以被表示成为仅仅一行的c代码： h(x) = a * x >> ( 32 – k ); 它的不足在于随机性能不够好(只保证pair-wise independence)，因此在FKS中使用仍然无法做到平均分配。因此动态更新的时间复杂度无法从amortized O(1) time改进为worst-case O(1) time。对此，[DMadH90]中的hash function可以做到FKS的worst-case O(1) time所需的足够的随机性。然而，[DMadH90]中的hash function无论空间的使用(O(sqrt(n)))还是计算的效率都远远落后与[DHKP97]提出的那个已在在现实中大量应用hash function。因此现实中人们宁愿忍受糟糕的worst-case time complexity，也仍旧使用随机性不够好却可以高效计算的[DHKP97]的hash function。我们需要解决这一对矛盾。寻找既有良好随机性,足够另FKS拥有worst-case O(1) time，又可以高效率计算的hash function。

2.2.4

最新发展情况。出现了cuckoo hashing，其基本思想是使用两个hash function而不是只用一个，这样对于每个关键词有两个可能的位置。当插入一个新关键词的时候，采用贪心法，如果该位置已经被占，则像杜鹃一样把它踢出巢，被踢出的元素寻找下一个可选位置，这个定义是递归的。对于cuckoo hashing，Pagh 2001[Pag01]提出了静态版本。Pagh， Rodler 2004[PR04]提出了动态版本。两个目前都基于uniform hash assumption的理想假设。理论上，使用uniform hashing function是open problem, 实践中，目前根本没有实现cuckoo hashing的标准库。因此我们可以实验cuckoo hashing在实际hash function上的性能，以及实现一个可以用的cuckoo hashing 库。

3.小结

3.1

关于现有的perfect hashing库如CMPH、gperf、Sux4J。上面已经提过了，在实际应用中，Linux下的CMPH library实现了基于FKS思想的一系列数据结构。然而CMPH library只针对静态的情况，即数据集不会改变。同样的，gperf和Sux4j也类似。

3.2

我们要做的就是在有限的独立性假设下，支持完美散列。这是非常有现实意义的一件事。[DKM+94]这个结果没有很好的实现，主要原因是对于散列函数的假设过于理想，这是一个比较基本的难点。 1.同时，我们需要解决随机性和运算效率之间的矛盾，得到一个令人较为满意的散列函数。 2.此外，测试cuckoo hashing的性能，并实现一个可以用的cuckoo hashing库。 3.实现一个动态perfect hashing的Linux open source library。 4.尝试对成果数学性质的证明。

3.3

可能的实践方案如下:

 第一步：在前人的假设基础上以及理论支持下(包括使用已有的解决碰撞的问题和已有的散列函数)实现静态版本的完美散列，从中体会散列表这种数据结构优点及其存在的不足。
 第二步：在第一步的基础上，实现动态版本的完美散列。主要实现数据的更新，包括对关键字的增加和更改等。
 第三步：自己独立设计散列函数，记录构造过程。然后在用自己的散列函数去实现静态和动态的完美散列。
 第四步：从理论上论证函数的可行性。推导构造同类函数的具体过程。
 第五步：将解决碰撞的函数和实现动态更新功能的完美散列联系起来，得到综合性解决方案，针对前述的问题加以修正完善。
 第六步：做出令人满意的库函数。至少可以做出比目前的标准库更好的。
 第七步：尝试对数学性质的证明。

Literature Review

Contents

Perfect Hashing Function Principles and Practice

1.前言

2.正文

2.1 经典方法

2.1.1

2.1.2

2.1.3

2.1.4

2.2 现代方法

2.2.1

2.2.2

2.2.3

2.2.4

3.小结

3.1

3.2

3.3

4.References

Navigation menu

Literature Review

Perfect Hashing Function Principles and Practice

1.前言

2.正文

2.1 经典方法

2.1.1

2.1.2

2.1.3

2.1.4

2.2 现代方法

2.2.1

2.2.2

2.2.3

2.2.4

3.小结

3.1

3.2

3.3

4.References

Navigation menu

Search