数据结构中散列表（哈希表）经典之冲突处理

来源：互联网收集：自由互联发布时间：2021-09-03

散列是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)，建立了关键字与存储位置的相互对应关系，这种关系 f 称为散列函数（

散列是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)，建立了关键字与存储位置的相互对应关系，这种关系 f 称为散列函数（哈希函数）。本文小编主要讲述散列函数的冲突处理问题。

未标题-1.jpg

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

1. 散列函数是否均匀；

2. 处理冲突的方法；

3. 散列表的装填因子。

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

解决哈希冲突的方法一般有：

NO.1开放定址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

公式：f(key)=(f(key)+di)%m(di=1,2,3….m-1)

比如说，关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，表长为12。散列函数f(key) = key mod 12。

当计算前5个数{12, 67, 56, 16, 25}时，都是没有冲突的散列地址，直接存入；计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。于是应用上面的公式f(37) = (f(37) + 1) mod 12 =2,。于是将37存入下标为2的位置。接下来22,29,15,47都没有冲突，正常的存入。到了48，计算得到f(48) = 0，与12所在的0位置冲突了，不要紧，我们f(48) = (f(48) + 1） mod 12 = 1，此时又与25所在的位置冲突。于是f(48) = (f(48) + 2） mod 12 = 2，还是冲突......一直到f(48) = (f(48) + 6） mod 12 = 6时，才有空位，如下表所示。

序号01234567891011关键字1225

16

6756

NO.2再哈希法

对于散列表来说，可以事先准备多个散列函数。

公式：fi(key)=RHi(key)(i=1,2,3…,k)

这里RHi 就是不同的散列函数，可以把除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算。

这种方法能够使得关键字不产生聚集，但相应地也增加了计算的时间。

NO.3链地址法（拉链法）

将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表前面的指针。对于关键字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，用前面同样的12为余数，进行除留余数法，可以得到下图结构。