词典

词典(dictionary)这种数据结构在编程语言中很常见,比如Java中的HashMap与Hashtable、Python中的字典等等,一个键值对可以称为一个词条,即entry = (key, value),而映射(map)就是词条的集合,但其中各词条(的关键码)互异,词典与映射基本相同,但允许词条的(关键码)雷同,进一步,关键码之间可以定义全序关系的词典称为有序词典(sorted dictionary),映射和词典都是动态的,统称符号表(symbol table)。实现词典的重要技术便是散列(hash),与其说散列是一种技术,不如说散列是一种思想,它重点解决的问题是数据结构在空间效率上的提高,而依照散列思想所实现的数据结构的访问方式不妨称为寻值访问(call-by-value),这种方式更为自然,适用范围也更广泛。

散列原理

当实际的词条数N远小于可能的词条数R时,散列技术可以在保持查找速度的同时,降低存储消耗。我们定义(bucket)为直接存放或间接指向一个词条,相应的,桶数组(bucket array)/散列表(hash table)的容量为M,即有\(N< M\ll R\),此时的空间复杂度为\(O\left ( N+M \right )= O\left ( N \right )\),装填因子\(\lambda = N\div M\),可以通过散列函数,将任一key映射至[0, N)进行定址,而时间复杂度则为\(expected-O\left ( 1 \right )\neq O\left ( 1 \right )\)。当\(key1\neq key2\),而\(hash\left ( key1 \right )= hash\left ( key2 \right )\)时,我们说出现了同义词(Synonym)。是否存在某种定址方法,能保证不出现冲突(消除同义词),亦即,散列函数等效于一个单射(injection)?答案是,在一般情况下,完美散列(perfect hashing)无法保证存在。基于散列函数的性质,它不可能是单射,但是,近似的单射往往可行。为此,我们需要精心设计散列表及散列函数,以尽可能降低冲突的概率;更需要制定可行的预案,以便在发生冲突时,能够尽快予以排解。

散列函数

好的散列函数应该满足一下4点:

  1. 确定(determinism):同一关键码总是被映射至同一地址
  2. 快速(efficiency):expected-O(1)
  3. 满射(surjection):尽可能充分的覆盖整个散列空间
  4. 均匀(uniformity):关键码映射到散列表各位置的概率尽量接近,可有效避免聚集(clustering)现象

考查第一种散列函数——除余法,除余法可表示为:hash(key) = key % M,此方法的关键在于M的取值,若取\(M= 2^{k}\),其效果相当于截取key的最后k位(bit),前面的n-k位对地址没有影响,所以当且仅当最后k位相同时,发生冲突,若取\(M\neq 2^{k}\),缺陷将有所改善,更进一步的,M为素数时,数据对散列表的覆盖最充分,分布最均匀。

除余法也有一些缺陷,其一为:存在不动点,即无论表长M取值如何,总有hash(0) = 0;其二为:只达到了零阶均匀,即[0, R)的关键码,平均分配至M个桶,但相邻关键码的散列地址也必相邻。更好的散列函数应该达到一阶均匀,即邻近的关键码,散列地址不再邻近。为此,我们引入了MAD(Multiply-Add-Divide)法,可表示为hash(key) = (a * key + b) % M,取M为素数,a > 0,b > 0,a % M != 0。当然,某些特定场合下,未必需要高阶的均匀性。

数字分析(selecting digits)指抽取key中的某几位,构成地址。比如,取十进制表示的奇数位:hash(123456789) = 13579

平方取中(mid-square)指取key2的中间若干位,构成地址。比如:

折叠法(folding)是将key分割成等宽的若干段,取其总和作为地址。如:

位异或法(XOR)则是将key分割成等宽的二进制段,经异或运算得到地址。如:

总之,散列函数越是随机,越是没有规律,越好。既然如此,为何不使用伪随机数发生器呢,显然,伪随机数发生器和我们的散列函数做的是同一件事,但是,伪随机数发生器的实现,因具体平台、不同历史版本而异,创建的散列表可移植性差,故需慎用此法!

很多时候,我们的key并不是整型的,比如字符串型,此时我们应首先将其转换为整数,即散列码,然后再做散列,这时就要用到多项式法,可表示为:\(hash\left ( s= x_{0}x_{1}…x_{n-1} \right )= x_{0}\times a^{n-1}+x_{1}\times a^{n-2}+…+x_{n-2}\times a^{1}+x_{n-1}= \left ( …\left ( \left ( x_{0}\times a+x_{1} \right )\times a+x_{2} \right )\times a+…x_{n-2} \right )\times a+x_{n-1}\)。

散列冲突

发生冲突要排解



发表评论

电子邮件地址不会被公开。 必填项已用*标注