hash冲突解决

 

1、开放地址法有一个公式: m是hash表长度,di 是产生冲突的时候的增量序列

 

fi(key) = (f(key)+di) MOD m;   

找到 fi(key) 位置空的放入此位置 ,当达到表尾m-1时，又从0开始探查.

 

a.线性探测法   (di=0,1,2,3,......,m-1)  

b.二次探测法（线性补偿探测法）   di=i^2,di=- (i^2); i=0,1,2,3,(m-1)/2

c.随机探测   di 是一组伪随机数列   使用一个确定性的算法计算出来的似乎是随机的数序，因此伪随机数实际上并不随机  比如电脑上的时间作为计算伪随机数的开始值。

 

2、再哈希法

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

比如字符串安装第一个字母进行哈希，如果产生冲突可以按照第二个字母进行哈希，再冲突，第三个，直到不冲突为止

 

3、链地址法

将所有关键字为同义词的记录存储在同一线性链表中。如下：

 

 

4、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

经过以上方法，基本可以解决掉hash算法冲突的问题。

注:之所以会简单得介绍了hash，是为了更好的学习lzw算法，学习lzw算法是为了更好的研究gif文件结构，最后，我将详细的阐述一下gif文件是如何构成的，如何高效操作此种类型文件。