- 因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。
a)开放地址法
这个方法的基本思想是：
- 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
这个过程可用下式描述：
Hi (key) = ( H (key)+ di ) mod m ( i = 1,2,……,k (k ≤ m – 1) )
- 其中：
H (key)为关键字key的直接哈希地址，m为哈希表的长度，di为每次再探测时的地址增量。 - 采用这种方法时，首先计算出元素的直接哈希地址
H (key)，如果该存储单元已被其他元素占用，则继续查看地址为H (key) + d2的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key 的数据元素存放到该单元。 - 增量 d 可以有不同的取法，并根据其取法有不同的称呼：
（1） di ＝ 1 ， 2 ， 3 ， …… 线性探测再散列；
（2） di ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列；
（3） di ＝ 伪随机序列 伪随机再散列；
例1 设有哈希函数 H (key) = key mod 7 ，哈希表的地址空间为 0 ～ 6，对关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）按线性探测再散列和二次探测再散列的方法分别构造哈希表。
解：
（1）线性探测再散列：
- 32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ；
- 55 ％ 7 = 6 发生冲突，下一个存储地址（ 6＋1 ）％ 7 ＝ 0 ，仍然发生冲突，再下一个存储地址：（ 6＋2 ）％ 7 ＝ 1 未发生冲突，可以存入。
- 22 ％ 7 ＝ 1 发生冲突，下一个存储地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未发生冲突；
- 38 ％ 7 ＝ 3 ；
- 21 ％ 7 ＝ 0 发生冲突，按照上面方法继续探测直至空间 5 ，不发生冲突，所得到的哈希表对应存储位置：
- 下标： 0 1 2 3 4 5 6
- 49 55 22 38 32 21 13
（2）二次探测再散列：
- 下标： 0 1 2 3 4 5 6
- 49 22 21 38 32 55 13
注意????：对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎，不能直接地删除，因为这样将会截断其他具有相同哈希地址的元素的查找地址，所以，通常采用设定一个特殊的标志以示该元素已被删除。
b)再哈希法
- 当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
- 比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止。
c)链地址法
将所有关键字为同义词的记录存储在同一线性链表中。
如下：
d)建立一个公共溢出区
- 假设哈希函数的值域为
[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。