一、哈希概念

顺序结构以及平衡树中，元素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++】-- 哈希算法（一）