c++——哈希表的模拟实现

         哈希又叫做散列，是一种组织数据的方式。本质上来说就是通过哈希函数把关键字key与存储位置建立出一个映射关系，在查找时，我们通过这个哈希函数就能用O(1)的效率，快速得到查找结果。

一、哈希的实现方式

        1、直接定址法

        这种方法适用在关键字的范围比较密集的情况下，比如一组数据的在[0,10]之间，那么我就开一个大小为11的组数，那么每个关键字的值就可以是它存储位置对应的下标。

        1.1、哈希冲突

        第一种直接定址法的缺点非常明显，在关键字范围很分散的情况下，就会非常的浪费内容，甚至会出现内存不够用的情况。比如说假如我们有一组数据的范围是[0,99999]，那么我们就需要开一个大小为100000的数组，如果这个一组数据只有10个，那么剩下的空间全都被浪费了。

        同时如果这一组数据中，每个数据可能出现的次数不止一次，那么就会出现插入两个相同的数据时，直接定址法会定位到同一个位置的情况，这种问题我们叫做哈希冲突。用其他的哈希函数计算出key值再进行插入也无法完全避免哈希冲突。也就是说在实际应用的过程中，哈希冲突是无法避免的，我们只能通过一个好的哈希函数来减少哈希冲突出现的次数，进而提高我们的效率。、

        1.2、负载因子

        假设一个哈希表中已经映射存储了N个值，此时哈希表的大小为M，那么此时的负载因子就是，负载因子越大，发生哈希冲突的概率越高，空间的利用率也越高；反之负载因子越小，发生哈希冲突的概率越低，空间的利用率也越低。

        1.3、将关键字转化为整数

        我们一般都是把关键字映射到数组中的某个位置，也就是将关键字与数组的下标进行联系，当然并不是所有的关键字都能被转化成下标，我们也并不知道使用者使用的关键字是什么，所以我们在设计哈希表的时候，需要添加一个仿函数，如果是能够直接转化成整数的类型，那就让他自己进行转化即可，如果是不能自己进行转化的类型，那就需要用户自己编写这个仿函数，把关键字按照自己制定的规则转化为整数。

        2、除法散列法/除留余数法

        顾名思义，这种方法就是利用除法来确定key和数组下标的关系，假设哈希表的大小为M，那么通过key除以M的余数作为映射的下标位置，也就是哈希函数为：hs(key) = key % M。

        在使用除法散列法作为哈希函数时，M要尽量避免一些时，否则会增加哈希冲突出现的概率，比如说2的整数次幂，10的整数次幂。比如选择的作为M的值，那么在计算下标时就是用key % ，如果是这样操作的话，那就相当于取了这个数的后X为，比如说M是16的话，此时的X相当于是4，在计算映射关系时就相当于取key的后四位，此时如果两个key值是63和31，他们二进制的后4位全都是1，那么此时两个本来看着不相关的数据，在插入时却发生了哈希冲突。

        所以在使用除留余数法时，建议M取一个不太接近2的整数次幂的一个质数，这样能有效降低哈希冲突出现的概率。

        3、乘法散列法

        乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路第⼀步：⽤关键字 K 乘上常数 A(0<A<1)，并抽取出 k*A 的⼩数部分。第⼆步：后再⽤M乘以k*A 的⼩数部分，再向下取整。

        h(key) = floor(M × ((A × key)%1.0))，其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥ 最重要的是A的值应该如何设定，Knuth认为 (⻩⾦分割点])⽐较好。

        乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key = 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 = 669.6366651392，那么hs(1234) = 669。

        4、全域散列法

        上面的三种散列方式都是由固定的哈希函数计算出key映射的下标位置，虽然在外部很难能够知道我们哈希函数采用的计算方式时哪种，但是如果有大量的数据进行测试，那么还是有一定的概率将我们的哈希函数的计算方式给反向推导出来，如果这个时候有人再针对我们提供的哈希函数构造一个会发生严重冲突的数据集，比如说让所有的关键字都落入同一个位置，这样就会严重的破坏我们程序的效率。

        为了针对这种情况有人又发明出了全域散列的方式，hs (key) = ((a × key + b)%P )%M，P需要选取一个足够大的质数，a可以随机选取[1,P-1]之间的任意整数，b可以随机选取[0,P-1]之间的任意整数，这样这个函数就构成了一个P*（P-1）组的全域散列函数组。

        需要注意的是，在使用全域散列法时，每次初始化哈希表的时候就要从这个全域散列函数组中随机选取一个进行使用，后续的增删查改都要固定使用这个散列函数，如果每次操作都选取不同的散列函数的话，那插入数据是一个散列函数，查找数据是一个散列函数，就会导致插入的数据的映射关系发生改变。

二、处理哈希冲突

         前面介绍的都是哈希函数，都是用来减少出现哈希冲突概率的方法，也说过了，哈希冲突是一定会出现的，那么就肯定要有解决哈希冲突的办法，主要的方法有两种，开放定址法和链地址法。

        一、开放定址法

        在开放定址发中，所有的元素都放在哈希表里，当一个关键字的key用哈希函数计算出来的位置已经被别的数量占有了的时候，就按照一定的规则，找到另外一个没有存储数据的位置进行存储，开放定址法中的负载因子一定是小于1的。这里说的一定规则一般情况有三种：线性探测、二次探测、双重探测。

        1、线性探测

        在发生哈希冲突的位置开始依次线性的向后一个位置进行探测，直到找到下一个没有存储数据的位置，如果走到了哈希表的尾部，则会回绕到哈希表的头部继续探测 。假设这个哈希表的大小为M，因为负载因子是小于1的，所以最多探测M-1次就一定能找到一个能够存储key的位置。

        2、二次探测

        在发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置。

        hs(key) = hash0 = key % M，如果hash0的位置发生了冲突，那么二次探测公式为:

hs(key,i) = hashi = (hash0  )  % M，i = {1,2,3...,M/2}，当hashi < 0时，需要将hashi += M，因为负数取模的规则和正数不一样。

        3、双重探测

        第⼀个哈希函数计算出的值发⽣冲突，使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不断往后探测，直到寻找到下⼀个没有存储数据的位置为⽌。

        h1 (key) = hash0 = key % M , hash0位置冲突了，则双重探测公式为： hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M， i = {1, 2, 3, ..., M}。

开发地址法的代码实现

        首先我们要确定哈希表需要把关键字的key和存储位置的下标进行联系，所以我们哈希表的底层结构用的应该是一个vector结构，同时我们需要存储数据，我们还要给存储的数据类型添加上一个标识它的状态，因为在如果我们在删除一个数据的时候，我们不能直接把这个位置的数据删除掉，而是要把它表示成删除，因为如果把这个位置直接删除了，那么可能会影响其他其他数据的查找操作。我们在进行查找操作时，是从映射位置开始查找，如果查找到空位置都没有找到这个数据，才说明这个数据不存在在哈希表内，如果把中间部分的数据删除了，那么后面的数据都有可能不会被找到。所以我们给数据添加一个标识位，表示这个存储位置的状态。

        这样还有一个需要讨论的问题，之前提到的哈希表里的M是用vector的size还是capacity。

        很显然是不能用size的，因为如果使用size的话，每次插入数据以后vector的size都在变化，那么哈希表的M也在变化，这样哈希表的映射关系就发生了改变，也就意味着如果用vector的size作为M每次插入数据，都要把前面的数据重新放入哈希表一遍。所以我们用的M是vector的capacity

enum State
{EXIST,EMPTY,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable(){_tables.resize(10);}private:vector<HashData<K, V>> _tables;size_t _n = 0;  // 表中存储数据个数};
}

扩容

        这里我们把哈希表的负载因子控制在0.7，当负载因为到达0.7以后我们就要进行扩容，如果按照正常的二倍扩容来进行的话，前一个数是质数，那它的二倍就一定不是质数了。这里介绍一下sig的质数表的解决方案。给定一个近似2倍的质数表，每次需要扩容的时候就去取下一个质数，取到的质数就是扩容后的大小。这里只需要给这个函数传一个当前大小 + 1作为参数就能取得下一个质数。

        但是这里为了方便操作，在后续的代码实现里我还是采取二倍扩容的方式进行。

inline unsigned long __stl_next_prime(unsigned long n)
{static const int __stl_num_primes = 28;static const unsigned long __stl_prime_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_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}

key不能取模的问题

        看到上面的结构可能会有人疑问，为什么哈希表的模板里还有一个class Hash = HashFunc<K> 这样的东西，因为并不是所有的关键字都是整型，当key是string或者是一些自定义类型时，它并不能直接转化为整型，而我们的哈希表内部一定是用关键字转化为整型，然后和数组的下标产生映射关系实现的，所以如果这个关键字的类型不支持自动转化为整型，那么就需要用户在传参的时候自己写一个仿函数来支持把关键字转化成整型。同时string作为关键字是很常见的，所以我们在写默认的仿函数的时候，可以写一个string的特化版本。

	// 哈希函数采用除留余数法template<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};// 哈希表中支持字符串的操作//这里用的是BKDR哈希的思路 这样处理以后"abcd" 和 "dcba"映射的位置是不一样的template<>struct HashFunc<string>{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 131;hash += e;}return hash;}};

查找、插入、删除

         这里的查找操作其实很简单，就是利用Hash把key先转化成整型，找到key映射的位置，如果找到位置不空且不是我们要找的key那么就按照我们的规则继续寻找下一个位置，直到找到这个key或者找到表示为空的位置，找到表示为空的位置表示这个key不存在在这个哈希表内。

        插入操作的技巧其实就在于扩容，当负载因子大于等于0.7时我们就要进行扩容，此时就需要一个更大的哈希表来存储这些数据，我们就可以复用这个插入的操作，遍历一遍原本的哈希表，把里面存储的数据重新插入到新的哈希表内，再把指向数组的指针一交换，这样哈希表不仅完成了扩容，还把原本的数据迁移到了这个表里，同时在这次插入结束后，我们定义出来用来扩容的新表也会随着这次的插入操作的结束而销毁，同时把我们旧表的数据也一并销毁了。

        删除操作和之前分析过的一样，我们增加这个标识位就是为了方便删除操作，找到要删除的数据把它的表示位改成DELETE即可。

	HashData<K, V>* Find(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key)return &_tables[hashi];++hashi;hashi %= _tables.size();}return nullptr;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//扩容if (_n * 10 / _tables.size() >= 7){HashTable newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST)newHT.Insert(_tables[i]._kv);}_tables.swap(newHT._tables);}Hash hash;size_t hashi = hash(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr)return false;else{ret->_state = DELETE;return true;}}

        二、链地址法

        开放地址法的思路是把所有的元素都存放到哈希表里，链地址法中的数据就不存放直接存储在哈希表中了，哈希表中存储的是一个一个的指针，当没有数据映射到这个位置的时候，这个指针为空，当有多个数据映射到这这个位置的时候，我们就把所有冲突的数据拼接成一个链表，挂在哈希表的下面。

链地址法代码实现

        这里我实现的代码是考虑到后续用链地址法来封装unordered_set和unordered_map的方式，如果只是想单纯的实现链地址法就不用考虑KeyOfT这个仿函数，以及这个代码里的T并不是我们V，在unordered_set里它就是一个Key，在unordered_map它就是一个pair<K,V>，所以我们才需要KeyOfT这个仿函数去取到T类型数据里面的Key。

        这里的基本结构和上面的实现方式是类似的，只不过把存储的数据从数据本身改成了结点的指针而已。

	namespace hash_bucket{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// K 为 T 中key的类型// T 可能是键值对，也可能是K// KeyOfT: 从T中提取key// Hash将key转化为整形，因为哈希函数使用除留余数法template<class K, class T, class KeyOfT, class Hash>class HashTable{typedef HashNode<T> Node;public:HashTable(){_tables.resize(10, nullptr);}// 哈希桶的销毁~HashTable(){//每个位置下面可能都挂着一个链表，所以要按照顺序挨个进行销毁for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}private:vector<Node*> _tables;  // 指针数组size_t _n = 0;			// 表中存储数据个数};}

扩容

        开放地址法里的负载因子是必须小于1的，链地址法中就没有限制了，但是如果同一个位置的冲突数据过多的话，会导致某哈希表里的某一条链特别长，所以我们可以把负载因子基本控制在1，负载因子大于1了，我们就进行扩容。

查找、插入、删除

        这里的查找操作比开放地址法的还要简单，只要到对应的桶里去找有没有想要的数据即可，如果走到空了都还没有找到，那就说明这这个数据不在哈希表里面了。

        插入操作用头插就很方便，这里的不同是扩容，这里我们用复用这个Insert操作同样可以实现，但是这样操作的代价会比较大，因为新表的结点需要一个一个重新去申请空间再插入到新表中，在完成操作以后，原本的结点数据又需要一个一个的去释放空间，所以这里的效率就会变的很低。这里我们只需要申请一个新的数组来存储指针，不需要一个新的哈希表。同时，我们还有可以把这些原本就有的结点重复使用，这样开新结点的时间消耗就剩下来了，但在重复使用的时候我们需要先记录当前链下的下一个结点的信息，不然在把这个结点插入到新数组以后，就会找不到旧表中的小一个元素了。

        删除操作也没有什么可说的，因为是一个单向的链表，所以需要记录当前位置的前一个结点，对当前位置进行删除以后，把链表重新接上即可；需要注意的就是前一个结点为空的情况就是待删除结点是头结点的情况，这种情况需要特殊处理一下。

	// 在哈希桶中查找值为key的元素，存在返回true否则返回falsebool Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();//在对应的桶里查找数据Node* cur = _tables[hashi];KeyOfT kot;while (cur){if (kot(cur->_data) == key)return true;cur = cur->_next;}return false;}// 插入值为data的元素，如果data存在则不插入bool Insert(const T& data){KeyOfT kot;Hash hs;//插入的数据已经存在if(Find(kot(data)))return false;//负载因子为1时扩容if (_n == _tables.size()){vector<Node*> newHT(_tables.size()*2,nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//头插到新表里size_t hashi = hs(kot(cur->_data)) % newHT.size();cur->_next = newHT[hashi];newHT[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newHT);}size_t hashi = hs(kot(data)) % _tables.size();//头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}// 哈希桶中删除key的元素，删除成功返回true，否则返回falsebool Erase(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){//删除结点为头结点if (prev == nullptr){_tables[hashi] = cur->_next;}//删除结点为中间结点else{prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}