开放地址法

再hash的方法

拉链法

建立公共溢出区法

 

开放地址法：

1. 基本思想：当发生地址冲突的时候，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止；  

2. 所用公式 Hi(key) = [H(key) + di]mod m;其中i = 1、2、3.....k（k<m-1）

H(key)为关键字key的直接hash地址

m为hash表的长度

di为再次探测时的地址增量

 

再hash的方法：

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突。缺点：计算时间增加

 

拉链法：

在HashMap中就是使用拉链法来解决hash冲突的问题的；

将hash冲突的记录存储在统一链表中

 

建立公共溢出区：

建立公共溢出区的基本思想是：假设哈希函数的值域是[1,m-1]，则设向量HashTable[0...m-1]为基本表，每个分量存放一个记录，另外设向量OverTable[0...v]为溢出表，所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。