【C++学习】哈希表的底层实现及其在unordered_set与unordered

文章目录

1. unordered系列关联式容器
- - 1.1 unordered_map
  - 1.2 unordered_set
  - 1.3.底层结构
2.哈希
- - 2.1哈希概念
  - 2.2哈希冲突
  - 2.3 哈希函数
  - 2.4 哈希冲突解决
  - - 2.4.1闭散列
    - 2.4.1开散列
    - 2.5开散列与闭散列比较
3.哈希的模拟实现
- - 1. 模板参数列表
  - 2. 迭代器的实现
  - 3. 增加通过key获取value操作
  - 4. 哈希实现总代码：
4.用实现的哈希封装unordered_map与unordered_set前的模板参数的梳理及相关联系的梳理
5.unordered_map的封装实现
6.unordered_set的封装实现

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

文章简介：

本篇博文主要会涉及到STL关联式容器，unordered系列关联式容器，unordered_set和unordered_map的底层数据结构，哈希表的底层及迭代器实现，以及在其上对unordered_set****和unordered_map的封装。

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 $log_2 N$ ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，分别为：unordered_map与unordered_set和unordered_multimap与unordered_multiset 这四个容器，他们与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

unordered_map和unordered_set与map与set类似，map与set是有序的，但是unordered系列都不是有序的，但是也不允许出现重复值。
unordered_multimap和unordered_multiset与unordered_map和unordered_set类似，unordered_map和unordered_set不允许重复值出现，但是multi系列是允许重复值出现的。
只要是前缀带了unordered的就是无序，后缀带了multi的就是允许键值重复。
他们在使用方面上与set与map非常类似，这里不作详解。

1.1 unordered_map

unordered_map的文档介绍链接: link

文档说明：

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps实现了直接访问操作符(operator[ ])，它允许使用key作为参数直接访问value。
它的迭代器至少是前向迭代器。

1.2 unordered_set

unordered_mset的文档介绍链接: link

1.3.底层结构

STL关联式容器中：
set和map的底层数据结构为红黑树，因为map和set要求是自动排序的，红黑树能够实现这一功能，并且各个操作的时间复杂度都较低，而unordered_set和unordered_map的底层数据结构为哈希表，查找时间复杂度为常数级。

2.哈希

2.1哈希概念

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

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的 存储位置 与它的 关键码 之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为：hash(key) = key % capacity（ capacity为存储元素底层空间总的大小）。
在这里插入图片描述
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，
但是如果我们再插入一个数7，就会和存放17的位置冲突，这个就引发了哈希冲突；

2.2哈希冲突

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

2.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

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

常见哈希函数
这里只讲解常用的几种方法

直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
面试题：字符串中第一个只出现一次字符

例如：数组arr[ ]={ 1 , 4 , 6 , 2 , 8 }; 假设线性函数我们取：Hash(key) = 2*key+1。
那么：Hash(6)=2 *1+1=13; 就把 6 存放到哈希表中对应映射位置为 13 的位置中，这样如果我们想要快速找元素6时，就可以直接利用该函数找到地址。

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

例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

在这里插入图片描述

2.4 哈希冲突解决

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

2.4.1闭散列

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

线性探测
现在需要插入元素44（如下图），先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
在这里插入图片描述
删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影
响。因此线性探测采用标记的伪删除法来删除一个元素。（例如使用枚举，列出三种状态（存在，不存在，已删除））

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

线性探测优点：实现非常简单（就不实现了，重点实现后面的开散列）
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。
如何缓解呢？

二次探测
二次探测就是与线性探测寻找下一个位置的方法不同而已。
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题
*找下一个空位置的方法为: $H_i$ = ( $H_0$ + $i^2$ )% m, 或者： $H_i$ = ( $H_0$ - $i^2$ )% m。其中：i = 1,2,3…， $H_0$ 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a（存放的数据个数/最多能存放的数据个数）不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列 最大的缺陷就是 空间利用率比较低，这也是哈希的缺陷。

2.4.1开散列

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

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

开散列实现

template<class K>
struct Hashfunc       //整型数据不用转换
{ size_t operator()(const K& key){return (size_t)key;    //直接返回}
};
template<>                     //特化
struct Hashfunc<string>         //如果为字符串类型，需要将其转化为整形
{size_t operator()(const string& s){size_t hashi = 0;for (auto e : s){hashi += e;hashi *= 131;       //这里13 131 1313.....都可以}return hashi;          //转换为整型返回}
};
template<class K, class V>     //储存数据的节点
struct HashNode
{HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}HashNode<K, V>* _next;    //指向写一个节点的指针pair<K, V> _kv;           //数据
};template<class K,class V,class HFunc = Hashfunc<K>>
class HashTable
{typedef HashNode<K, V> Node;
public:HashTable(size_t size = 10){_table.resize(size, nullptr);_n = 0;}插入函数的实现(这里只有插入函数，扩容与检查函数文章后面会有)bool insert(const pair<K,V>& kv){//1.查重，如果已经存在，不用插入了//2.检查是否需要扩容//3.插入代码Hashfunc<K> HFunc;         //转换能取模的整型size_t hashi = HFunc(kv.first) % _table.size();if (_table[hashi])   //如果不为bullptr，则说明改位置已经有数据了，直接头插{                            //因为单链表的头插效率高//头插Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;}else       //如果为nullptr，则说明该位置还没有数据，直接插入{Node* newnode = new Node(kv);_table[hashi] = newnode;++_n;return true;}}删除函数的实现bool Erase(const K& key){Hashfunc<K> HFunc;          //转换能取模的整型size_t hashi = HFunc(key) % _table.size();   //找到该元素对应到哈希表中的位置if (_table[hashi])            //如果不为空，则说明有元素{Node* cur = _table[hashi];Node* parent = nullptr;     //保存上一个节点，因为如果不是第一个节点需要链接while (cur)                 //寻找要删除的元素的节点{if (cur->_kv.first == key)      //找到了{if (cur == _table[hashi]){   //如果是第一个节点，特殊处理delete cur;_table[hashi] = nullptr;_n--;return true;}else{                       //不是第一个节点if(parent)parent->_next = cur->_next;   //链接delete cur;_n--;return true;}}parent = cur;cur = cur->_next;}return false;}else{return false;}}
private:vector<Node*> _table;      ///表size_t _n;         //记录储存的有效数据个数
};

开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。
数据类型为非整型时的定址方法
因为%取模的操作数只能是整型，那么当我们存储的数据类型为string或则Date(日期类)时，应该怎样去计算位置呢？
这时，如果存储的数据不是整型的时候，就需要先转换为整型再定址；

2.5开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：
由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

3.哈希的模拟实现

1. 模板参数列表

// K:关键码类型
// T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是unordered_set,T为 K
// KeyOfValue: 因为T的类型不同，通过value取key的方式就不同，详见见unordered_map/set的实现
// HFunc : 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
template<class K, class T, class KeyofT, class HFunc = Hashfunc<K> >
class HashTable;

2. 迭代器的实现

解析：

因为我们实现的hashTable是开散列的，底层是一个数组，数组里面存储的一个一个的节点，节点下面有可能挂着一个哈希桶；迭代器的实现必须要实现 ++，*，!= 操作，++ 指向下一个节点的，这里如果迭代器里面我们只选择封装一个节点的指针的话，那么如果当这个节点是一个哈希桶里面的最后一个节点时，则没有办法找到下一个节点，所以需要加一个哈希表的地址，当然也可以是哈希表中存放节点指针的vector；
其中下一个节点的寻找方法：
1. 判断当前节点的下一个节点是否为空，如果不为空，则让其指向下一个节点即可，如果当前节点的下一个节点为空，则需要步骤二。
2. 计算出当前节点所在哈希表中的下标（哈希地址），向后寻找数组中不为空的位置，让其指向该位置。
因为我们需要访问HashTable里面的私有成员（vector<Node*> ），所以需要将迭代器设置成HashTable的友元类。

代码实现：

template<class K, class T, class KeyofT, class HFunc>        //前置声明，因为迭代器需要一HashTable的一个指针，需要使用到HashTable，编译器默认向上找，如果不加前置声明，则会找不到报错                            
class HashTable;                                                    template<class K, class T, class KeyofT,class HFunc = Hashfunc<K>>
struct Iterator
{typedef HashTable<K, T, KeyofT, HFunc> HashTable;typedef Iterator<K, T, KeyofT,HFunc> Self;typedef HashNode<T> Node;       //存放数据的节点Node* _node;          //节点指针HashTable* _ht;        //哈希表Iterator(Node* node, HashTable* ht):_node(node),_ht(ht){}T& operator*(){return _node->_date;}T* operator->(){return &_node->_date;}Self& operator++(){KeyofT kot;if (_node->_next)   //如果该节点的下一个节点存在{_node = _node->_next;}//找下一个桶else{Hashfunc<K> Hfunc;size_t hashi = Hfunc(kot(_node->_date)) % _ht->_table.size();hashi++;while (hashi < _ht->_table.size()){if (_ht->_table[hashi]){_node = _ht->_table[hashi];break;}hashi++;}if (hashi == _ht->_table.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}	bool operator==(const Self& s){return _node == s._node;}
};

3. 增加通过key获取value操作

//map
struct mapKeyofT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};

///set
struct setKeyofT
{const K& operator()(const K& key){return key;}
};

4. 哈希实现总代码：

#pragma once
#include<iostream>
#include<string>
#include<vector>using namespace std;template<class T>
struct HashNode
{HashNode(const T& date):_next(nullptr), _date(date){}HashNode<T>* _next;T _date;
};template<class K>
struct Hashfunc       //整型数据不用转换
{ size_t operator()(const K& key){return (size_t)key;    //直接返回}
};
template<>                     //特化
struct Hashfunc<string>         //如果为字符串类型，需要将其转化为整形
{size_t operator()(const string& s){size_t hashi = 0;for (auto e : s){hashi += e;hashi *= 131;       //这里13 131 1313.....都可以}return hashi;          //转换为整型返回}
};
///迭代器的实现
template<class K, class T, class KeyofT, class HFunc>        //前置声明
class HashTable;                                                    template<class K, class T, class KeyofT,class HFunc = Hashfunc<K>>
struct Iterator
{typedef HashTable<K, T, KeyofT, HFunc> HashTable;typedef Iterator<K, T, KeyofT,HFunc> Self;typedef HashNode<T> Node;Node* _node;HashTable* _ht;Iterator(Node* node, HashTable* ht):_node(node),_ht(ht){}T& operator*(){return _node->_date;}T* operator->(){return &_node->_date;}Self& operator++(){KeyofT kot;if (_node->_next){_node = _node->_next;}//找下一个桶else{Hashfunc<K> Hfunc;size_t hashi = Hfunc(kot(_node->_date)) % _ht->_table.size();hashi++;while (hashi < _ht->_table.size()){if (_ht->_table[hashi]){_node = _ht->_table[hashi];break;}hashi++;}if (hashi == _ht->_table.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}	bool operator==(const Self& s){return _node == s._node;}
};template<class K, class T, class KeyofT, class HFunc = Hashfunc<K>>
class HashTable
{typedef HashNode<T> Node;
public:template<class K, class T, class KeyofT, class HFunc>friend struct Iterator;typedef Iterator<K, T, KeyofT, HFunc> iterator;iterator begin(){for (int i = 0; i <_table.size(); i++){if (_table[i]){return iterator(_table[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}HashTable(size_t size = 10){_table.resize(size, nullptr);_n = 0;}~HashTable(){for (size_t i = 0; i < _table.size(); i++){if (_table[i]){Node* cur = _table[i];Node* next = nullptr;while (cur){next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}}pair<iterator,bool> insert(const T& date){KeyofT kot;//查重，如果已经存在，不用插入了Node* ret = find(kot(date));if (ret){return make_pair(iterator(ret,this), false);}//扩容   if (_n == _table.size()){vector<Node* > newtable(2 * _table.size(), nullptr);         //创建一个新的newtableHashfunc<K> HFunc;for (size_t i = 0; i < _table.size(); i++)              //遍历原hashtable，将节点移到新的hastable里{if (_table[i])                                  //如果不为空，则移动节点到新表的对应位置上{Node* cur = _table[i];while (cur){//头插到新表对应位置size_t hashi = HFunc(kot(cur->_date)) % newtable.size();Node* next = cur->_next;cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;       //移动完后，将原表中映射位置置空}}               _table.swap(newtable);          //调用vector的的swap函数完成交换}//插入代码Hashfunc<K> HFunc;size_t hashi = HFunc(kot(date)) % _table.size();if (_table[hashi]){//头插Node* newnode = new Node(date);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);}else{Node* newnode = new Node(date);_table[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}}//查找Node* find(const K& key){KeyofT kot;Hashfunc<K> HFunc;size_t hashi = HFunc(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_date) == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hashfunc<K> HFunc;size_t hashi = HFunc(key) % _table.size();if (_table[hashi]){Node* cur = _table[hashi];Node* parent = nullptr;while (cur){KeyofT kot;if (kot(cur->_date) == key)      //找到了{if (cur == _table[hashi])   //是第一个节点{delete cur;_table[hashi] = nullptr;_n--;return true;}else                       //不是第一个节点{if(parent)parent->_next = cur->_next;delete cur;_n--;return true;}}parent = cur;cur = cur->_next;}return false;}else{return false;}}private:vector<Node*> _table;           //表size_t _n;                     //记录储存的有效数据个数
};

4.用实现的哈希封装unordered_map与unordered_set前的模板参数的梳理及相关联系的梳理

我们是想要用同一个哈希表封装出不同的容器（unordered_map与unordered_set），所以就需要对相关操作参数及操作做出改变。

unordered_map与unordered_set存储的数据类型不同，unordered_map存储的是pair<K,V> ，K为key的类型，V为value的类型而unordered_set，存储的是K，所以就需要对节点所存储的数据类型做出改变，如图：
因为unordered_map中的key为pair中的第一个数据，而unordered_set中存储的数据就是key，所以当在需要取出数据里面的key进行操作时，unordered_map与unordered_set取出的方法有差异，所以需要各自提供一个仿函数来实现：如图：

5.unordered_map的封装实现

#pragma once
#include"HashTable.h"
namespace map
{template<class K, class V, class HFunc = Hashfunc<K>>class unorderedmap{struct mapKeyofT              //取数据中的key，即pair<K,V>中的k{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashTable<K, pair<K, V>, mapKeyofT, HFunc>::iterator iterator;pair<iterator,bool> insert(const pair<K, V>& kv){return _ht.insert(kv);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V& operator[](const K& key){pair<iterator, bool> ret = _ht.insert(make_pair(key,V()));return (ret.first)->second;}private:HashTable<K, pair<K, V>, mapKeyofT, HFunc> _ht;    //需要用自己的mapKeyofT去实例化一个HashTable};

6.unordered_set的封装实现

#pragma once
#include"HashTable.h"
namespace set
{template<class K, class HFunc = Hashfunc<K>>class unorderedset{struct setKeyofT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, setKeyofT, HFunc>::iterator iterator;pair<iterator, bool> insert(const K& key){return _ht.insert(key);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}private:HashTable<K, K, setKeyofT, HFunc> _ht;   //需要用自己的setKeyofT去实例化一个HashTable};