-
【C++】哈希表特性总结及unordered_map和unordered_set的模拟实现
前言
- unordered系列关联式容器是C++11中新增的一类容器，包括unordered_map，unordered_set，unordered_multimap和unordered_multiset。
- 它们的底层实现是哈希表，可以快速地查找和插入元素，时间复杂度为O(1)。
- 它们的元素是无序的，因此遍历时元素的顺序是不确定的。
- 它们的使用方式和红黑树结构的关联式容器（如map和set）基本类似，只是需要包含不同的头文件（
或 ）。 - 它们支持直接访问操作符（operator[]），可以使用key作为参数直接访问value。
- 哈希最大的作用就是查找（效率很高的），哈希并不具有排序的功能，unordered_map和unordered_set仅仅只有去重的功能而已
一、哈希表的特性 - 哈希函数和哈希冲突
- 哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表中有多少条数据，插入和查找的时间复杂度都是为O(1)。
- 哈希表是通过把关键码值映射到表中一个位置来访问记录，这个映射函数叫做散列函数或哈希函数。
- 哈希表的元素是无序的，因为散列函数的映射结果是随机的。
- 哈希表可能会产生碰撞，也叫哈希冲突，就是不同的关键码值映射到同一个位置，这时就需要采用一些方法来解决碰撞，比如开放地址法或链表法，同时。
1 哈希函数
- 直接定址法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B，常用的A是1，B是0。
优点：简单、均匀
缺点：需要事先知道关键字的分布情况，若分布较广，则空间消耗比较高。
使用场景：适合查找比较小且连续的情况 - 除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址，一般不这么干，最常用的就是拿vector.size()作为除数，每次扩容将vector.size()扩容二倍。但后面开散列的解决方式那里，我们会仿照库，用质数的集合作为vector.size()，然后用其作为除数。
2. 哈希冲突
当多个关键码key在通过哈希函数映射之后，得到了相同的哈希地址，也就是多个key映射到同一个位置上时，这种现象称为哈希冲突或哈希碰撞。解决哈希冲突的办法一般为两种，一种是闭散列的方式解决，即用线性探测或二次探测的方式向后寻找空的哈希位置，一种是开散列的方式解决，即将哈希冲突的元素通过单链表链接，逻辑上像哈希表挂了一个个的桶，所以这样的解决方式也可称为链地址法，或哈希桶方式。
区别概念：介绍一下闭散列和开散列：- 开散列和闭散列都是解决哈希冲突的方法，也就是当不同的关键码值映射到同一个位置时，如何处理的问题。
- 开散列方法又叫链地址法，它是把发生冲突的关键码存储在散列表主表之外，每个位置对应一个链表，链表的头节点存储在主表中。这样，当查找一个关键码时，先通过散列函数得到其位置，然后在对应的链表中进行查找。
- 闭散列方法又叫开放地址法，它是把发生冲突的关键码存储在主表中另一个槽内。这样，当查找一个关键码时，如果发现其位置已经被占用，就按照一定的规则寻找下一个空闲的位置，直到找到或者遍历整个表。
- 开散列和闭散列的区别是：
- 开散列需要额外的空间来存储链表节点，而闭散列不需要；
- 开散列可以容纳任意多的元素，而闭散列的容量有限；
- 开散列的查找效率取决于链表的长度，而闭散列的查找效率取决于探测规则；
- 开散列更适合关键码值分布不均匀的情况，而闭散列更适合关键码值分布均匀且空间紧张的情况。
二、闭散列的实现 – 开放地址法
1. 定义数据结构
闭散列的实现，我们以键值作为存储元素来讲解。
我们采用vector作为底层容器，用vector来存储哈希结点，哈希结点是一个结构体，其中存储键值对和状态值，_state用于标定哈希映射位置为空、存在、删除三种状态。
同时为了判断什么时候进行哈希表的扩容，在hashTable类中多增加了一个无符号整型的_n变量，表示当前哈希表中存储数据的个数，方便我们用数据个数和vector.size()作除法，看结果是否大于负载因子，如果大于则扩容，如果不大于则继续插入。enum state { EMPTY, EXIST, DELETE }; template <class K, class V> struct HashNode { HashNode() : _state(EMPTY) {} HashNode(const pair<K, V>& kv) :_kv(kv) , _state(EMPTY) {} pair<K, V> _kv; //数据 enum state _state; //状态 }; //...... };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
2.insert()
负载因子
哈希表冲突越多，效率越低
若表中位置都满了，就需要扩容 ，我们利用负载因子进行判断何时扩容负载因子的概念
负载因子 = 填入表的元素个数 / 表的长度
表示 表储存数量的百分比填入表的元素个数 越大，表示冲突的可能性越大，
填入表的元素个数 越小，表示冲突的可能性越小
所以在开放定址法时，应该控制在0.7-0.8以下，超过就会扩容线性探测
哈希表的线性探测原理是一种解决哈希冲突的方法，它的基本思想是：当发生哈希冲突时，就从当前位置开始，顺序查找下一个空闲的位置，然后将数据插入到该位置。例如，如果我们要将数据 88 插入到哈希表中，经过哈希函数计算得到的数组下标是 16 ，但是在数组下标为 16 的位置已经有其他元素了，那么就继续查找 17 ， 18 ，直到找到一个空闲的位置，然后将 88 插入到该位置。
在实现扩容时，我们进行代码复用，我们不再新建立vector，而是新建立一个哈希表，对新哈希表中的vector进行扩容，然后调用哈希表的Insert函数，将原vector中的键值对的关键码插入到新哈希表当中，这样就不需要自己在写代码，进行代码复用即可。最后将新哈希表中的vector和原哈希表的vector进行swap即可，这样就完成了原有数据到新表中的挪动，然后再插入要插入的kv即可。
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; //大于标定的负载因子，进行扩容，降低哈希冲突的概率 if (_n * 10 / _tables.size() > 7)//可能会出现除0错误 { //旧表数据，重新计算，映射到新表 /*vectornewtables; newtables.resize(2 * _tables.size()); */ HashTable<K, V, BKDRHash<K>> newHT; newHT._tables.resize(2 * _tables.size()); for (auto& e : _tables) { if (e._state == EXIST) { newHT.Insert(e._kv); //取原表中的数据插入到新表的vector里面，键值对之间发生赋值重载。因为newHT是新开的初始化好的哈希表 //递归通常是自己调用自己，这里不是递归，仅仅是代码复用而已。 } } _tables.swap(newHT._tables); } size_t hashi = Hash()(kv.first) % _tables.size();//这里不能%capacity，某些位置不是可用的，vector[]会对下标检查 while (_tables[hashi]._state == EXIST) { //线性探测 ++hashi; //二次探测 //hashi = hashi + i * i;//降低冲突概率，但还是有可能会冲突，占其他位置 hashi %= _tables.size(); } /*_tables[hashi] = Node(kv); _tables[hashi]._state = EXIST;*/ //在构造新表对象时，默认构造已经初始化好哈希表里面的结点空间了，你再开空间拷贝数据浪费。 _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
3.Find()
查找的思想非常简单，我们首先利用要查找的key值求出映射的哈希地址，如果当前位置的状态为存在或者删除，则继续找，若在循环中找到了，则返回对应位置的地址，若没找到则返回nullptr，遇见空则结束查找。
在线性探测中，如果查找到尾部了，则让hashi%=vector的size即可，让hashi回到开头的位置。但有一种极端特殊情况，就是边插入边删除，这样整个哈希表中的结点状态有可能都是delete或exist，则在线性探测中不会遇到empty，while会陷入死循环，所以在while里面多加一层判断，如果start等于hashi，说明在哈希表中已经线性探测一圈了，那此时就返回，因为找了一圈都没找到key，那就说明key不在哈希表里面。
Node* Find(const K& key) { size_t hashi = Hash()(key) % _tables.size(); size_t start = hashi; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST) { return &_tables[hashi]; } ++hashi; hashi %= _tables.size();//防止越界 if (start == hashi) break; } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
4. Erase()
大部分数据结构容器的删除其实都是伪删除或者叫做惰性删除，因为我们无法做到释放一大块空间的某一部分空间，所以在数据结构这里的删除基本都是用标记的伪删除 ,哈希表的删除也一样，我们在每个结点里面增加一个状态标记，用状态来标记当前结点是否被删除。如果删除结点不存在，则返回false。
bool Erase(const K& key) { Node* ret = Find(key); if (ret == nullptr) return false; ret->_state = DELETE; --_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
5.仿函数处理key值不能取模无法映射 — BKDRHash
上面代码中，对于整型数据可以完成key值取模映射，那如果我们的数据是string类型，怎么解决？string如何对vector的size取模呢？此时就需要仿函数来完成自定义类型转换为整型的操作了，只有转换为整型，我们才能取模，进而才能完成哈希映射的工作。
对于其他类型，比如int，char，short，double等，我们直接强转为size_t，这样就可以完成哈希映射。字符串转换为整型的场景还是比较常见的，网上有很多关于字符串哈希的算法，我们取最优的算法，思路就是将每一个字符对应的ascll码分别拆下来，每次的hash值都为上一次的hash值×131后再加上字符的ascll码值，遍历完字符串后，最后的hash为字符串转成整型的结果，这样每个字符串转换后的整型是极大概率不重复的，是一个非常不错的哈希算法，被人们称为BKDRHash。
template <class K> struct BKDRHash { size_t operator()(const K& key) { return (size_t)key;//只要这个地方能转成整型，那就可以映射，指针浮点数负数都可以，但string不行 } }; template <> struct BKDRHash<string> { size_t operator()(const string& key) { //return key[0];//字符串第一个字符是整型，那就可以整型提升，只要是个整型能进行%模运算，完成映射即可。 size_t hash = 0; for (auto ch : key) { hash = hash * 131 + ch; } return hash; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
三、开散列的实现 — 链地址法（哈希桶）
开散列的哈希表是最常用的方式，库里面的unordered_map和unordered_set用的也是哈希桶的方式实现的，我们模拟实现的哈希桶也仿照库实现，哈希结点node里面存储键值对和下一个结点指针。
1. 定义框架结构
在哈希表的模板参数中，也多加了一个缺省仿函数类的参数，也就是Hash，因为我们需要Hash的仿函数对象或匿名构造，将key转成整型。
template <class K, class V> struct hashNode { hashNode(const pair<K,V>& kv) :_kv(kv) ,_next(nullptr) {} pair<K, V> _kv; hashNode<K, V>* _next; }; template <class K, class V, class Hash = BKDRHash<K>> class hashTable { public: typedef hashNode<K, V> Node; …………省略 private: vector<Node*> _table; size_t _n; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
对于哈希桶，我们必须写出析构函数，因为编译器默认生成的析构函数会调用vector的析构，而vector的析构仅仅只能将自己的空间还给操作系统，如果某些节点指针指向了具体的节点，则只归还vector的空间是不够的，还需要归还那些申请的节点空间。
所以需要遍历每一个哈希桶，将每一个桶里面的节点都还给操作系统，这里就用到单链表的节点删除的知识了，在删除前需要保留下一个位置，要不然delete归还空间之后就找不到下一个节点的位置了。2.insert()
为什么进行头插？
对单链表进行尾插，因为尾插还需要找尾，那就需要遍历桶，这样的效率太低，并且桶中也不要求次序什么的，所以我们直接进行头插即可，头插的效率很高，因为映射找到哈希地址之后即可进行头插。- 哈希桶的负载因子，官方默认值为1.0，那就是_n和vector.size()相等的时候进行扩容，扩容的目的还是重新建立映射关系，缓解哈希冲突，因为如果某一个哈希桶的结点个数过多，在哈希映射之后还需要遍历哈希桶寻找结点，会降低哈希查找的效率，所以扩容就是多增加哈希桶的个数，减少平均哈希桶中结点的个数，提高哈希查找的效率。
2.注意我们遍历原表的每个结点指针，将每个指针指向结点的key重新计算哈希映射关系，头插到新的vector里面，在每完成一个桶的重新映射关系后，将原vector中的桶位置的指针置为空，否则析构的时候，结点会被析构两遍。等到原表的所有结点遍历完之后，将新的vector和原来的vector一交换即可，临时对象_newtable在离开函数栈帧时会被销毁，调用vector的默认析构完成空间的归还即可
研究表明，每次除留余数法最好模一个素数，这会大概率降低哈希冲突的可能性。所以我们下面的扩容大小每次挑选小于2倍的最大素数作为扩容后的vector大小，这里复用了一下stl库里面的素数表。
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 }; for (size_t i = 0; i < __stl_num_primes; i++) { if (__stl_prime_list[i] > n) { return __stl_prime_list[i]; } } return __stl_prime_list[__stl_num_primes - 1]; } bool Insert(const pair<K, V>& kv) { if (Find(kv.first))//不允许重复元素 return false; //负载因子控制在1，超过就扩容 if (_n == _table.size()) { vector<Node*> _newtable; _newtable.resize(__stl_next_prime(_table.size()), nullptr);//resize开空间后，默认值为Node*()的构造，我们也可以自己写 for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; size_t hashi = Hash()(cur->_kv.first) % _newtable.size(); cur->_next = _newtable[hashi]; _newtable[hashi] = cur; cur = next; } _table[i] = nullptr; } _table.swap(_newtable); } size_t hashi = Hash()(kv.first) % _table.size(); Node* newnode = new Node(kv); newnode->_next = _table[hashi];//newnode的next指向当前表哈希映射位置的结点地址 _table[hashi] = newnode;//让newnode做头 ++_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
3.Find()
哈希桶的查找和闭散列的哈希表很相似，先通过key找到映射的哈希桶，然后去对应的哈希桶里面找查找的结点即可，找到返回结点地址，未找到返回nullptr即可。
Node* Find(const K& key) { size_t hashi = Hash()(key) % _table.size(); Node* cur = _table[hashi]; while (cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
4.Erase()
哈希桶的erase其实就是单链表结点的删除，如果是头删，那就是下一个指针作头，如果是中间删除，则记录前一个结点位置，让前一个结点的next指向删除结点的next。然后归还结点空间的使用权，即为delete结点指针。
bool Erase(const K& key) { Node* ret = Find(key); if (!ret) return false; size_t hashi = Hash()(key) % _table.size(); Node* cur = _table[hashi]; if (cur->_kv.first == key)//头删 { _table[hashi] = cur->_next; delete cur; cur = nullptr; } else//中间删除 { while (cur) { Node* prev = cur; cur = cur->_next; if (cur->_kv.first == key) { prev->_next = cur->_next; delete cur; cur = nullptr; } } } --_n; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
四、封装实现unordered系列容器
封装实现unordered系列容器所需硬件的哈希表结构以及哈希函数、插入、查找、删除这些接口我们直接复用开散列哈希桶的接口即可，重点在于我们实现容器的迭代器操作，只要实现了迭代器的操作，那我们自己封装的unordered系列容器基本上就能跑起来了。
1.迭代器设计
- 迭代器需要定义一些模板参数，包括键值类型、元素类型、哈希函数类、键值获取类等。其中，元素类型对于unordered_set来说就是键值类型，对于unordered_map来说就是pair
类型。哈希函数类用于将元素类型转换为整数类型，键值获取类用于从元素类型中提取键值。 - 迭代器需要封装两个指针，一个是节点指针，用于指向当前遍历的元素，另一个是哈希表指针，用于在遍历完一个链表后找到下一个不为空的链表。
- 迭代器需要重载一些运算符，包括*和->运算符，用于访问当前元素的数据域；++运算符，用于移动到下一个元素；==和!=运算符，用于比较两个迭代器是否指向同一个元素。
- 迭代器需要提供一些构造函数和析构函数，用于创建和销毁迭代器对象。
//前置声明 template <class K, class T, class Hash, class KeyOfT> class hashTable; template <class K, class T, class Hash, class KeyOfT> struct __HTIterator { typedef hashNode<T> Node; typedef hashTable<K, T, Hash, KeyOfT> HT; typedef __HTIterator<K, T, Hash, KeyOfT> Self; Node* _node; HT* _ht; __HTIterator(Node* node, HT* ht) :_node(node) ,_ht(ht) {} Self& operator++() { if (_node->_next) { _node = _node->_next; } else { //当前桶走完了，要去哈希表里面找下一个桶 size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_table.size(); hashi++; while (hashi != _ht->_table.size() && _ht->_table[hashi] == nullptr) { hashi++; } if (hashi == _ht->_table.size()) _node = nullptr; else _node = _ht->_table[hashi]; } return *this; } T& operator->() { return &_node->_data; } T* operator*() { return _node->_data; } bool operator!=(const Self& it)const { return _node != it._node; } bool operator==(const Self& it)const { return _node == it._node; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
2.unordered_map的[ ]操作
我们知道unordered_map是一个无序关联容器，内部使用哈希表和桶来存储键值对。所以当使用[ ]操作符访问一个键时，unordered_map应先计算该键的哈希值，然后根据哈希值找到对应的桶。
- 如果桶中没有任何元素，或者没有找到与该键相等的元素，unordered_map会在桶中插入一个新的节点，键为给定的键，值为默认构造的值。
- 如果桶中有一个或多个元素，并且找到了与该键相等的元素，unordered_map会返回该元素的引用¹。
- 如果桶中有多个元素，并且没有找到与该键相等的元素，unordered_map会在桶的末尾插入一个新的节点，键为给定的键，值为默认构造的值。
V& operator[](const K& key) { pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; } pair<iterator,bool> Insert(const T& data) { KeyOfT kot; iterator it = Find(kot(data)); if (it != end()) return make_pair(it, false);//如果插入的值已经存在那就不再进行插入，返回对应位置迭代器即可。 if (_n == _table.size()) { vector<Node*> _newtable; _newtable.resize(__stl_next_prime(_table.size()), nullptr); for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; size_t hashi = Hash()(kot(cur->_data)) % _newtable.size(); cur->_next = _newtable[hashi]; _newtable[hashi] = cur; cur = next; } _table[i] = nullptr; } _table.swap(_newtable); } size_t hashi = Hash()(kot(data)) % _table.size(); Node* newnode = new Node(data); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return make_pair(iterator(newnode, this), true); } void test_unordered_map() { string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" , "蓝莓" ,"草莓" }; unordered_map<string, int> countMap; for (auto& e : arr) { countMap[e]++; } unordered_map<string, int>::iterator it = countMap.begin(); //1.不用语法糖，一点一点遍历也可以 while (it != countMap.end()) { cout << it->first << ":" << it->second << endl; ++it; } //2.我们实现了迭代器，直接用语法糖也可以。 for (const auto& kv : countMap)//将解引用后的迭代器赋值给kv { cout << kv.first << ":" << kv.second << endl; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
本节完
-
相关阅读:
面试官：订单ID是怎么生成的？难道不是MySQL自增主键？
Kotlin | 在for、forEach循环中正确的使用break、continue
视频剪辑技巧，给每个视频添加不同背景图
中国石油大学(北京)-《 油气藏经营管理》第一阶段在线作业
易基因｜疾病研究：DNA甲基化和转录组学特征在高浆卵巢癌复发和耐药过程中高度保守
LeetCode高频题300. 最长递增子序列
vue3 + antd 图片上传 （精简篇）cv即可
做了3年Java，靠着这份面试题跟答案，我从15K变成了30K
2-95 基于matlab的模板定位
LeetCode|动态规划|392. 判断子序列、115. 不同的子序列、 583. 两个字符串的删除操作
- 原文地址：https://blog.csdn.net/weixin_62676865/article/details/130840380
