C++——深部解析哈希

好久不见给大家分享一张图片吧

前言

在我们前面的学习中，我们知道了set和map相关的多个库文件和数据结构，今天我们我们将学习基础的哈希表和哈希桶。

学习set和map时，我们非常清楚它们都是树状结构，set为key类型，而map的为key、value类型，而哈希是一种顺序结构，那么就让我们来感受一下哈希表和哈希桶吧！！

一、哈希是什么？

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

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

 搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功 该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)

二、库文件

在学习哈希底层之前我们先了解一下大佬是怎么实现的哈希；

unordered_set

unordered_map

在这里我们理解几个和哈希相关的概念

1、哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突 或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢？

2 哈希函数

引起哈希冲突的一个原因可能是：

哈希函数设计不够合理。

哈希函数设计原则： 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值 域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数

1. 直接定址法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

2. 除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

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

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

6. 数学分析法--(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散 列地址。

哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

3、闭散列

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

1. 线性探测

比如现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4， 因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

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

插入

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

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影 响。因此线性探测采用标记的伪删除法来删除一个元素。

三 、闭散列的实现和底层逻辑

我们在学习二叉树和set和map时，我们存储数据有一个规律，那就是如果插入一个树，当这个数据比根大，那么我们就往右走，比根小我们就往左走，通过这个规律，我们就可以把一个节点放到正确的位置上去；

在闭散列的概念中我们略有了解，那就是我们的哈希存储是在一个顺序表里面的，当让这个数据和顺序表建立某种映射关系，这样我们就可以轻松找到了。

这里可能有人会问了，我们既然借助了顺序表为什么不直接用顺序表呢，这里可以参考上面的哈希的优点；再说说个人看法，当我们在顺序表里面去找一个数据的时候我们需要将整个顺序表给遍历一遍，而哈希找一个数据只需要在一个小的范围里去查找；

1、哈希表（闭散列）的定义

我们这里存储的算法为除留余数法；

enum Status//将状态进行枚举
{EMPTY,//空EXIST,//存在DELETE//删除
};template<class K,class V>
struct HashData
{pair<K, V> _kv;//存储数据Status _state= EMPTY;//状态
};
template<class K,class V>
struct HashData
{
public:bool Insert(const pair<K, V>& kv)//插入函数{}HashData<K, V>* Find(const K& key)//查找函数{}bool Erase(const K& key)//删除函数{}
private:vector<HashData<K, V>> _tables;//这里我们用的是顺序表size_t _n = 0; // 存储的数据个数
};

 现在我们知道了哈希表的基本结构；

现在然我们用图片理解哈希表吧

我们以前在顺序表里面存储数据的时候都是一个数据一个数据挨着存储，而现在我们在存储时，我们直接对要存储的数据进行取余，余数就是我们要存储的位置了，以后要是向对某个数据进行操作，我们只需要在这个数据的余数处去找这个数据

现在有一个问题那就是当我们的一个表里面要存储5、15，而表的长度为10，我们对5、15取余都是5，那怎么办呢？

这就是我们前面概念所提到过的哈希碰撞。这个时候我们只需要进行偏移一下就可以，也就是将hashi++（hashi=key%_tables.size())；

2、哈希表（闭散列）的插入

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;// 负载因子超过0.7就扩容//if ((double)_n / (double)_tables.size() >= 0.7)if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);// 遍历旧表，重新映射到新表for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hashi = kv.first % _tables.size();// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST){index = hashi + i;index %= _tables.size();++i;}_tables[index]._kv = kv;_tables[index]._state = EXIST;_n++;return true;
}

 我们在插入的时候，是通过映射关系进入插入的，这个关系就是key对空间进行取余数，然后在对应的位置放元素，当某个位置有数据时，我们就进行偏移，将hashi++，就是向后移动一位；

思考，如果余数相同的数据太多了，我们++一圈，也就是一轮回来还是没有位置存放数据时因该怎么办？这种情况的时间复杂度是不是还不如vector呢？

解决方法那就是就行扩容，将我们的_table.size()的大小变大，那也就是进行扩容；我们解决方案是定义一个负载因子，当负载因子大于0.7时，我们就就行扩容，我们重新开辟一个顺序表，将原来的哈希表进行遍历一遍，重新进行映射一次，否则就有取余过后那个位置上找不到某一个数据；

例如：15% 10=5和15%20=15这样，我们扩容完我们15应给放在15的位置，然而我们不遍历重新映射就会导致查找时在15位置找不到15；

思考：哈希表什么情况下进行扩容？如何扩容？

3、哈希表（闭散列）的查找

HashData<K, V>* Find(const K& key)
{if (_tables.size() == 0){return false;}size_t hashi = key % _tables.size();// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._state == EXIST&& _tables[index]._kv.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();++i;// 如果已经查找一圈，那么说明全是存在+删除if (index == hashi){break;}}return nullptr;
}

 我们查找这里也是非常简单的，就是在取余过后到hashi的位置上去找，如果这个位置上的数据不是我们想要的数据，那么我们就往它的后面去找，直到什么时候结束呢？

当我们在hashi过面一直找到数据状态为空的时候停止，因为我们插入的时候为空的位置放上了偏移或没偏移的数据，若这段空间不连续有空的的时候，那么就说明没有找到；

4.哈希表（闭散列）的删除

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}
}

这个函数就更简单了，我们只需要将这个位置的状态改为删除就可以了，然后让_n--，就可以了；

四、哈希桶

1、开散列

开散列概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中。

大家看这幅图好看嘛，我们的哈希桶（开散列）也就是长这个样子的，屋檐呢就相当于顺序表，然后呢每个挂件呢也就相当于hashi相同的数据串在一起的样子。

2、哈希桶（开散列）的定义

template<class K, class V>
struct HashNode
{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}
};template<class K, class V>
class HashTable
{typedef HashNode<K, V> Node;
public:~HashTable(){}Node* Find(const K& key){}bool Erase(const K& key){}bool Insert(const pair<K, V>& kv){}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数
};

 我们之前的哈希表呢是直接将数据放在顺序表上的，而现在呢，我们是在顺序表上放hashi相同节点的一个节点的地址，然后将剩下相同节点一个一个的串联在下面，也就是链表一样；

相当于在顺序表里面放每个链表的头节点；

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可 能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希 表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点， 再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可 以给哈希表增容。

3、哈希桶（开散列）的析构

这里的析构就不只是将顺序表给销毁了，我们要将链表的每一个节点进行delete

~HashTable()
{for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}
}

4、哈希桶（开散列）的插入

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first)){return false;}// 负载因因子==1时扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = kv.first % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

我们在每个hashi相同位置进行链表的链接，为了节省效率呢，我们就在链表的头部进行头插，然后顺序表里面就存放这个新进来元素的地址；

当我们的hashi不够用的时候呢，我们就将它进行扩容。扩容完以后呢，我们不能再像哈希表一样遍历原来表进行开空间释放空间了，这样非常麻烦。

我们通常是将他们的指针指向位置改变，定义一个next进行记录工作节点下一个节点的位置，以便于后续的更新，然后在新的顺序表里重新进行头插cur。

 5、哈希桶（开散列）的删除

bool Erase(const K& key)
{size_t hashi = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;
}

删除呢也就是我们链表的删除一样，我们找到hashi=key%size（）的位置，然后在这个串上找key的位置，但是要定义一个prev来记录key的上一个节点的位置，便于链接；

 6、哈希桶（开散列）的查找

查找呢也就像链表一样，到key取完余数以后相同的链表上去找key即可；

非常简单，上菜

Node* Find(const K& key)
{if (_tables.size() == 0)return nullptr;size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

下期进行unordered的封装

总结

哈希表是在一个顺序表里面去找hashi（key%size（））的位置，存在向后偏移，空就存储。

和哈希桶在顺序表里面存放单链表，把hashi相同的数据串联在一起；