前言:我们前面已经学习论map和set,现在又冒出来一个unordered_map和unordered_set,这两个有啥差别吗?前面我们已经说过,map和set的底层是红黑树,那unordered_map和unordered_set的底层是什么呢?接下来我们会逐渐揭开它神秘的面纱。
如果大家不了解map和set可以看我往期博客:C++之map与set的使用与原理+拓展avl树(详解)-CSDN博客
目录
一,unordered_map和unordered_set的使用
1)unordered_set
1)函数模板参数
2)构造函数
3)成员函数及功能
2)unordered_map
1)函数模板参数
2)构造函数
2)成员函数及功能
二,unordered_map和unordered_set的底层实现及代码
1)哈希表
2)常见哈希函数
3)线性探测法
4)线性探测法代码
1)提前准备
2)私有成员变量
3)插入
4)删除
5)查找
6)完整代码
5)悬挂法
1)私有成员变量
2)插入
3)删除
4)查找
5)完整代码
一,unordered_map和unordered_set的使用
1)unordered_set
1)函数模板参数
Hash模板参数默认是哈希桶(等下会讲原理),Pred则是一个判断两个key是不是相等的函数,用来查找元素和插入元素时判断是否存在,Alloc则类似于new开辟空间。
2)构造函数
explicit unordered_set ( const allocator_type& alloc );
分配器构造法
templateunordered_set ( InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
迭代器范围构造法
unordered_set ( const unordered_set& ust ); unordered_set ( const unordered_set& ust, const allocator_type& alloc );
拷贝构造法
unordered_set ( unordered_set&& ust ); unordered_set ( unordered_set&& ust, const allocator_type& alloc );
移动构造函数(右值引用构造,我后面的博客应该会讲右值引用,现在大家期待一下吧)
unordered_set ( initializer_listil, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
初始化列表构造法(在C++11后,一切皆可{}初始化,例如:
unordered_seta={1,2,3,4,5}
1,2,3,4,5会形成一个初始化列表,这样子方便连续的构造
可以一次性就把所有初始化列表里面的值构造,无需多次调用构造函数。
3)成员函数及功能
unordered_set - C++ Referencehttps://legacy.cplusplus.com/reference/unordered_set/unordered_set/
2)unordered_map
1)函数模板参数
首先我们看模板参数,T也就是value,Hash函数默认是哈希桶,Pred则是一个判断两个key是不是相等的函数,用来查找元素和插入元素时判断是否存在,Alloc则类似于new开辟空间。
2)构造函数
explicit unordered_map ( const allocator_type& alloc );
分配器构造法
templateunordered_map ( InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
迭代器范围构造法
unordered_map ( const unordered_map& ump ); unordered_map ( const unordered_map& ump, const allocator_type& alloc );
拷贝构造函数
unordered_map ( unordered_map&& ump ); unordered_map ( unordered_map&& ump, const allocator_type& alloc );
移动构造函数(右值引用构造)
unordered_map ( initializer_listil, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
初始化列表构造法
2)成员函数及功能
由于这是老生常谈了,大家看文档估计也能看懂,这里给大家一个链接,有兴趣的自行观看
unordered_map - C++ Referencehttps://legacy.cplusplus.com/reference/unordered_map/unordered_map/
二,unordered_map和unordered_set的底层实现及代码
1)哈希表
哈希表有点类似于我们的计数排序,但是计数排序有缺点就是只能排整形家族,哈希表就是会开大于我们要存储数据元素个数的大小(一般来说是数组),然后通过一个特点的转换公式把不同类型全部转化为无符号整形,然后按照下标存储,但是如何将不同类型的元素转换整形呢?这是一个问题,我们这里提供一个思路,假如是string或者插入类型,是不是它们都有ascll码值,将ascll码值转换为整型不就行了吗?
templatestruct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 特化 是匹配问题,当为string类型是不会走上面的HashFunc函数,特化的模板函数的格式在下面 template<>struct HashFunc { size_t operator()(const string& s) { size_t hash = 0; for (auto e : s) { hash += e; hash *= 131; } return hash; } };
我们也提供几种Hash整形的转换方法。
2)常见哈希函数
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)线性探测法
这种方法的解决办法是当发现两个位置冲突了之后,就从这个元素开始查找下一个空的元素,如果发现空的元素就插入,有些人可能会说如果全满了呢?那就回到0号下标开始继续查找,因为数组大小是大于元素个数的,所有不要担心全部满了。那查找呢?这种情况不能只查找映射位置,要一直往后找,直到碰到空。那如何删除了,删除不能直接删除,这样子可能会导致下次查找元素出现错误,因为这个位置制空后,查找的原则是找到空就停止,原本应该继续往后找的,但是因为你删除元素导致此位置为空,无法向后继续找,所有我们要有一个标记方法标注这里是被删除的,而不是本身就为空。
4)线性探测法代码
1)提前准备
首先我们需要一个东西来标记当前位置的状态,辨别删除和为空,防止误判,我们采用枚举
enum State { EMPTY, EXIST, DELETE };
2)私有成员变量
数组加枚举变量,数组因为里面要包括枚举和元素所以使用结构体封装一下
class Hash{ struct Elem { pair_val; //一个存Key,一个存value State _state; }; private: std::vector _ht; size_t _size; size_t _totalSize; // 哈希表中的所有元素:有效和已删除, 扩容时候要用到 };
3)插入
bool Insert(const pair& val) { if (((double)_size/_ht.size())>=0.7) {//如果元素占了整个数组大小的7/10就扩容 HashTable a; a._ht.resize(_ht.size()*2); //开辟新的空间 for (size_t i = 0; i < _ht.size(); i++) { if (_ht[i]._state == EXIST) { a.Insert(_ht[i]._val); } } a._ht.swap(_ht); //交换数据 _totalSize = _size; } size_t site = val.first % _ht.size(); //哈希函数求映射位 while (_ht[site]._state ==EXIST) { //找到空的位置或者已经被删除了的位置 site++; site = site % _ht.size(); } _ht[site]._state = EXIST; //改变状态 _ht[site]._val = val; _size++; _totalSize++; //数据个数加加 return true; }
4)删除
// 删除 bool Erase(const K& key) { size_t site = Find(key); //复用Find函数 if (site == 0) //没找到,返回false return false; _ht[site - 1]._state = DELETE; //改变状态和数据个数 _size--; return true; }
5)查找
// 查找 size_t Find(const K& key) { size_t site = key % _ht.size(); //利用哈希函数求映射值 while (_ht[site]._state != EMPTY&&_ht[site]._val.first!=key) { site++; //找到元素的位置并且位置状态位存在 site = site % _ht.size(); } if (_ht[site]._state == EMPTY||_ht[site]._state==DELETE) return 0; return site+1; //返回下标 }
6)完整代码
#pragma once #include#include #include #include using namespace std; namespace Close_Hash { enum State { EMPTY, EXIST, DELETE }; template class HashTable { struct Elem { pair _val; State _state; }; public: HashTable(size_t capacity = 5) : _ht(capacity), _size(0), _totalSize(0) { for (size_t i = 0; i < capacity; ++i) _ht[i]._state = EMPTY; } // 插入 bool Insert(const pair & val) { if (((double)_size/_ht.size())>=0.7) { HashTable a; a._ht.resize(_ht.size()*2); for (size_t i = 0; i < _ht.size(); i++) { if (_ht[i]._state == EXIST) { a.Insert(_ht[i]._val); } } a._ht.swap(_ht); _totalSize = _size; } //cout <<_size<<" "<<_ht.size() << "容量比:" << (double)_size / _ht.size() << endl; size_t site = val.first % _ht.size(); while (_ht[site]._state ==EXIST) { site++; site = site % _ht.size(); } _ht[site]._state = EXIST; _ht[site]._val = val; _size++; _totalSize++; return true; } // 查找 size_t Find(const K& key) { size_t site = key % _ht.size(); while (_ht[site]._state != EMPTY&&_ht[site]._val.first!=key) { site++; site = site % _ht.size(); } if (_ht[site]._state == EMPTY||_ht[site]._state==DELETE) return 0; return site+1; } // 删除 bool Erase(const K& key) { size_t site = Find(key); if (site == 0) return false; _ht[site - 1]._state = DELETE; _size--; return true; } size_t Size()const { return _size; } bool Empty() const { return _size == 0; } void Swap(HashTable & ht) { swap(_size, ht._size); swap(_totalSize, ht._totalSize); _ht.swap(ht._ht); } private: size_t HashFunc(const K& key) { return key % _ht.capacity(); } private: std::vector _ht; size_t _size; size_t _totalSize; // 哈希表中的所有元素:有效和已删除, 扩容时候要用到 }; }
5)悬挂法
悬挂法人如其名,它的结构就是一个数组下面挂在一堆链表,也就是说数组里面并不直接存着元素,而是存着指针,这种方法有什么好处呢?前面我们的线性探测法如果当前位置被占了就需要找下一个空位,而悬挂法只需要在链表下面多加一个元素就行了。但是有一个小技巧,我们新加入的元素不需要挂在最后,只需要取代第一个结点的位置就行了。
1)私有成员变量
悬挂法需要一个一个数组,数组里面应该包括一个结点的struct指针,struct里面应该包括数据,和下一个结点的地址。
templatestruct HashNode { HashNode * _next; T _data; HashNode(const T& data) :_next(nullptr) , _data(data) {} }; private: vector _table; size_t _size; // 哈希表中有效元素的个数
2)插入
悬挂法插入结点先通过哈希函数找到下标,然后按照我上面说的那种方法,具体代码实现及注释如下
Node* Insert(const V& data) { // 0. 检测是否需要扩容 CheckCapacity(); // 1. 通过哈希函数计算data所在的桶号 size_t bucketNo = HashFunc(data); // 2. 检测该元素是否在bucketNo桶中 // 本质:检测链表中是否存在data的节点 Node* pCur = _table[bucketNo]; while (pCur) { if (pCur->_data == data) return nullptr; pCur = pCur->_pNext; } // 插入新节点,直接头插 pCur = new Node(data); pCur->_pNext = _table[bucketNo]; _table[bucketNo] = pCur; ++_size; return pCur; }
3)删除
删除元素需要先通过哈希函数找到下标,然后按照顺序查找是否存在这个元素,然后删除,但是删除要注意必须保存其父节点不然删除无法更新链表,还有就要要注意删除头节点要单独处理
// 删除哈希桶中为data的元素(data不会重复) bool Erase(const V& data) { //哈希函数找结点,然后保存下标,需要一个指针指向其父亲 size_t bucketNo = HashFunc(data); Node* pCur = _table[bucketNo]; Node* pPre = nullptr; //找到下标后循坏查找 while (pCur) { if (data == pCur->_data) { // 删除 if (_table[bucketNo] == pCur) { // 删除第一个节点 _table[bucketNo] = pCur->_pNext; } else { // 删除的不是第一个节点 pPre->_pNext = pCur->_pNext; } delete pCur; --_size; return true; } pPre = pCur; pCur = pCur->_pNext; } return false; }
4)查找
如果仔细看了上面,估计查找已经手到擒来了,找到映射下标遍历就是了
Node* Find(const V& data) { size_t bucketNo = HashFunc(data); Node* pCur = _table[bucketNo]; while (pCur) { if (data == pCur->_data) return pCur; pCur = pCur->_pNext; } return nullptr; } size_t Size()const { return _size; } bool Empty()const { return 0 == _size; }
5)完整代码
#pragma once #include#include #include "Common1.h" using namespace std; namespace OpenHash { template class HashFunc { public: size_t operator()(const T& val) { return val; } }; template<>class HashFunc { public: size_t operator()(const string& s) { const char* str = s.c_str(); unsigned int seed = 131; // 31 131 1313 13131 131313 unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return hash; } }; template struct HashBucketNode { HashBucketNode(const V& data) : _pNext(nullptr), _data(data) {} HashBucketNode * _pNext; V _data; }; // 本文所实现的哈希桶中key是唯一的 template >class HashBucket { typedef HashBucketNode Node; typedef Node* PNode; typedef HashBucket Self; public: HashBucket(size_t capacity) : _table(GetNextPrime(capacity)) , _size(0) {} ~HashBucket() { Clear(); } // 哈希桶中的元素不能重复 Node* Insert(const V& data) { // 0. 检测是否需要扩容 CheckCapacity(); // 1. 通过哈希函数计算data所在的桶号 size_t bucketNo = HashFunc(data); // 2. 检测该元素是否在bucketNo桶中 // 本质:检测链表中是否存在data的节点 Node* pCur = _table[bucketNo]; while (pCur) { if (pCur->_data == data) return nullptr; pCur = pCur->_pNext; } // 插入新节点 pCur = new Node(data); pCur->_pNext = _table[bucketNo]; _table[bucketNo] = pCur; ++_size; return pCur; } // 删除哈希桶中为data的元素(data不会重复) bool Erase(const V& data) { size_t bucketNo = HashFunc(data); Node* pCur = _table[bucketNo]; Node* pPre = nullptr; while (pCur) { if (data == pCur->_data) { // 删除 if (_table[bucketNo] == pCur) { // 删除第一个节点 _table[bucketNo] = pCur->_pNext; } else { // 删除的不是第一个节点 pPre->_pNext = pCur->_pNext; } delete pCur; --_size; return true; } pPre = pCur; pCur = pCur->_pNext; } return false; } Node* Find(const V& data) { size_t bucketNo = HashFunc(data); Node* pCur = _table[bucketNo]; while (pCur) { if (data == pCur->_data) return pCur; pCur = pCur->_pNext; } return nullptr; } size_t Size()const { return _size; } bool Empty()const { return 0 == _size; } void Clear() { for (size_t i = 0; i < _table.capacity(); ++i) { Node* pCur = _table[i]; // 删除i号桶所对应链表中的所有节点 while (pCur) { // 采用头删 _table[i] = pCur->_pNext; delete pCur; pCur = _table[i]; } } _size = 0; } size_t BucketCount()const { return _table.capacity(); } void Swap(Self& ht) { _table.swap(ht._table); swap(_size, ht._size); } private: size_t HashFunc(const V& data) { return HF()(data) % _table.capacity(); } void CheckCapacity() { if (_size == _table.capacity()) { #if 0 HashBucket ht(_size * 2); // 将旧哈希桶中的元素向新哈希桶中进行搬移 // 搬移所有旧哈希桶中的元素 for (size_t i = 0; i < _table.capacity(); ++i) { Node* pCur = _table[i]; while (pCur) { ht.Insert(pCur->_data); // new 节点 pCur = pCur->_pNext; } } Swap(ht); #endif Self ht(GetNextPrime(_size)); // 将旧哈希桶中的节点直接向新哈希桶中搬移 for (size_t i = 0; i < _table.capacity(); ++i) { Node* pCur = _table[i]; while (pCur) { // 将pCur节点从旧哈希桶搬移到新哈希桶 // 1. 将pCur节点从旧链表中删除 _table[i] = pCur->_pNext; // 2. 将pCur节点插入到新链表中 size_t bucketNo = ht.HashFunc(pCur->_data); // 3. 插入节点--->头插 pCur->_pNext = ht._table[bucketNo]; ht._table[bucketNo] = pCur; } } this->Swap(ht); } } private: vector _table; size_t _size; // 哈希表中有效元素的个数 }; }