如何巧妙处理哈希表中的长尾词冲突问题？

本文共计1280个文字，预计阅读时间需要6分钟。

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

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

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

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。