本文将证明比较模型的查询操作find(k)的时间复杂度不能快于 Theta(log n) ，介绍了哈希(hash)的基础理论与对查询、删添操作的改进（时间复杂度将达到 Theta(1)，并给出了MIT6.006未在课题上证明的Hash Family的全域性(universal)。（知乎的排版还是好麻烦…

回顾

无序与排序集合的时间复杂度

在正文之前，我们先回顾无序与有序集合的操作时间复杂度，排序集合在查询操作 find(k) 上做到了Theta(log n)，但插入与删除操作时间复杂度仍较高。接下来我们将寻找更快的操作方式。我们首先证明在给定条件下，上述查询操作已经是最快的了！

1. 比较模型(Comparsion Model)

我们之前介绍的排序算法都有一个共同特点：区分不同元素的唯一方式是比大小，无论是遍历、选择、插入还是归并算法，都没有事先对任何元素进行区分，元素之间只有直接或间接地比较大小才能得以区分，而这是决定时间复杂度下界的一个关键。

决策树路径距离

在上一节末尾，我们使用递归树刻画了算法的过程，事实上，任何算法都可以表示成一个类似的决策树（Decision Tree）的形式。决策树的每个节点是一个二元比较（<,le,>,ge,=,neq）操作，它返回Ture或False，在一个节点后会形成两个不同的分支，分支会不断扩展，最终形成从根（起始的一个节点）到许多叶子（节点后不再有分支，即输出的结果）的一颗决策树。

决策树示意图

现在，我们考虑find(k)对应决策树的叶子数量，很显然，我们至少应该能够查询到集合的所有元素，这表明叶子数量即 find(k) 操作对应的输出至少为集合的元素总量n；同时，当关键词不再集合中时，我们无法查询到任何结果，此时应该返回None,这表明查询操作的叶子数量，即输出结果数，至少应为n+1.

与之前相同，查询操作的时间复杂度正好对应决策树从根到叶的最长路径距离（这是因为每个比较操作的时间是 Theta(1),h 个二院比较累加的时间复杂度正好为 Theta(h)），于是问题求时间复杂度下界的转化为，决策树的高度至少为多少时能生成至少 n+1片叶子（输出）?

由于一个节点至多生成两个子节点，那么要生成n+1片叶子至少需要 left lceil (n+1)/2right rceil 个节点，而生成这些节点，又至少需要 leftlceilleft lceil(n+1)/2rightrceil /2rightrceil 个节点 cdots 计算过程又与之前的二分法求时间复杂度是完全相同的，这样得到的路径长度至少为 left lceil log(n+1)-1right rceil，于是比较模型的时间复杂度下界为 Omega(log n).这便完成了证明。

2. 直接访问数组(Direct Access Array)

比较模型的关键是事先不知道任何信息，如果我们要跳出比较模型，就必须要打破这一限制。回忆之前的计算模型Word-RAM，它对内存上任意一个位置的访问时间都是 O(1)的，如果我们直接将集合的关键字/键/key（不妨设为整数）与内存的第k个位置对应，将集合的项目/值/value存入第k个位置，那么我们便可以通过直接输入key得到value了！

但是缺点是显然的，如果我们记键的最大值为u，那么我们就需要O(u)的空间进行存储，并且CPU一次能调用的字节是有限的为2^omega bits，omega为机器字节现在通常为64，那么我们还要保证ule 2^omega才能使查询操作时间复杂度为O(1).后者是容易实现的，但前者可能需要巨大的空间。

• e.g. 如果keys是十个字母长的名字（英文），一个名字占据1bit，那么就需要26^{10}approx 17.6TB的空间，然而许多空间占用是冗余的。

3. 哈希/散列(Hashing)

Hashing

为了避免巨大的空间占用，我们考虑对keys进行压缩映射，也称为Hash映射，即：

begin{equation}h(k): {0,cdots,u-1}to{0,cdots,m-1}end{equation}

然而上述映射存在着一个问题，即当m<u时，哈希映射不是单射，这意味着我们输入两个不同的关键字a,b，可能有h(a)=h(b)，我们称这种现象为发生了碰撞(colilsion)。由于内存的同一位置不能存放两个item，为了解决上述问题，我们可以采用下面两种方法：

• 将后来的item存于数组的其它位置(open addressing),这正是Python采用的一种方法。然而这种方法分析较复杂，未在课程中阐述。
• 在碰撞处存放指针，指向另一支持动态操作的数据结构（如链表等），将碰撞的items存放于该数据结构，这称之为chaining。

Chaining

我们现在对碰撞线性引入的Chaining进行分析。

• 当关键词是均匀分布的指标时（例如从0到100每个数都是key），那么chain的大小为n/m=n/Omega(n)=O(1)（如果Hash map也是“均匀”的）。
• 当chain size为O(1)时，所有操作的时间复杂度自然也是O(1)的。
• 当Hash map“不好时”，例如h(k)=text{constant}，那么哈希表便退化为链表（取决于指针指向的数据结构），此时便失去了Hash的优势。

上述分析告诉我们，在关键词均匀分布的情况下，要使时间复杂度下降，必须选择“均匀”的Hash映射。

Hash Functions

使Hash映射能保证“均匀”的一个常用函数是模运算：

begin{equation}h(k)=(k text{mod} m)end{equation}

模运算即对非零整数k,m，存在整数b与整数r,0le r<m使得k=bm+r，模运算即k text{mod} m = r. m应避免某些选择，例如m=2^p时，h(k)就是k的p个最低位数字。一般m会选择为较大的素数，同时避免接近2到10中素数的幂。

• NOTE：这里做一个说明(kbmod p)表示的是k模p后的余数，而k=l (bmod p)表示的是k,l在模p意义下相等，即模p后余数相同。

然而，无论怎样选择m，我们总能找到某种均匀分布使得Theta(n)的关键字被映射至同一槽中，进而使平均检索时间为Theta(n).为了尽量避免这种最坏的情况，我们需要对固定的函数进行改进，那便是引入随机选择，但每个随机选择的哈希函数也应尽可能的“好”。

Universal

为了引入随机化，我们定义类似与之前的Hash函数：

begin{equation}h_{ab}(k)=((ak+b text{mod} p)text{mod} m)end{equation}

ain{1,2,cdots,p-1},bin{0,1,2,cdots,p-1}被等概率地随机选择，于是我们得到了一族Hash函数(Hash Family):mathcal{H}(p,m)={h_{ab}|a,bin{0,1,cdots,p-1},aneq0}.这一族函数是全域(Universal)的，即成立下式：

begin{equation}text{Pr}_{hinmathcal{H}}{h(k_i)=h(k_j)}le 1/m, forall k_ine k_jin{0,1,cdots,u}end{equation}

text{Pr}表示概率。关于该性质的证明我们放在最后，该性质使得在期望意义下，Hash表的查询等操作时间复杂度是O(1)的。为了分析碰撞的期望性质，我们定义指示函数：X_{ij}= 1,if h(k_i)=h(k_j),X_{ij}= 0,otherwise.这是一个关于h的随机变量。于是，h(k_i)的链长(size of chain)可以表示为X_i = sum_{j}X_{ij}.链长的期望为：

mathbb{E}_{hinmathcal{H}}{X_i} = mathbb{E}_{hinmathcal{H}}{sum_j X_{ij}}=1+sum_{jneq i}mathbb{E}_{hinmathcal{H}}{X_{ij}},/ = 1+sum_{jneq i}[1cdot text{Pr}_{hinmathcal{H}}{h(k_i)=h(k_j)}+0cdot text{Pr}_{hinmathcal{H}}{h(k_i)neq h(k_j)}]/<br>le 1 + sum_{jneq i}1/m = 1+(n-1)/m

上式的1来源于X_{ii}本身，即在不考虑碰撞时，每个槽本应存放的一个关键字。由于m=Omega(n),上式表明查询操作的期望时间复杂度是O(1+(n-1)/m)=O(1)的。

动态化

为了能使Hash族对于动态操作保持高效，我们借鉴之前动态数组的想法，在执行动态操作（不妨考虑插入）时，当出现n/m>1的，我们重新随机选择一个Hash函数，并且增大m到r倍，如此反复。这样得到的插入、删除平均期望时间复杂度便是O(1)的。

• 注意，平均来源于不断扩大m；期望来源于重新选择Hash函数。

我们对各操作时间复杂度做一个总结：

时间复杂度

* Proof University of Hash Family

在MIT6.006中并未给出Hash函数族的全域性的证明，我们在此进行补充，这里需要假设p>m.

• 首先，forall k,lin{0,1,cdots,m}且kneq l，给定h_{ab}inmathcal{H},记r=(ak+b) bmod p, s = (al+b) bmod p,则有rneq s。
• 否则若r=s,则有a(k-l)=r-s (bmod p)。但p是素数，且由于ain{1,2,cdots,p-1},故anmid p。而k,lin{0,1,cdots,m},kneq l,m<p,于是(k-l)nmid p,矛盾。于是rneq s.

• 上述分析表明，k,l在模p层面是不冲突的（即模p是运算是单射）。由于(a,b)这一数对的选择共有(p-1)p种，而对每一个Hash函数，即每一对(a,b)都将产生一对(r,s)，下面说明这个关系是一一对应的。
• 只需说明给定一对(r,s)，能确定一对(a,b)。事实上，在知晓k,l,r,s的情况下，可以解得a=((r-s)((k-l)^{-1}bmod p))bmod p,且b=(r-ak)bmod p.这里(k-l)^{-1}是mathbb{Z}_p的逆元，即满足(k-l)(k-l)^{-1}=1 (bmod p)的解。
• 于是(a,b),(r,s)是一一对应的。

• 由于rneq s,故text{Pr}{h_{ab}(k)=h_{ab}(l)} = text{Pr}{r=s (bmod m)}，且(r,s)与(a,b)一一对应，那么给定r后，s还剩下p-1中选择。我们只需考察在这p-1个选择中，r=s (bmod m)的数目。
• 在给定r的情况下，与r模m相等的数有{cdots,r-m,r,r+m,cdots}，由于sneq r，那么除去r，剩下的数目至多为 left lceil p/m right rceil-1 而 left lceil p/m right rceil-1 le ((p+m-1)/m)-1le dfrac{p-1}{m} 这个不等式的证明是平凡的，只需将 p=cm+d 的形式代入即可),于是有：

text{Pr}{s=r(bmod m)} le dfrac{p-1}{m}/(p-1) = dfrac{1}{m}.

• 综上，我们完成了构造的Hash Family是全域的证明。