解决hash冲突的常用方法

开放地址法

1.线性探查法

从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

2.平方探查法

平方探查法即是发生冲突时，用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空闲单元。在实际操作中，平方探查法不能探查到全部剩余的单元。

3.双散列函数探查法

该方法是开放地址法中最好的方法之一，它的探查序列是：
hi=(h(key)+ih1(key))%m 0≤i≤m-1 //即di=ih1(key)
即探查序列为：
d=h(key)，(d+h1(key))%m，(d+2h1(key))%m，…，等。
该方法使用了两个散列函数h(key)和h1(key)，故称为双散列函数探查法。

拉链法

将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0…m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。

再哈希法

就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。

建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。