哈希冲突解决方法_哈希冲突的解决

哈希

哈希（散列）是一种数据结构，通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系，如果要查、改数据，就可以直接到对应的位置去，使得时间复杂度达到了 O(1) ，原因如下：

若结构中存在和 关键字K 相等的记录，则必定在 f(K) 的存储位置上。由此，不需比较便可直接取得所查记录。

称上面的对应关系 f 为 散列函数（Hash function），按这个映射关系事先建立的表为散列表，这一映象过程称为 散列造表 或 散列 ，最终所得的存储位置称 散列地址 。

哈希（散列）函数

哈希函数用来建立元素与其存储位置的映射关系。

对于哈希函数来说，必须具有以下特点：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
• 哈希函数计算出来的地址能均匀分布在整个空间中（防止产生密集的哈希冲突）

哈希冲突大量出现往往都是因为哈希函数设计的不够合理，但是即使再优秀的哈希函数，也只能尽量减少哈希冲突的次数，无法避免哈希冲突。

常见的哈希函数

1. 直接定址法（常见）
   哈希函数：Hash(Key) = A * Key + B
   这是最简单的哈希函数，直接取关键字本身或者他的线性函数来作为散列地址。

2. 除留余数法（常见）
   哈希函数 ：Hash(key) = key % capacity
   几乎是最常用的哈希函数，用一个数来对 key 取模，一般来说这个数都是容量。

3. 平方取中法
   对关键字进行平方，然后取中间的几位来作为地址。

4. 折叠法
   折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和（去除进位），并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况.

5. 随机数法
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key)，其中 random 为随机数函数。通常应用于关键字长度不等时。

6. 数学分析法
   分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

字符串哈希函数

因为哈希函数的常用方法如直接定址、除留余数、平方取中等方法需要用的 key值 为整型，而大部分时候我们的 key 都是 string，由于无法对 string 进行算数运算，所以需要考虑新的方法。

常见的字符串哈希算法有 BKD、SDB、RS 等，这些算法大多通过一些公式来对字符串每一个 字符的 ascii值 或者 字符串的大小 进行计算，来推导出一个不容易产生冲突的 key值 。

例如 BKDHash ：

struct _Hash<std::string> { 
    const size_t& operator()(const std::string& key) { 
    // BKDR字符串哈希函数 size_t hash = 0; for (size_t i = 0; i < key.size(); i++) { 
    hash *= 131; hash += key[i]; } return hash; } }; 

这里推荐两篇文章，一篇具体对比各类字符串哈希函数的效率，一篇是实现：

• 字符串Hash函数对比
• 各种字符串Hash函数

哈希冲突

对不同的关键字可能得到同一散列地址，即 key1≠key2 ，而 f(key1)=f(key2) ，这种现象称碰撞（哈希冲突）。

哈希冲突使得多个数据映射的位置相同，但是每个位置又只能存储一个数据，所以就需要通过某种方法来解决哈希冲突。

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

1. 散列函数是否均匀；
2. 处理冲突的方法；
3. 散列表的负载因子（装填因子）。

第一点取决于上面讲过的哈希函数，不再赘述，下面详细讲一下2、3点。

处理冲突的方法可分为两类：开散列方法( open hashing，也称为拉链法，separate chaining ) 和 闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。

闭散列（开放地址法）

因为闭散列是顺序的结构，所以可以通过遍历哈希表，来将冲突的数据放到空的位置上。

1. 线性探测
   线性探测即为从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
   这种方法实现起来极为简单，但是效率也不高，因为如果同一位置产生了大量的哈希冲突，就会导致每次都在同一个位置进行探测，例如我在10这里连续冲突100次，此时所有探测的次数加起来就会高达100！

2. 二次探测
   二次探测即为从发生冲突的位置开始，每次往后探测 ±k²(k<=m/2，m为散列表长) 个位置，如：1²，-(1²)，2²，-(2²) 等。
   这样的话就将每次探测的效率从 O(N) 提升到了 O(logN) ，即使有着大量的冲突堆积，也不会导致效率过低。

3. 伪随机数探测
   这种方法并不常见，实现方法是：创建一个伪随机数序列，根据序列内容决定每次往后探测的长度。

开散列（链地址法/拉链法）

先用哈希函数计算每个数据的散列地址，把具有相同地址的元素归于同一个集合之中，把该集合处理为一个链表，链表的头节点存储于哈希表之中。

链地址法在每一个映射位置都建立起一个链表（数据过多时可能会转为建立红黑树），将每次插入的数据都直接连接上这个链表，这样就不会像闭散列一样进行大量的探测，但是如果链表过长也会导致效率低下。

负载因子以及增容

哈希冲突出现的较为密集，往往代表着此时数据过多，而能够映射的地址过少，而要想解决这个问题，就需要通过 负载因子（装填因子） 的判断来进行增容。

负载因子的大小 = 表中数据个数 / 表的容量（长度）

对于闭散列

对于闭散列来说，因为其是一种线性的结构，所以一旦负载因子过高，就很容易出现哈希冲突的堆积，所以当负载因子达到一定程度时就需要进行增容，并且增容后，为了保证映射关系，还需要将数据重新映射到新位置。

经过算法科学家的计算， 负载因子应当严格的控制在 0.7-0.8 以下，所以一旦负载因子到达这个范围，就需要进行增容。

因为除留余数法等方法通常是按照表的容量来计算，所以科学家的计算，当对一个质数取模时，冲突的几率会大大的降低，并且因为增容的区间一般是 1.5-2 倍，所以算法科学家列出了一个增容质数表，按照这样的规律增容，冲突的几率会大大的降低。

这也是 STL 中 unordered_map/unordered_set 使用的增容方法。

//算法科学家总结出的一个增容质数表，按照这样增容的效率更高 const int PRIMECOUNT = 28; const size_t primeList[PRIMECOUNT] = { 
    53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul, ul }; 

hashmap 的负载因子为什么默认是 0.75 ？

比如说当前的容器容量是 16，负载因子是 0.75,16*0.75=12，也就是说，当容量达到了 12 的时候就会进行扩容操作。而负载因子定义为 0.75 的原因是：

• 当负载因子是 1.0 的时候，也就意味着，只有当散列地址全部填充了，才会发生扩容。意味着随着数据增长，最后势必会出现大量的冲突，底层的红黑树变得异常复杂。虽然空间利用率上去了，但是查询时间效率降低了。
• 负载因子是 0.5 的时候，这也就意味着，当数组中的元素达到了一半就开始扩容。虽然时间效率提升了，但是空间利用率降低了。 诚然，填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是，这时候空间利用率就会大大的降低，原本存储 1M 的数据，现在就意味着需要 2M 的空间。

对于开散列结构

因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多，随着数据的增多，就可能会导致某一个桶过重，使得效率过低。

所以最理想的情况，就是每个桶都有一个数据。这种情况下，如果往任何一个地方插入，都会产生哈希冲突，所以当数据个数与桶的个数相同时，也就是负载因子为 1 时就需要进行扩容。

具体实现

哈希表（闭散列）

创建

对于闭散列，我们需要通过状态来记录一个数据是否在表中，所以这里会使用枚举来实现。

enum State { 
    EMPTY,//空 EXITS,//存在 DELETE,//已经删除 }; template<class T> struct HashData { 
    HashData(const T& data = T(), const State& state = EMPTY) : _data(data) , _state(state) { 
   } T _data; State _state; }; 

插入

插入的思路很简单，计算出映射的地址后，开始遍历判断下面几种状态：

• 如果映射位置已存在数据，并且值与当前数据不同，则说明产生冲突，继续往后查找
• 如果映射位置的数据与插入的数据相同，则说明此时数据已经插入过，此时就不需要再次插入
• 如果映射位置的状态为删除或者空，则代表着此时表中没有这个数据，在这个位置插入即可

bool Insert(const T& data) { 
    KeyOfT koft; //判断此时是否需要增容 //当装填因子大于0.7时增容 if (_size * 10 / _table.size() >= 7) { 
    //增容的大小按照别人算好的近似两倍的素数来增，这样效率更高，也可以直接2倍或者1.5倍。 std::vector<HashData> newTable(getNextPrime(_size)); for (size_t i = 0; i < _table.size(); i++) { 
    //将旧表中的数据全部重新映射到新表中 if (_table[i]._state == EXITS) { 
    //如果产生冲突，则找到一个合适的位置 size_t index = HashFunc(koft(_table[i]._data)); while (newTable

今天的文章
哈希冲突解决方法_哈希冲突的解决分享到此就结束了，感谢您的阅读。