一、哈希概念

顺序结构以及平衡树中，元素key与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过key的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即，搜索的效率取决于搜索过程中元素的比较次数。

效率最高的搜索方法：不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的key之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

1.插入和查找

向该结构中插入元素和查找元素时：

插入元素：将元素key存放到用hashFunc计算出的元素key的位置。

查找元素：对元素的key进行计算，把用hashFunc计算的函数值当做元素的存储位置，在哈希结构中按此位置取元素比较，若key相等，则查找成功。

2.哈希表

哈希方法中使用的转换函数称为哈希函数（也叫散列函数），来建立映射关系，构造出来的结构称为哈希表 (Hash Table)(也叫散列表)。

如有数据集合{ 5,2,6,8,9,7}，假如哈希函数设置为：

hash(key) = key % capacity

其中capacity为存储元素底层空间总大小

按照这种方法查找不用拿key多次比较，因此查找的速度比较快。

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突。当再插入别的元素时，有可能发生哈希冲突，比如插入22，hashFunc(22) = 22%10 = 2，2的位置已经存了数据2了，那么22该如何存储呢？

引起哈希冲突的原因：哈希函数设计不合理。哈希函数设计原则包括：

（1）哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

（2）哈希函数计算出来的地址能均匀分布在整个空间中

（3）哈希函数应比较简单

3.常见的哈希函数

（1）直接定址法

取关键字的某个线性函数为散列地址：Hash(key)= A*key + B

优点：简单，速度快，节省空间，查找key O(1)的时间复杂度

缺点：当数据范围大时会浪费空间，不能处理浮点数，字符串数据

使用场景：适用于整数，数据范围比较集中

例如计数排序，统计字符串中出现的用26个英文字符统计，给数组分配26个空间，遍历到的字符是谁，就把相应的元素值++

（2）除留余数法

把数据映射到有限的空间里面。设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将key转换成哈希地址。如第2节哈希表的例子。

哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

解决哈希冲突最常用的方法是闭散列和开散列。

二、用闭散列解决哈希冲突

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。下一个位置怎样找呢？有以下两种常见方式：

1.线性探测法介绍

如下场景，要插入22，通过哈希函数hashfunc(22) = 22%10=2计算出的地址为2，2的位置已经有数据2了，现在发生了冲突：

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

①插入：通过哈希函数获取待插入元素在哈希表中的位置。如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

②删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，否则会影响其他元素的搜索。比如删除元素2，如果直接删除掉，22查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素，即给每个位置一个标记，用空、存在、删除3种状态来区分。

负载因子 = 存储的有效数据个数/空间的大小

负载因子越大，冲突的概率越高，增删查改效率越低

负载因子越小，冲突的概率越低，增删查改的效率越高，但是空间利用率低，浪费多。

负载因子 <1，就能保证发生哈希冲突时一定能找到空位置

2.线性探测的实现

（1）状态

区分哈希表的一个位置有没有数据，如果用两种状态表示，在(1)或不在(0)，那么就会带来两个问题：

①0表示不在，那么如何存数据0呢？

②如果数据发生冲突，当前位置和后面位置都存放的是冲突数据，加入当前位置的数据被删除了，那么查找key时发现当前位置状态为不在，那么就不会再向后查找了。

因此要用3个状态位分别表示空、已占用、已删除，用枚举表示状态位：

1. #pragma once
2. #include<vector>
3. #include<iostream>
4. using namespace std;
5. 
6. namespace CloseHash
7. {
8. //当前位置的状态有3种：空、已存在、已删除
9.  enum State
10.   {
11.     EMPTY,
12.     EXIST,
13.     DELETE,
14.   }; 
15. }

（2）定义HashData

哈希数据应包含两个成员：数据和状态

1.  template<class K, class V>
2.  struct HashData
3.  {
4.    pair<K, V> _kv;//数据
5.    State _state = CloseHash::State::EMPTY;//状态
6.  };

（3）哈希表

哈希表包含两个成员：哈希数据、存储的有效数据的个数

模板有3个参数K、V、HashFunc。

①由于不知道key是K还是pair，所以需要定义两个模板参数K、V来包含key是K或pair的两种情况

②由于不知道key的数据类型是int还是string、pair、struct，计算key的映射位置时需要取模，但是只能对int型取模，string、struct、pair无法取模，HashFunc作为仿函数，它的实例可以分别应对这些类型的取模。

1. template<class K, class V, class HashFunc>
2.  class HashTable
3.  {
4. private:
5.    vector<HashData<K, V>> _table;//哈希表
6.    size_t _n = 0;//存储有效数据的个数
7.  };

（4）查找

①无论传给哈希表的数据是K还是pair，查找时，都需要用K做key来进行查找

②计算元素位置

③如果当前位置元素为key，那么就返回该元素，否则可能发生了冲突，继续向后探测

1.  public:
2. //用K查找
3.    HashData<K,V>* Find(const K& key)
4.         {
5.  if (_table.size() == 0)
6.          {
7.    return nullptr;
8.          }
9. 
10.           HashFunc hf;//仿函数
11.   size_t start = hf(key) % _table.size();//除留余数法，查找元素位置
12.   size_t index = start;
13.   size_t i = 1;
14.   while (_table[index]._state != EMPTY)
15.           {
16.     if (_table[index]._state == EXITS 
17.               && _table[index]._kv.first == key)//找到了
18.             {
19.       return &_table[index];//该位置存在且值为key返回地址方便对该数据进行修改
20.             }
21. 
22.         //冲突时，向后查找
23.             index = start + i;//线性探测  //index = start + i*i;//二次探测
24.             index %= _table.size();
25.             ++i;
26.           }
27. 
28.   return nullptr;
29.         }

（5）插入

①先查看key查看在不在，在就插入失败

②第一次插入时，哈希表的的是0，所以第一次插入时就要让表扩容

③还需要判断负载因子是否>0.7，如果表满了，就要开一个新表，并把旧表的数据都插入到新表上

④当计算的位置有数据时，就向后探测，直到探测到空位置即可存入数据

1.    bool Insert(const pair<K, V>& kv)
2.    {
3.      HashData<K, V>* ret = Find(kv.first);
4.      if (ret)
5.      {
6.        return false;
7.      }
8. 
9.      if (_table.size() == 0)
10.       {
11.         _table.resize(10);
12.       }
13.       else if ((double)_n / (double)_table.size() > 0.7)//负载因子 > 0.7， 需要增容
14.       {
15.         HashTable<K, V, HashFunc> newHashTable;
16.         newHashTable._table.resize(2 * _table.size());
17. 
18.         for (auto& e : _table)
19.         {
20.           if (e._state == EXIST)
21.           {
22.             newHashTable.Insert(e._kv);
23.           }
24.         }
25. 
26.         _table.swap(newHashTable._table);
27.       }
28. 
29.       HashFunc hf;
30.       size_t start = hf(kv.first) % _table.size();
31.       size_t index = start;
32. 
33.       //探测后面的位置---线性探测
34.       size_t i = 1;
35.       while (_table[index]._state == EXIST)
36.       {
37.         //状态为State时，就发生了冲突，需要向后找空位置
38.         index = start + i;
39.         index %= _table.size();
40.         ++i;
41.       }
42. 
43.       //找到空位置就存入数据
44.       _table[index]._kv = kv;
45.       _table[index]._state = EXIST;
46.       ++_n;
47. 
48.       return true;
49.     }
50. 
51.     //用K查找
52.     HashData<K, V>* Find(const K& key)
53.     {
54.       if (_table.size() == 0)
55.       {
56.         return nullptr;
57.       }
58. 
59.       HashFunc hf;//仿函数
60.       size_t start = hf(key) % _table.size();//除留余数法，查找元素位置
61.       size_t index = start;
62.       size_t i = 1;
63.       while (_table[index]._state != EMPTY)
64.       {
65.         if (_table[index]._state == EXITS
66.           && _table[index]._kv.first == key)//找到了
67.         {
68.           return &_table[index];//该位置存在且值为key返回地址方便对该数据进行修改
69.         }
70. 
71.         //冲突时，向后查找
72.         index = start + i;//线性探测  //index = start + i*i;//二次探测
73.         index %= _table.size();
74.         ++i;
75.       }
76. 
77.       return nullptr;
78.     }

（6）删除

利用假删除，将状态标记为删除即可：

1.    //删除
2.    bool Erase(const K& key)
3.    {
4.      HashData<K, V>* ret = Find(key);
5.      if (ret == nullptr)//没找到
6.      {
7.        return false;
8.      }
9.      else//找到了
10.       {
11.         ret->_state = DELETE;
12.         --_n;
13. 
14.         return false;
15.       }
16.     }

（7）仿函数

仿函数的目的是为了让不同类型的数据能够取模，方便计算数据位置

类的仿函数模板，默认支持int：

1. template<class K>
2.  struct Hash
3.  {
4.    size_t operator()(const K& key)
5.    {
6.      return key;
7.    }
8.  };

string类型的仿函数，不能用上述仿函数的类模板，因为字符不能取模。string类型的仿函数用来做key的数值尽量要找不重复的，否则会导致发生冲突的概率比较高

1.  struct StringHashFunc
2.  {
3.    //采用BKDR哈希（乘以质数，如131）,会减少冲突
4.    size_t operator()(const string& s)
5.    {
6.      size_t value = 0;
7. //取每个字符*131之后的和
8.      for (auto e : s)
9.      {     
10.         value += e;
11.         value *= 131;
12.       }
13.       return value;
14.     }
15.   };

任意类型（pair、结构体）都可以做key，key尽量选择不容易重复的成员，跟一个把这个类型对象转换成整形的仿函数。比如一个类型做map/set的key，那就要求该类型能支持比较大小。又比如一个类型做unordered_map/unordered_set的key，那就要求该类型能支持转换成整形+相等比较。

（8）完整代码段

HashTable.h

1. #pragma once
2. #include<vector>
3. #include<iostream>
4. using namespace std;
5. 
6. namespace CloseHash
7. {
8.  //当前位置的状态有3种：空、已存在、删除
9.  enum State
10.   {
11.     EMPTY,
12.     EXIST,
13.     DELETE,
14.   };
15. 
16.   template<class K, class V>
17.   struct HashData
18.   {
19.     pair<K, V> _kv;
20.     State _state = EMPTY;
21.   };
22. 
23.   //默认支持整形
24.   template<class K>
25.   struct Hash
26.   {
27.     size_t operator()(const K& key)
28.     {
29.       return key;
30.     }
31.   };
32. 
33.   //对常用string类型模板特化
34.   template<>
35.   struct Hash<string>
36.   {
37.     size_t operator()(const string& s)
38.     {
39.       size_t value = 0;
40.       for (auto e : s)
41.       {
42.         value += e;
43.         value *= 131;
44.       }
45.       return value;
46.     }
47.   };
48. 
49. 
50.   template<class K, class V, class HashFunc = Hash<K>>
51.   class HashTable
52.   {
53.   public:
54.     bool Insert(const pair<K, V>& kv)
55.     {
56.       HashData<K, V>* ret = Find(kv.first);
57.       if (ret)
58.       {
59.         return false;
60.       }
61. 
62.       if (_table.size() == 0)
63.       {
64.         _table.resize(10);
65.       }
66.       else if ((double)_n / (double)_table.size() > 0.7)//负载因子 > 0.7， 需要增容
67.       {
68.         HashTable<K, V, HashFunc> newHashTable;
69.         newHashTable._table.resize(2 * _table.size());
70. 
71.         for (auto& e : _table)
72.         {
73.           if (e._state == EXIST)
74.           {
75.             newHashTable.Insert(e._kv);
76.           }
77.         }
78. 
79.         _table.swap(newHashTable._table);
80.       }
81. 
82.       HashFunc hf;
83.       size_t start = hf(kv.first) % _table.size();
84.       size_t index = start;
85. 
86.       //探测后面的位置---线性探测
87.       size_t i = 1;
88.       while (_table[index]._state == EXIST)
89.       {
90.         //状态为State时，就发生了冲突，需要向后找空位置
91.         index = start + i;
92.         index %= _table.size();
93.         ++i;
94.       }
95. 
96.       //找到空位置就存入数据
97.       _table[index]._kv = kv;
98.       _table[index]._state = EXIST;
99.       ++_n;
100. 
101.      return true;
102.    }
103. 
104.    //用K查找
105.    HashData<K, V>* Find(const K& key)
106.    {
107.      if (_table.size() == 0)
108.      {
109.        return nullptr;
110.      }
111. 
112.      HashFunc hf;//仿函数
113.      size_t start = hf(key) % _table.size();//除留余数法，查找元素位置
114.      size_t index = start;
115.      size_t i = 1;
116.      while (_table[index]._state != EMPTY)
117.      {
118.        if (_table[index]._state == EXITS
119.          && _table[index]._kv.first == key)//找到了
120.        {
121.          return &_table[index];//该位置存在且值为key返回地址方便对该数据进行修改
122.        }
123. 
124.        //冲突时，向后查找
125.        index = start + i;//线性探测  //index = start + i*i;//二次探测
126.        index %= _table.size();
127.        ++i;
128.      }
129. 
130.      return nullptr;
131.    }
132. 
133.    //删除
134.    bool Erase(const K& key)
135.    {
136.      HashData<K, V>* ret = Find(key);
137.      if (ret == nullptr)
138.      {
139.        return false;
140.      }
141.      else
142.      {
143.        ret->_state = DELETE;
144.        --_n;
145. 
146.        return false;
147.      }
148.    }
149.  private:
150.    vector<HashData<K, V>> _table;//哈希表
151.    size_t _n = 0;//存储有效数据的个数
152.  };
153. 
154.  void test_CloseHashInt()
155.  {
156.    int a[] = { 6,201,35,76,89,2 };
157.    HashTable<int, int> ht;
158.    //ht.Insert(make_pair<6, 6>);
159.    for (auto e : a)
160.    {
161.      ht.Insert(make_pair(e,e));
162.    }
163.  }
164. 
165.  void test_CloseHashString()
166.  {
167.    string a[] = { "篮球","足球","篮球","篮球","羽毛球","羽毛球","乒乓球","羽毛球" };
168.    HashTable<string, int> ht;
169.    //ht.Insert(make_pair(6, 6));
170.    for (auto e : a)
171.    {
172.      auto ret = ht.Find(e);
173.      if (ret)
174.      {
175.        ret->_kv.second++;
176.      }
177.      else
178.      {
179.        ht.Insert(make_pair(e, 1));
180.      }
181.    }
182.  }
183. }

Test.cpp

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "HashTable.h"
3. 
4. int main()
5. {
6.  CloseHash::test_CloseHashInt();
7.  CloseHash::test_CloseHashString();
8. 
9.  return 0;
10. }

【C++】-- 哈希算法（一）

一、哈希概念

1.插入和查找

2.哈希表

3.常见的哈希函数

（1）直接定址法

（2）除留余数法

二、用闭散列解决哈希冲突

1.线性探测法介绍

2.线性探测的实现

（1）状态

（2）定义HashData

（3）哈希表

（4）查找

（5）插入

（6）删除

（7）仿函数

（8）完整代码段

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】-- 哈希算法（一）

一、哈希概念

1.插入和查找

2.哈希表

3.常见的哈希函数

（1）直接定址法

（2）除留余数法

二、用闭散列解决哈希冲突

1.线性探测法介绍

2.线性探测的实现

（1）状态

（2）定义HashData

（3）哈希表

（4）查找

（5）插入

（6）删除

（7）仿函数

（8）完整代码段

热门文章

最新文章

相关课程

相关电子书

相关实验场景