认识哈希以及哈希表的模拟实现

1.什么是哈希

概念：哈希（hash）又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字key跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出key存储的位置，进行快速地查找

举个例子：

哈希最简单的一种方式就是直接定址法，当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，如一组关键字值都在[a,z]的小写字母，那么我们就可以开一个有26个空间的数组，每个关键字通过一个哈希函数计算出要存储在数组空间的位置，该哈希函数可以为用每个关键字的ASCII码值减去a的ASCII码值，得到的结果就是它们要存储位置的下标，也就是说直接定址法就是用关键字计算出一个绝对位置或者相对位置。当然该种方法也是有缺点的，当关键字的范围比较分散时，就很浪费内存甚至不够用。

所以，哈希的本质就是，通过某一种特定的规则，映射到某个存储空间，将关键字存储到这个空间，那么在查找或者删除时也通过该规则找到这个关键字，这样就提高了查找的效率

2.哈希函数

2.1 除留余数法/除法散列法

假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。当使用除留余数法时们要尽量避免M为某些值，如2的幂，10的幂。如果是2^x，那么key模上2的x次方就相当于保留key后面的后x位，那么后x位相同的值，计算出来都是一样的，映射位置就冲突了，例如：63和31这两个数，然后取M为16，也就是2的4次方，那么63和31通过哈希函数计算出来的结果都为15，因为63和31的二进制位的后4位是相同的，导致结果一样。如果M取10的幂那么就更明显了。所以使用该方法时，建议取M不太接近2的整数次幂的一个质数（素数）

2.2 乘法散列法

乘法散列法对哈希的大小M不做要求，第一步：用关键字key乘上常数A(0<A<1)，并抽取出key*A的小数部分，第二步：再用M乘上得到的小数部分，再向下取整。也就是说哈希函数为：h(key) = floor(M x ((A x key)%0.1))，其中floor表示对表达式向下取整，A的取值最好为0.6180339887…（黄金分割点）

2.3 全域散列法

全域散列法主要用于，防止我们使用的哈希函数遭到破坏，比如针对我们提供的哈希函数，特意构造一个发生严重冲突的数据集，导致所有关键字都落到同一个位置。解决这种问题的方法就是给我们的哈希函数增加随机性，也就是全域散列法。哈希函数为：h(key) = ((a x key + b) % P)% M，其中P要选一个足够大的素数，a可以选1~P-1的任意整数，b可以选0到P-1的任意整数，这些函数构成了一个P*（P-1）组全域散列组。需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续的增删查改也要使用这个散列函数，否则就导致找不到插入的key了

以上是几种常见的制定哈希函数的方法

3.哈希冲突

概念：当两个不同的key映射到同一个位置时，这种情况就叫作哈希冲突或者哈希碰撞

我们知道即使设计了优秀的哈希函数，但是哈希冲突是不可避免的，选择优秀的哈希函数只是尽可能地减少冲突。那么有什么办法可以解决冲突呢，来看下面几种方法

4.解决哈希冲突的方法

4.1 开放定址法

在开放定址法中所有元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则再按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于的，这里的规则有三种如下：

• 线性探测：从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。用除留余数法计算出h(key) = hash0 = key % M，若hash0的位置冲突了，则线性探测：h(key,i) = hashi = (key + i) % M，i的取值为0到M-1，因为负载因子小于1，负载因子为存储值的个数比上空间个数，则最多探测M - 1次，一定能找到一个存储key的位置。如下图举例：

• 二次探测：从发生冲突位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希为，则回绕到哈希表头的位置；如果往左走到哈希头，则回绕到哈希表尾的位置，用除留余数法计算出h(key)=hash0=key%M,若hash0冲突了，则二次探测：h(key,i)=hashi=(hash0 ± i^2)%M，i的取值为0到M/2，当hashi小于0时需要hashi+=M，如下图举例：

• 双重探测(了解)：第一个哈希函数计算出的值发生冲突，使第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。h(key)=hash0=key%M，发生冲突时，双重探测公式为：hc(key,i)=hashi=(hash0+i*h2(key))%M，i的取值为1到M，要h2(key)<M，且它们互为质数。

4.1.1 用除留余数法和线性探测模拟实现简单的哈希表

代码如下：

#pragma once
#include <iostream>
#incldue <vector>
using namespace std;//用于表示存储空间的状态
enum State
{EXIST,DELETE,EMPTY
};
template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY; //存储哈希表中存储空间的状态
};//由于哈希表对关键字的要求是支持关键字能取模、且还能支持比较关键字相等
//所以我们需要通过用仿函数取去控制关键字
template<class K>
class HashFunc
{
public:const size_t operator()(const K& key){return (size_t)key;}
};//由于string作为关键字经常被用到，所以可以对string转整型的仿函数作特化
template<>
class HashFunc<string>
{
public:const size_t operator()(const string& key){size_t ret = 0;for (auto& s : key){//使string的每个ASCII码值都参与运算，得到不同的关键字ret += s;ret *= 131;}return ret;}
};template<class K,class V,class Hash = HashFunc<K>> //由于int类型的关键字经常用，所以用来作缺省值
class HashTable
{
public://sgi版本的哈希表inline unsigned long _stl_next_prime(unsigned long n){static const int _stl_num_primes = 28;static const unsigned long _stl_primes_list[_stl_num_primes] ={53,        97,        193,        389,        769,1543,      3079,      6151,       12289,      24593,49157,     98317,     196613,     393241,     786433,1572869,   3145739,   6291469,    12582917,   25165843,50331653,  100663319, 201326611,  402653189,  805306457,1610612741,           3221225473,             4294967291};const unsigned long* first = _stl_primes_list;const unsigned long* last = _stl_primes_list + _stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);//lower_bound()在迭代器的范围内取>=n的最小值return pos == last ? *(pos - 1) : *(pos);}HashTable(){//提前开好第一个质数大小的空间_tables.resize(_stl_next_prime(1));}bool insert(const pair<K, V>& kv){if (find(kv.first))return false; //次模拟实现不允许冗余//当负载因子过大时，就会扩容，负载因子一般到0.7就扩容了//扩容这里还是按照扩2倍的方式扩容，但是要保持哈希的大小是一个质数，当第一个是质数，//扩2倍就不是质数了，如何解决这样的问题呢，使用sgi版本的哈希表，它提供了一个近似2倍的质数表//我们可以每次去质数表中获取扩容后的大小即可if ((double)_n / (double)_tables.size() >= 0.7){//获取质数表中比当前质数还要大的下一个质数size_t newsize = _stl_next_prime(_tables.size() + 1);//由于扩容了之后，哈希表的大小发生了变化，所以哈希表里面的值需要重新映射//创建一个哈希表对象，开一个newsize大小的空间，调用insert函数HashTable<K, V, Hash> newhs;newhs._tables.resize(newsize);//遍历旧表，将值全部映射到新的哈希表for (int i = 0; i<_tables.size(); ++i){if (_tables[i]._state == EXIST){newhs.insert(_tables[i]._kv);}}_tables.swap(newhs._tables);}Hash hs;size_t hash0 = hs(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state == EXIST){//说明存在冲突//使用线性探测解决冲突hashi = (hash0 + i) % _tables.size();++i;}//说明该hashi的位置为EMPTY或DELETE_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* find(const K& key){Hash hs;size_t hash0 = hs(key) % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}//线性探测hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool erase(const K& key){HashData<K, V>* ret = find(key);if (ret){--_n;ret->_state = DELETE;return true;}return false;}private:vector<HashData<K,V>> _tables; //直接用vector来作哈希表size_t _n; //表中存储数据个数
};

4.2 链地址法

开放定址法虽然解决了哈希冲突，但是都是通过占用其他数据的位置来存放数据的，弊大于利，且开放定址法的所有数据都存放在哈希表中，但链地址法不是，链地址法不直接将数据存放在哈希表中，而是在哈希表中存放一个指针，没有数据映射这个位置时，该指针指向空，当有多个数据映射同一个位置时，就把这些冲突的数据链接成一个链表，挂在哈希表中映射到的位置下面，链地址法也叫作哈希桶。

链地址法如下图例：

从上面的举例来看，这样既解决了哈希冲突的问题，也解决了占用其他数据位置的问题，相较于开放定址法，该方法较优

链地址法的扩容问题

开放定址法的负载因子须小于1，而链地址法的负载因子就没有限制了，可以大于1，但是负载因子越大，哈希冲突的概率就越大，空间利用率也越高，所以将负载因子基本控制在1就好。stl中的unordered_map和unordered_set的最大负载因子也为1

4.2.1 用除留余数法和链地址法模拟实现简单的哈希表

#pragma once
#include <iostream>
#include <vector>
namespace hash_bucket
{//将存储的数据定义成结点template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;//指向下一个结点的指针HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){ }};template<class K>class HashFunc{public:const size_t operator()(const K& key){return (size_t)key;}};//由于string作为关键字经常被用到，所以可以对string转整型的仿函数作特化template<>class HashFunc<string>{public:const size_t operator()(const string& key){size_t ret = 0;for (auto& s : key){//使string的每个ASCII码值都参与运算，得到不同的关键字ret += s;ret *= 131;}return ret;}};template<class K,class V,class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:inline unsigned long _stl_next_prime(unsigned long n){static const int _stl_num_primes = 28;static const unsigned long _stl_primes_list[_stl_num_primes] ={53,        97,        193,        389,        769,1543,      3079,      6151,       12289,      24593,49157,     98317,     196613,     393241,     786433,1572869,   3145739,   6291469,    12582917,   25165843,50331653,  100663319, 201326611,  402653189,  805306457,1610612741,           3221225473,             4294967291};const unsigned long* first = _stl_primes_list;const unsigned long* last = _stl_primes_list + _stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);//lower_bound()在迭代器的范围内取>=n的最小值return pos == last ? *(pos - 1) : *(pos);}HashTable(){//提前开好第一个质数大小的空间_tables.resize(_stl_next_prime(1),nullptr);}~HashTable(){//遍历哈希表，把每个桶都释放掉for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool insert(const pair<K, V>& kv){if (find(kv.first))return false;Hash hs;//到负载因子到1时就扩容if (_n == _tables.size()){size_t newsize = _stl_next_prime(_tables.size() + 1);//创建一个新的指针数组，将旧表中的结点直接移动到新的指针数组中//直接对结点进行二次利用，避免了多次拷贝的问题vector<Node*> newtables(newsize, nullptr);//遍历就表，将结点移到newtables中for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){//从头开始将结点移动过去，所以要记录好下一个结点Node* next = cur->_next;//计算当前结点在新表中映射的位置size_t hashi = hs(cur->_kv.first) % newtables.size();//一样头插到新表中cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}//旧表的数据都被移走了，须置空_tables[i] = nullptr;}//最后再进行交换_tables.swap(newtables);}size_t hashi = hs(kv.first) % _tables.size();Node* newnode = new Node(kv);//用头插的方式插到哈希桶里newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}Node* find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){//头删_tables[hashi] = cur->_next;}else{//先建立前后链接再删除prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; //指针数组size_t _n = 0;};
}