- 全域散列法(universal hashing)
设 hasha,b(key)=(a×key+b) modm，如同除余散列法中一样，m的值应为质数，而a∈{1,2,3,…,m-1}，b∈{0,1,2,…,m-1}且a,b的值应在运行时动态确定。
全域散列的基本思想是只给出hash函数的基本“骨架”，而其中的某些参数通过运行时在指定范围内随机选取确定，从而实际上形成了一个函数簇，根据上述a,b的取值范围，我们知道这个函数簇中存在m×(m-1)个函数。因为即使对于同一个输入，每次执行时选取不同的参数将拥有不同的性能表现，因此所设计的函数实际上独立于任意被散列的关键字。只有当一个相对糟糕的输入（即该输入不构成随机分布），遇到一个选取的相对糟糕的散列函数时才将导致较差的散列分布，在多数情况下这类散列往往具有较好的运行性能。
- 完全散列法(perfect hashing)
完全散列法与其说是一种函数设计方法，倒不如说是对碰撞(Collision)情况的另一种解决策略。见名知意，即将原集合中被散列函数作用之后发生碰撞的元素继续进行散列。更具体的说，存在待查找的元素key，经过一次散列我们知道该元素被散列至槽hash(key)处，然而其他元素也有可能被散列至该处，因此对散列至该槽的原集合的子集继续进行散列，所得到的值hash'(hash(key))即为所要查找的元素key的确切存储位置。其中外层hash过程称为一级散列，内层hash'过程称为二级散列。
这个策略会存在几个问题，首先二级散列之后可能还会存在碰撞问题，是否需要进行三级散列甚至更多级的散列？其次，某个槽对应的二级散列函数应如何选取？最后，一级散列中某个槽所对应的二级散列表的尺寸应该如何设置？
这三个问题其实可以一并解决。首先对于是否需要更多级的散列，因为外层的一级散列已经将原集合分散为一系列子集，若我们将一级散列表设置为与原集合尺寸相近的大小，同时合理的选取一个散列函数，那么在每个槽中发生碰撞的元素个数将在一个可控范围内，此时如果为了少部分元素再设置三级散列的话，不仅增加了整个结构的复杂性以及对于内存的要求，而且还要再次为三级散列选取合理的散列函数，所以二级是一个比较合理的选择，那么如何解决二级散列上的碰撞问题呢？我们先来解决二级散列函数的选取问题，同样可以有多种策略，考虑每个槽对应的二级散列函数与外层的一级散列函数均相同的策略，或者是所有的二级散列函数均相同但不与一级散列函数相同，这两种策略实际将二级散列表中的元素之间可能发生的碰撞事件耦合在一起，因为可能选取的某个函数虽然解决了其中一个槽的元素碰撞问题，但其他槽内的元素仍然存在碰撞的可能性，因此若要使得选择出的函数能够一次解决二级散列表中出现的所有碰撞情况，必然需要经过多次尝试。因此我们考虑个性化制定每个槽所对应的散列函数，这使得我们需要事先做大量的准备，显然不太现实。考虑上述全域散列法，我们发现通过设置不同的参数，即能生成特定于某个槽的散列函数，若生成的散列函数导致二级散列表中发生碰撞，那么重新从全域散列函数簇中选取，直至不发生碰撞为止即可。另外，只需合理设置二级散列表的大小，这种重新选取的概率将变得极低，一个可行的指导原则是将二级散列表的大小设置为外层散列至该槽的元素个数的平方。
图3
完全散列的分析更形象化的说明如图3所示。最后要说明的一点是，这种通过两次散列的方法虽然提供了高效的搜索，但代价是花费了更多的内存空间，同时因为插入操作有可能导致在二级散列表中发生碰撞，因此这种方法只适用于静态关键字集合中，“静态”意指该集合一旦确定，便不再发生动态变化，即不发生插入或是删除操作。
开放寻址(openaddressing)
同链接法一样，开放寻址是一种用于解决碰撞的策略。与链接法不同的是，开放寻址将所有待散列的元素全都存放在一个散列表之中，更详细的说，使得某个关键字被散列函数作用之后得到与其对应的槽的过程称为寻址，在链接法中，每个关键字只能对应某个固定的槽，并且被散列之后该关键字将存放在与该槽对应的链表中，因此我们又可以形象地称链接法为固定寻址或封闭寻址。而开放寻址顾名思义，即每个关键字可以与散列表中的多个槽形成一对多的映射关系，因为可能在首次寻址过程中该槽已被先前的关键字所占据，因而接下来我们根据事先所制定的某个规则继续试探下一个槽是否可用，直至找到一个可用的槽并将关键字存储在其中为止。因为所有元素都存放在散列表中，因此散列表的大小必定大于或是等于原集合的大小。这里存在的一个问题是，如果仅将待散列的关键字作为函数的单个输入，那么最终必定只有与其对应的单个输出（即固定的下标值），因此我们必须寻找一个引导因子，使得在关键字不变的情况下诱使函数的输出发生变化，因为所有的关键字放在一个散列表中，因而将该引导因子的值域设置为与散列表的大小相同能够更充分的利用整个散列表，形式化地：
设原集合中存在元素elem，诱导因子为i，散列表的大小为m，则有
hash: (elem, i)→γ，其中i,γ∈{0,1,2,…,m-1}
并且该函数所形成的探查序列为 <hash(elem,0),hash(elem,1), …, hash(elem,m-1)>
这里诱导因子被形式化地定义为区间[0,m)中的某个值，诱导因子i的取值序列被固定为<0,1,…,m-1>只是为了方便散列函数的实现，实际可根据原集合中的元素所存在的模式制定更具针对性的值域及取值序列，这里我们将重点放在开放寻址下的散列函数设计上。通常在开放寻址中所用的散列函数主要由以下几种：
- 线性试探法
设 hash(key, i)=(hash'(key)+i) modm，其中 i=0,1,…,m-1，hash'为辅助散列函数
在线性试探中，首次探查位置取决于hash'(key)的值，若发生碰撞，则接下来所探查的位置为(hash'(key)+1) modm，从而所形成的探查序列为<hash'(key), hash'(key)+1,…, m-1, 0,…,hash'(key)-1>。因为散列表的大小为m，所以整个散列表总共提供m种不同的探查序列。并且由于线性试探使用连续探查的方式，因此随着散列表中元素的增加，所占用的槽逐渐呈连续分布状况，从而增加插入/搜索操作的期望时间。
- 二次试探法
设 hash(key,i)=(hash'(key)+c1i+c2i2)modm，如上所述，i=0,1,…,m-1，hash'为辅助散列函数，c1，c2为辅助参数
可以发现，线性试探法实际是二次试探的特殊情况，若取参数c1=1，c2=0，那么二次试探将“退化”为线性试探。同样的，整个探查序列也是由hash'(key)所决定的，因为虽然探查序列中各元素之间的增量[c1i+c2i2]不再以线性的方式进行，但对于每个元素来说，引导因子i总是以步长1的方式递增，这就导致所有元素的探查序列的增加方式是相同的，因此整个散列表同样提供m种不同的探查序列。但随着散列表中元素的增加，这种跳跃式的增量方式使得插入/搜索操作的运行时间受到的影响较小。
- 双重试探法
设 hash(key,i)=(hash'(key)+i×hash''(key)) modm，其中i=0,1,…,m-1，hash'，hash''均为辅助散列函数
双重试探法的首个探查位置为hash'(key)，当产生碰撞之后，接下来的探查位置为(hash'(key)+hash''(key))modm，因此我们发现在双重试探法中，不仅初始探查位置依赖于关键字key，探查序列中的增量hash''(key)同样依赖于关键字key，因而整个散列表提供了m2种不同的探查序列，较之于前两种开放寻址具备了更多的灵活性。这里还要注意的是应保证hash''(key)与m互质，因为根据固定的偏移量所寻址的所有槽将形成一个群，若最大公约数p=gcd(m,hash''(key))>1，那么所能寻址的槽的个数为m/p<m，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的槽为<1,4, 7, 10>，寻址个数为12/gcd(12,3)=4。
最后要注意的一点是，因为开放寻址将所有的关键字均存放在散列表中，因此我们必须保证散列表的大小始终大于原集合的元素个数，以使得任何时刻都能将元素存放在其中，但动态集合的插入操作有可能使得散列表被填满，这种情况下如果还需进行插入操作，那么我们就必须扩大散列表，由于散列表的大小m发生变化，考虑到m是散列函数中的参数，我们并不能保证m发生变化之后，同样一个关键字能被散列至同样的槽中，因此存放在原先散列表中的关键字必须被重新散列，这就带来了额外的开销。因此我们首先应充分挖掘待存储的数据集的特点，比如作用在该集合上的操作是否在大多数情况下为搜索，而动态的插入/删除操作较少发生，或者是预留一个较大的散列表，能够保证原集合必定不超过该散列表的大小，在这之后才考虑使用开放寻址。 |
