简单均匀Open Hashing的Search操作平均时间复杂度证明

在HKU的COMP2119 Intro to DS&A课程中的一点收获,以前学习数据结构时没有这么注意理论细节,导致今天一开始没有搞明白,现在大概清楚了,在这里记录一下。写得比较啰嗦,主要是为了容易看懂。Wordpress自带的编辑器打公式实在是太蛋疼了,以后有空要好好整理一下。

假设:

  1. hash表的长度为m,现有元素个数为n。
  2. 采用的hash函数是理想的,即hash值在0~m-1内均匀分布(simple uniform hashing),也就是说每个元素被插入每个位置的概率是相同的,且不同元素相互独立。
  3. 采用拉链法(Chaining, a.k.a open hashing)解决冲突。

定义hash表的装填因子(load factor)为α=n/m。下面证明Find操作在查找成功和失败的情况下平均时间复杂度均为O(1+α)。

设Hash函数计算的平均时间复杂度为O(1)。当查找一个元素时,我们先计算它的key对应的hash值,然后在hash值所对应的slot的链表中从头到尾逐个检查,直到找到一个元素,其key与要找的元素的key相同,或发现全都不相同为止。

  1. 查找成功

查找成功意味着要找的key是n个元素的key中的某一个。按照这n个元素在插入时的先后顺序,我们有:对于第i个插入的元素,它被放置的位置对应的链表中已经存在的元素个数的期望是(i-1)/m(前i-1个元素均匀放到m个slots中,任意一个slot中的元素个数期望都是(i-1)/m)。那么这个新插入的元素在链表中就是第(i-1)/m + 1个元素。按照Find操作的算法,当我们要查找这个元素时,需要比较(i-1)/m + 1次。那么n个元素的平均比较次数就是(sigma(i=1 to n)((i-1)/m + 1))/n。按下图过程可推出平均比较次数为1 + α/2 – 1/(2m)。当m很大时,平均搜索次数就是1+α/2,再加上hash函数的计算时间,成功查找的时间复杂度就是O(1+1+α/2) = O(1+α)(其中1+1=2和1同阶,α/2和α同阶)。

Screen Shot 2015-09-22 at 19.17.51

  1. 查找失败

查找失败意味着要找的key在其hash值对应的slot的链表中不存在,也就是将链表中元素全部比较了一遍。由于均匀分布,每个链表中的元素个数都是n/m,所以比较次数就是n/m=α。再加上计算hash值的O(1),可得查找失败的平均时间复杂度也是O(1+α)。

综上所述,在hash值均匀分布、采用拉链法处理冲突时,Find操作的平均时间复杂度均为O(1+α)。

 

参考文献:

Discrete Mathematics for Bioinformatics WS 07/08, G. W. Klau, 5. Februar 2008