? 在部分散列表（分离链接，开放定址https://www.cnblogs.com/dhcao/p/10534728.html）中，当装填因子\(\lambda\)合理，散列函数合适的情况下，期望的插入、删除、和查找的平均时间都是\(O(1)\)，即在没有冲突的情况下计算散列所需要的时间。
? 但是在最坏情况(冲突)下，查找的最坏情形是多少？
? 我们期望最坏的情况下，查找的时间函数也是\(O(1)\) — 完美散列
? 简单起见：我们首先定义所有的项N都事先已知。在分离链接法中，我们如果多用一些表，那么这些表的长度就会相应减少，假设我们有充分多的表，则在相当高的概率下可以期待根本没有冲突。但是，这种方法存在2个基本问题。1，表的数量可能会大得离谱；2，即使有很多表，还是可能碰到冲突，这个跟运气也有关系。
? 定义完美散列：我们已经知道在分离链接法中，当发生冲突的时候，我们会在冲突地点构建一个链表来处理冲突，在链表中依次放入冲突值。但这里提供另一种做法：我们在每个位置创建二级散列表，并将二级散列表的大小设定为位置中元素数量的平方。
? 图解：
图解说明：在位置0处有一个元素，我们给它创建一个长度为1都散列表。位置1，位置2都没有元素，我们不创建散列表。在位置3有2个元素，我们创建一个大小为\(4(2^2)\)都散列表。在位置7有3个元素，我们在位置7创建一个大小\(9(3^2)\)的散列表。第一次散列到位置3，但是不将数据直接放入位置3，而是放入位置3所保留的二级散列表中，第二次散列决定在二级散列表中的位置。这种使用二级散列表的方法叫做完美散列。
? 完美散列的优势：所有的元素都可以存入二级散列表中，那么任何元素的查找都只需要散列2次得到。
?
? 说明1：完美散列的前提是所有的元素的值都已经知道，所以元素的一次散列值和二次散列值已经知道，上述图中的数据结构在元素存入前已经可以确定。
? 说明2：为什么是元素个数的平方呢？？— 见定理2.2.1
? 说明3：我们可以确定：当我们的主散列表大小是N时，二级散列表的期望大小时2N。 — 见定理2.2.2
?
? 证明：问题转化，将N个球，放入M个盒子！
? 若一对球\((i,j)\)被放入同一个盒子，则称之为冲突。
? 1.冲突的概率：
\[
球i被放入1号盒子的概率是：f(i) = 1/M \球j被放入1号盒子的概率是：f(j) = 1/M\总共M个盒子：f(i) * f(j) *M= 1/M
\]
? 任意2个球冲突的概率是\(1/M\)
? 2.在N个球中，类似1中\(i,j\)的组合有\(N*(N-1)/2\)对：
\[
1号球跟其他球的组合方式：1*(N-1)\2号球跟其他球的组合方式：1*(N-1)\共N个球，去除重复项后的组合方式：N(N-1)/2
\]
? 3.整个散列表的冲突期望值：
\[
\sum_{i,j<N;i\neq j}^{N}{a_n}=[N(N-1)/2] *(1/M) \=N(N-1)/2M\=N(N-1)/2N^2\=(N-1)/2N\< \frac12
\]
? 证明：在上述定理中我们知道当盒子个数为\(N^2\)时成对冲突的期望值是\((N-1)/2N\)。
? 1.在\(N\)个盒子中冲突次数的期望值是$N(N-1)/2N \(或者记做\)(N-1)/2$。
? 2.假设位置\(i\)的散列个数为\(b_i\)，那么在位置\(i\)的二次散列表大小为\(b_i^2\)。而且已经占用了冲突次数\(b_i(b_i-1)/2\)。
? 3.令冲突次数 \(b_i(b_i-1)/2 = c_i\) 。那么\(c_i\)：
\[
c_i = b_i(b_i-1)/2\=\frac {b_i^2-b_i}{2}\位置i的空间b_i^2:\quad b_i^2 = 2c_i+b_i
\]
? 4.得到上述描述：
? a) \(c_i\)表示位置\(i\)的冲突次数，\(b_i\)表示位置\(i\)的项数。\(b_i^2\)表示位置\(i\)所用的空间。
? b) 所谓位置\(i\)，可以是第一个位置，也可以是第N个位置。
? 5.因为位置\(i\)一共多少个？N个
\[
N个位置的总空间是：\quad \displaystyle \sum_{i=1}^{n}b_i^2 = 2 \sum_{i=1}^{n}c_i^2+\sum_{i=1}^{n}b_i^2\可知冲突总次数：\quad \sum_{i=1}^{n}c_i^2 = (N-1)/2\总项数：\quad \sum_{i=1}^{n}b_i^2 = N\所以：\qquad \sum_{i=1}^{n}b_i^2 = 2(N-1)/2+N\=2N-1<2N
\]
? 定理得证
原文：https://www.cnblogs.com/dhcao/p/10561684.html