【C++、数据结构】哈希 — 闭散列与哈希桶的模拟实现

📖 前言

哈希表在日常生活中我们一定略有耳闻，作为STL中我们所必须学习和了解的容器，首先哈希查找的时间复杂度为〇（1），是一种一一映射的存储方式，其次它在日常生活中的应用范围也是很广的，例如位图，海量数据筛选中用到的布隆过滤器等等……

下面我们就来先学习一下STL中的应用哈希表的两个容器，再了解一下底层结构 （两个关联式容器unordered_map和unordered_set，unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构），最后再来模拟实现一下……
🙋 🙋 🙋 🙋 🙋

---

1. STL中哈希表的两个应用⚡

在STL中对应的容器分别是unordered_map和unordered_set这两个关联式容器。

只要我们会用set那么我们就会用unordered_set，但不是任何场景下，unordered_map/set都能将map/set替换掉。

哈希是一种映射，有的地方也叫散列：存储关键字跟存储位置建立关联关系

1.1 🌟unordered_set

unordered_set 文档介绍

我们简单的试用一下unordered_set，如下代码：

void test_set()
{unordered_set<int> s;//set<int> s;s.insert(1);s.insert(3);s.insert(4);s.insert(2);s.insert(10);//unordered_set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;
}

结果是无序的

由上图和查阅资料得知：

• map和set： 去重 + 排序
• unordered_map和unordered_set： 只有去重

其余函数接口和之前所学的容器使用起来大致相同，不再一一赘述。

unordered_map和unordered_set都是单向迭代器：

值得注意的是unordered_map和unordered_set的迭代器都是单项迭代器，而我们之前学的map和set则是单项迭代器。

unordered_set和set的性能对比：

void test_op()
{
//对比插入的效率：int n = 1000000;vector<int> v;v.reserve(n);srand(time(0));for (int i = 0; i < n; i++){//v.push_back(i);//v.push_back(rand()+i);  //重复少v.push_back(rand());	  //重复多}size_t begin1 = clock();set<int> s;for (auto e : v){s.insert(e);}size_t end1 = clock();size_t begin2 = clock();unordered_set<int> us;for (auto e : v){us.insert(e);}size_t end2 = clock();cout << s.size() << endl;cout << "set insert:" << end1 - begin1 << endl;cout << "unordered_set insert:" << end2 - begin2 << endl;//扩容重新哈希是有消耗的 -- 数据量多的时候，没有那么多重复的数据的时候也不一定//对比查找的效率size_t begin3 = clock();for (auto e : v){s.find(e);}size_t end3 = clock();size_t begin4 = clock();for (auto e : v){us.find(e);}size_t end4 = clock();cout << "set find:" << end3 - begin3 << endl;cout << "unordered_set find:" << end4 - begin4 << endl;//对比删除的效率size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "set erase:" << end5 - begin5 << endl;cout << "unordered_set erase:" << end6 - begin6 << endl;
}

因为生成随机数的个数有个最大值，不能生成无限多个随机数，这就导致了有很多数字的重复。

当重复的数字很多时：

当没有重复的数字时：

总结：

总的来说unordered_map和unordered_set要比map和set的性能要好的，但是也并不是一定的，当数据量很大的时候，扩容重新哈希是有消耗的。

1.2 🌟unordered_map

unordered_map文档介绍

void test_map()
{unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("left", "剩余"));dict["string"];dict["left"] = "剩余";dict["string"] = "字符串";unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << (*it).first << " " << (*it).second << endl;it++;}
}

---

2. 常见查找的性能对比💥

• 暴力查找： 时间复杂度〇(N)

• 二分查找： 时间复杂度〇(logN) ，缺点 — 有序、数组结构

• 搜索二叉树： 时间复杂度〇(N)，缺点 — 极端场景退化成单支

• 平衡二叉搜索树： 时间复杂度〇(logN)

• • AVLTree: 左右子树高度差不超过1
• • 红黑树：最长路径不超过最短路径的2倍

• 哈希

• B树系列： 多叉平衡搜索树 — 数据库原理

• 跳表

备注：

红黑树高度略高一些，但是跟AVL树是同一数量级，对于现代计算机没有差别但是红黑树相对而言近似平衡，旋转少。

---

3. 哈希表模拟实现🏁

3.1 哈希的概念：

普通查找：

• 我们之前查找一个数据时，一般都是通过比较，查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为〇(N)，平衡树中为树的高度，即〇(logN)。

理想的搜索方法：

• 可以不经过任何比较，一次直接从表中得到要搜索的元素。
• 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
• 该中存储结构可以实现：
• • 插入元素时：
    根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
• • 查找元素时：
    对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
    取元素比较，若关键码相等，则搜索成功。

哈希表就由此而来…

---

3.2 哈希函数：

我们如何一一将键值转换为对应的关键码值，并映射到对应序号的存储位置呢？

直接映射法：

直接建立映射关系问题:
1、数据范围分布很广、不集中（可能存在空间浪费严重的问题）
2、key的数据不是整数，是字符串怎么办？是自定义类型对象怎么办？

此时我们就需要一个函数对特殊非整数类型的数据进行处理，使其返回一个特定的整数，这个函数我们叫做 —— 哈希函数。

常见的哈希函数：

• 直接定址法：（常用）
• • 取关键字的某个线性函数为散列地址
• • 使用场景：适合查找比较小且连续的情况
• 除留余数法：（常用）
• • 直接用该值除以表的大小然后取余数
• 字符串哈希算法：（常用）
• • 参考文献
    

---

3.3 哈希冲突：

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

按照上述哈希函数计算出键值对应的关键码值，但是算出来的这些码值当中，有很大的可能会出现关键码值相同的情况，这种情况就叫作：哈希冲突。

• 哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
• 解决哈希冲突两种常见的方法是：闭散列和开散列

---

3.4 闭散列 — 开放地址法：

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

线性探测：（依次去找空位置）

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

插入：

• 通过哈希函数获取待插入元素在哈希表中的位置
• 线性探测找到空位置将值插入

查找

• 挨个遍历哈希表，直到找到空为止

删除：

• 通过关键码值再用线性探测找到该值直接删除
• 注意：
• • 删除要是直接删除的话有可能会影响查找的准确性
• • 如图删除了10，要去找60就会找不到
• • 所以我们给每个键值提供一个状态，采取伪删除的方法

线性探测的缺点：

• 一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

二次探测：（跳跃着找空位置）

对上面方法的优化：

• 不那么拥堵

闭散列哈希表并不能太满：

• 太满就会导致线性探测时，找不到位置
• 更不能放满，那样探测就会陷入死循环
• 所以要控制一下存储的数据
• 我们引入了一个变量n来记录存储数据的个数

散列表的载荷因子定义为: a = 填入表中的元素个数 / 散列表的长度

所以我们要控制一下负载因子：

代码如下：

template<class K>
struct DefaultHash
{size_t operator()(const K& key){return (size_t)key;}
};//字符串哈希算法
template<>
struct DefaultHash<string>
{size_t operator()(const string& key){//BKDRsize_t hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}
};//闭散列（开放地址法）
namespace CloseHash
{enum State{EMPTY,EXITS,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class HashFunc = DefaultHash<K>>class HashTable{typedef HashData<K, V> Data;public:bool Insert(const pair<K, V>& kv){//去重if (Find(kv.first)){return false;}//负载因子到0.7及以上，就扩容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;//扩容以后，需要重新映射HashTable<K, V, HashFunc> newHT;newHT._tables.resize(newSize);//遍历旧表，插入newHTfor (auto& e : _tables){if (e._state == EXITS){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);}HashFunc hf;size_t starti = hf(kv.first);//调用仿函数，获取整数starti %= _tables.size();//求模取余 -- 但是不能除0size_t hashi = starti;size_t i = 1;//线性探测/二次探测while (_tables[hashi]._state == EXITS){hashi = starti + i;++i;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXITS;_n++;//有效数据个数++return true;}Data* Find(const K& key){//空表直接返回空指针if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t starti = hf(key);starti %= _tables.size();size_t hashi = starti;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = starti + i;i++;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){Data* ret = Find(key);if (ret){ret->_state = DELETE;_n--;return true;}else{return false;}}private:vector<Data> _tables;size_t _n = 0; //存储关键字个数};
}

扩容时我们不能直接将原来的数据拷贝过去：

• 因为哈希是映射的关系，关键码值是通过数据和表的大小计算出来的
• 如果直接拷贝的话全都乱套了
• 这时我们需要重新映射
  
• 如图所示，也不是特别麻烦
• 直接建立一个新表，然后遍历旧表一次映射到新表中
• 不过扩容时会有不少的消耗

补充：

• 映射的时候取模
• 应该是对表的size()取模，而不是capacity()
• 因为对capacity取模的话，可能取到超出size的位置
• operator[]会对超出size的检查（不过有的也不检查，根据不同版本的库里定）

---

3.5 开散列 — 哈希桶、拉链法，开链法：

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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

很显然，哈希桶中每个元素是个地址，所以哈希桶的底层原理就是一个指针数组，每个结点再挂着一个单链表，这样冲突就很容易解决了。

namespace 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 V, class HashFunc = DefaultHash<K>>class HashTable{typedef HashNode<K, V> Node;public:~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;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//新方法：（转移结点）//*原来单链表中的结点得到了利用，就不用去开新的结点了//负载因子 == 1 扩容HashFunc hf;if (_tables.size() == _n){size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newTable;newTable.resize(newSize, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newSize;cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}newTable.swap(_tables);}size_t hashi = hf(kv.first);hashi %= _tables.size();//头插到对应的桶即可（单链表的尾插效率不高，但是头插效率高）Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}//定位到桶，然后在同中挨个找一遍Node* Find(const K& key){if (_tables.size() == 0){return nullptr;}HashFunc hf;size_t hashi = hf(key);//size_t hashi = HashFunc()(key);hashi %= _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){if (_tables.size() == 0){return false;}HashFunc hf;size_t hashi = hf(key);hashi %= _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;}prev = cur;cur = cur->_next;}return false;}private://指针数组vector<Node*> _tables;size_t _n = 0;};
}

扩容我们有两种方案：

方案一：

方案二：

很显然我们更倾向于方案二：

• 以为方案二中是将原来单链表中的结点得到了利用，就不用去开新的结点了
• 而方案一则是又开了一遍新的结点，效率不高
• 方案一是拷贝创建新的结点，方案二是转移结点

哈希表的析构：

虽然vector自己的析构函数可以释放哈希表，但是哈希桶中挂着的每个结点是不能释放的，需要我们手动释放掉。