Literature Review

From TCS Wiki
Jump to navigation Jump to search

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

可能的实践方案如下:

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

4.References