素材下载网站开发文档,网站购物建设实训心得体会,昆山做网站企业,wordpress 汽车 模板下载前言#xff1a;我们前面已经学习论map和set#xff0c;现在又冒出来一个unordered_map和unordered_set#xff0c;这两个有啥差别吗#xff1f;前面我们已经说过#xff0c;map和set的底层是红黑树#xff0c;那unordered_map和unordered_set的底层是什么呢#xff1f;…
前言我们前面已经学习论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成员函数及功能
2unordered_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 ); 分配器构造法
template class InputIteratorunordered_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_listvalue_type il,size_type n /* see below */,const hasher hf hasher(),const key_equal eql key_equal(),const allocator_type alloc allocator_type() ); 初始化列表构造法在C11后一切皆可{}初始化例如
unordered_setint a{1,2,3,4,5} 12345会形成一个初始化列表这样子方便连续的构造 可以一次性就把所有初始化列表里面的值构造无需多次调用构造函数。
3成员函数及功能
unordered_set - C Referencehttps://legacy.cplusplus.com/reference/unordered_set/unordered_set/
2unordered_map
1函数模板参数 首先我们看模板参数T也就是valueHash函数默认是哈希桶Pred则是一个判断两个key是不是相等的函数用来查找元素和插入元素时判断是否存在Alloc则类似于new开辟空间。
2构造函数 explicit unordered_map ( const allocator_type alloc );
分配器构造法
template class InputIterator
unordered_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_listvalue_type il, 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码值转换为整型不就行了吗
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 特化 是匹配问题当为string类型是不会走上面的HashFunc函数特化的模板函数的格式在下面
template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash e;hash * 131;}return hash;}
};
我们也提供几种Hash整形的转换方法。
2常见哈希函数
1. 直接定址法--(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 面试题字符串中第一个只出现一次字符 2. 除留余数法--(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址 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{pairK, V _val; //一个存Key一个存valueState _state;};
private:std::vectorElem _ht;size_t _size;size_t _totalSize; // 哈希表中的所有元素有效和已删除, 扩容时候要用到
};
3)插入
bool Insert(const pairK, V val) {if (((double)_size/_ht.size())0.7) {//如果元素占了整个数组大小的7/10就扩容HashTableK, V 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) //没找到返回falsereturn 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]._stateDELETE) return 0;return site1; //返回下标}
6完整代码
#pragma once
#includestring
#includevector
#include algorithm
#includeiostream
using namespace std;
namespace Close_Hash
{enum State { EMPTY, EXIST, DELETE };templateclass K, class Vclass HashTable{struct Elem{pairK, V _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 pairK, V val) {if (((double)_size/_ht.size())0.7) {HashTableK, V 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]._stateDELETE)return 0;return site1;}// 删除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(HashTableK, V 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::vectorElem _ht;size_t _size;size_t _totalSize; // 哈希表中的所有元素有效和已删除, 扩容时候要用到};
}
5悬挂法
悬挂法人如其名它的结构就是一个数组下面挂在一堆链表也就是说数组里面并不直接存着元素而是存着指针这种方法有什么好处呢前面我们的线性探测法如果当前位置被占了就需要找下一个空位而悬挂法只需要在链表下面多加一个元素就行了。但是有一个小技巧我们新加入的元素不需要挂在最后只需要取代第一个结点的位置就行了。 1私有成员变量
悬挂法需要一个一个数组数组里面应该包括一个结点的struct指针struct里面应该包括数据和下一个结点的地址。
templateclass Tstruct HashNode{HashNodeT* _next;T _data;HashNode(const T data):_next(nullptr), _data(data){}};
private:vectorNode* _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 string
#include vector
#include Common1.husing namespace std;namespace OpenHash
{templateclass Tclass HashFunc{public:size_t operator()(const T val){return val;}};templateclass HashFuncstring{public:size_t operator()(const string s){const char* str s.c_str();unsigned int seed 131; // 31 131 1313 13131 131313unsigned int hash 0;while (*str){hash hash * seed (*str);}return hash;}};templateclass Vstruct HashBucketNode{HashBucketNode(const V data): _pNext(nullptr), _data(data){}HashBucketNodeV* _pNext;V _data;};// 本文所实现的哈希桶中key是唯一的templateclass V, class HF HashFuncVclass HashBucket{typedef HashBucketNodeV Node;typedef Node* PNode;typedef HashBucketV, HF 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 0HashBucketT 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);
#endifSelf 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:vectorNode* _table;size_t _size; // 哈希表中有效元素的个数};
}
