开放寻址法
开放寻址法是解决散列表发生碰撞的方法之一，与另外一种方法--链接法相对应。开放寻址法把所有的元素都存放在散列表中，也就是每个表项包含动态集合的一个元素，或者包含NIL。
当查找一个元素时，要检查所有的表项，知道找到所需的元素，或者最终发现元素不在表中。不像在链接法中，这里没有链表，也没有元素存放在散列表外。在这里散列表有可能会被填满，但是装载因子（动态集合元素/散列槽数）绝对不会大于1。
在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项，直到找到一个空槽来放置这个元素为止。检查顺序可以是线性的，可以是二次的，也可以是再次散列的。
查找关键字和插入关键字的算法基本上是一样的。
在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将NIL置于其中来标识它为空。因为这样做的话，会导致在插入另外的关键字探查过程中，有可能无法检索某些关键字。这里有一个解决方法，就是在槽i中置一个特定的槽当作空槽，从而可以插入新元素。
1.线性探查给定一个普通的散列函数h’:U->{0,1,2…m-1}(称为辅助散列函数)，线性探查方法采用的散列函数为：h(k,i)=(h’(k)+i) mod m , i=0,1,2,…m-1
给定一个关键字k，第一个探查的槽式T(h’(k)),接下来探查下一个槽，知道T[m-1]。
线性探查方法比较容易实现，但存在一个问题，成为一次群集。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。群集现象很容易出现，这是因为当一个空槽前有i个满的槽时，该空槽为下一个将被占用的槽的概率是(i+1)/m，连续被占用的槽的序列将会变得越来越长，因而平均查找时间也会随之增加。2.二次探查（quadratic probing）采用的形式如下：
h(k,i)=(h’(k)+c1i+c2i)modm
其中h’是一个辅助散列函数，c1和c2为辅助常数，i=0,1,…m-1。处事的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。3.双重散列是用在开放寻址法的最好方法之一，因为它所产生的排列具有随机选择的排列的许多特性。它采用如下形式的散列函数：
h(k,i)=(h1(k)+i*h2(k))modm
其中h1和h2是辅助散列函数。初始探查位置为T[h1(k)],后续的探查位置在此基础上加上偏移量h2(k)模m。与线性探查和二次探查不同的是，这里的探查序列以两种方式依赖于k，因为初始探查位置和偏移量都可能发生变化。