完美散列
一、介绍
在部分散列表（分离链接，开放定址）中，当装填因子(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
2.2 定理
2.2.1定理：假设将N个数据放入(M=N^2)个位置，则没有冲突的概率最少是(1/2)。
证明：问题转化，将N个球，放入M个盒子！
若一对球((i,j))被放入同一个盒子，则称之为冲突。
1.冲突的概率：
任意2个球冲突的概率是(1/M)
2.在N个球中，类似1中(i,j)的组合有(N*(N-1)/2)对：
3.整个散列表的冲突期望值：
2.2.2 定理：若(N)个项被放入包含(N)个盒子的主散列表中，则二级散列表的总容量的期望值最多是(2N)。
证明：在上述定理中我们知道当盒子个数为(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)：
4.得到上述描述：
a) (c_i)表示位置(i)的冲突次数，(b_i)表示位置(i)的项数。(b_i^2)表示位置(i)所用的空间。
b) 所谓位置(i)，可以是第一个位置，也可以是第N个位置。
5.因为位置(i)一共多少个？N个
定理得证