简单均匀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和α同阶）。

2. 查找失败

查找失败意味着要找的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