做网站备案谁做,中文企业网站模板,中俄跨境电商平台有哪些,网站程序源码目录 1. 简介unordered_set与unordered_map2. 哈希表#xff08;散列#xff09;2.1 哈希表的引入2.2 闭散列的除留余数法2.2.1 前置知识补充与描述2.2.2 闭散列哈希表实现 2.3 开散列的哈希桶2.3.1 结构描述2.3.2 开散列哈希桶实现2.3.3 哈希桶的迭代器与key值处理仿函数 3.… 目录 1. 简介unordered_set与unordered_map2. 哈希表散列2.1 哈希表的引入2.2 闭散列的除留余数法2.2.1 前置知识补充与描述2.2.2 闭散列哈希表实现 2.3 开散列的哈希桶2.3.1 结构描述2.3.2 开散列哈希桶实现2.3.3 哈希桶的迭代器与key值处理仿函数 3. unordered_set与unordered_map的封装3.1 哈希桶的细节调整3.2 具体封装 1. 简介unordered_set与unordered_map 在C库中除开map与set这两个关联式容器外还存在着另外两个此类容器unordered_setunordered_map。unordered中文释义为无序的这也正是这一对容器使用时的表征特点这一对容器分别对应set与map即K模型与KV模型的存储数据结点。那么除开使用迭代器遍历时其内存储数据无序外这一对容器与map与set容器有何不同为什么要在已有map与set的情况下再向库中加入这一对乍看功能冗余且劣于原本map与set的容器呢我们来看下面的一组对照试验。unordered_set与unordered_map其的关键性常用接口与使用和mapset相同不同的是其只支持正向迭代器且多了一些桶负载因子相关的接口。 #include iostream
using namespace std;
#include unordered_set
#include set
#include stdlib.h
#include time.h
#include vectorint main()
{const int N 1000000;vectorint data(N);setint s;unordered_setint us;srand((unsigned int)time(NULL));for (int i 0; i N; i){//data.push_back(rand());//重复数据多//data.push_back(rand() i);//重复数据少data.push_back(i);//有序数据}//插入int begin1 clock();for (auto e : data){s.insert(e);}int end1 clock();int begin2 clock();for (auto e : data){us.insert(e);}int end2 clock();cout insert number s.size() endl endl;//查找int begin3 clock();for (auto e : data){s.find(e);}int end3 clock();int begin4 clock();for (auto e : data){us.find(e);}int end4 clock();int begin5 clock();for (auto e : data){s.erase(e);}int end5 clock();int begin6 clock();for (auto e : data){us.erase(e);}int end6 clock();cout set Insert end1 - begin1 endl;cout unordered Insert end2 - begin2 endl endl;cout set Find end3 - begin3 endl;cout unordered Find end4 - begin4 endl endl;cout set Erase end5 - begin5 endl;cout unordered Erase end6 - begin6 endl endl;return 0;
}运行结果 由运行结果可得 1 当数据无序时在重复数据较多的情况下unordered系列的容器插入删除效率更高 2 当数据无序但重复数据较少的情况下两种类型的容器两者插入数据效率仿佛 3 当数据有序时红黑树系列的容器插入效率更高在日常的应用场景中很少出现有序数据情况虽然mapset有着遍历自得有序这一优势但关联式容器的主要功能为映射关系与快速查询其他优点尽是附带优势。所以unordered系列容器的加入与学习是必要的。 2. 哈希表散列
2.1 哈希表的引入 在初阶数据结构的学习中我们学习了一种排序方式叫做基数排序其使用数组下标表示需排序数据下标对应的元素代表相应数据的出现次数。以此映射数据并排序时间复杂度只有O(n)。基数排序创建的数据存储数组除可以用于数据排序外我们不难发现其用来查询一个数据在或不再可以通过访问下标对应数据直接得到查询效率及其高。这一为排序所创建的存储数组就是一个简单的哈希表我们也称之为散列即数据并非连续而是散列在一段连续的空间中。哈希表中的哈希是指一种数据结构的设计思想为通过某种映射关系为存储数据创建一个key值其的映射关系不一但都可以通过key值找到唯一对应的一个数据且使得数据散列在存储空间中。上述的存储结构为常见哈希表结构的一种我们称之为直接定址法哈希表但此种哈希表其使用上存在诸多限制当存储数据的范围跨度较大时就会使得空间浪费十分严重。接下来我们来学习几种在其基础上进行优化具有实用价值的常用哈希表结构。 2.2 闭散列的除留余数法
2.2.1 前置知识补充与描述 除留余数法为了解决存储数据大小范围跨度过大的问题我们不再直接使用存储数据左key值映射而是通过存储数据除以哈希表大小得到的余数做key值。这样就能将所有数据集中映射至一块指定大小的空间中。哈希冲突/哈希碰撞取余数做key值的方式虽然能够使得数据映射到一块指定空间中并大幅度减少空间的浪费可是这也会产生一个无法避免的问题那就是不同数据的经过取余得到的余数可能相同如此就会导致同一key值映射多个数据使得无法进行需要的存储与查询。这一问题就被称为哈希碰撞。线性探测与二次探测哈希碰撞的解决存在多种方法策略这里我们简单了解两种常用方式 1 线性探测当前key值对应数据位被占用时向后遍历hashi i直至找到为空的数据位再将数据存入而探测查询时也以线性逻辑搜索直至遍历至空则代表查询数据不存在越界回绕。 2 二次探测当前key指对数据位被占用时当前key值依次加正整数的平方hashi i 2 i^2 i2直至遍历至空存入探测查询时依次逻辑或至空结束越界回绕。补充 1 负载因子哈希表中存储数据个数与哈希表长度的比值一般控制在0.7左右若负载因子超过进行扩容 2 线性探测容易导致数据的拥堵与踩踏二次探测的方式为对此的优化 3 处理非数字类型数据将其转换为size_t类型后再进行key值映射采用仿函数的方式 2.2.2 闭散列哈希表实现
哈希表结构
//结点状态
enum State
{EMPTY,//可插入查询结束EXIST,//不可插入向后查询DELETE//可插入向后查询
};//数据结点
templateclass K, class V
struct HashNode
{pairK, V _kv;State _state;HashNode(const pairK, V kv make_pair(K(), V())):_kv(kv),_state(EMPTY){}
};//哈希表
templateclass K, class V, class hash HashFuncK
class HashTable
{typedef HashNodeK, V HashNode;typedef Hash_iteratorK, V, hash iterator;
public:HashTable(size_t n 10){_table.resize(n);}//迭代器相关iterator begin();iterator end(); //查找HashNode* Find(const K key);//插入bool Insert(const pairK, V kv);//删除bool Erase(const K key);private:vectorHashNode _table;//结点size_t n 0;//存储数据个数hash hs;//仿函数处理key值
};操作实现
//查找
HashNode* Find(const K key)
{int hashi hs(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST hs(_table[hashi]._kv.first) hs(key)){return _table[hashi];}hashi;hashi % _table.size();}return nullptr;
}//插入
bool Insert(const pairK, V kv)
{//扩容类型转换//重新建立映射关系插入(现代写法)if ((double)n / (double)_table.size() 0.7){HashTableK, V, hash newtable(_table.size() * 2);//迭代器for (auto e : _table){newtable.Insert(e._kv);}_table.swap(newtable._table);}//找到要插入的位置int hashi hs(kv.first) % _table.size();//线性探测while (_table[hashi]._state EXIST){if (_table[hashi]._kv.first kv.first){return false;}//可能越界需要回绕hashi;hashi % _table.size();}//插入单参数的构造函数支持隐式类型转换_table[hashi] kv;_table[hashi]._state EXIST;n;return true;
}//删除
bool Erase(const K key)
{//将要删除结点的状态改为deleteint hashi key % _table.size();//复用findHashNode* ret Find(key);if (ret){ret-_state DELETE;n--;return true;}else{return false;}
}迭代器相关接口
iterator begin()
{for (size_t i 0; i _table.size(); i){HashNode* cur _table[i];if (cur){return iterator(cur, this);}}return end();//补
}iterator end()
{return iterator(nullptr, this);
}key指出类型转换仿函数
//仿函数
templateclass K//数字类型
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//string类型全特化常用
template
struct HashFuncstring
{size_t operator()(string str){size_t key 0;for (auto e : str){key e;key * 131;}return key;}
};//其他类型自定义类型
struct Date
{int _year;int _month;int _day;
};struct HashDate
{size_t operator()(const Date d){size_t key 0;key d._day;key * 131;//科学建议值key d._month;key * 131;key d._year;key * 131;return key;}
};struct Person
{int name;int id;//有唯一项用唯一项无唯一项乘权值拼接int add;int tel;int sex;
};2.3 开散列的哈希桶
2.3.1 结构描述 除留余数法后线性探测的存储方式会导致数据的拥堵踩踏随着数据存储数量的增加踩踏与拥挤的现象会越来越频繁二次探测的优化也仅仅只是饮鸩止渴。由此我们来学习一种新的哈希结构也是使用最广泛的一种其存储方式为 顺序表中存储链表指针相同key值的数据构造成链表结构的数据结点挂入同一链表中此种数据结构就被称为哈希桶 2.3.2 开散列哈希桶实现
哈希桶结构
//数据结点
template class K, class V
struct HashNode
{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv),_next(nullptr){}
};//哈希桶结构
template class K, class V, class hash HashFuncK
class HashTable
{typedef HashNodeK, V, hash HashNode;
public://构造HashTable(size_t n 10){_table.resize(n, nullptr);_n 0;}//析构~HashTable(){for (size_t i 0; i _table.size(); i){HashNode* cur _table[i];while (cur){HashNode* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}private:vectorHashNode* _table;size_t _n;//插入数据个数计算负载因子与扩容hash hs;//非数字类型key值处理friend struct iterator;//迭代器会需要访问存储数据的vector
};操作实现
//插入
bool Insert(const pairK, V kv)
{//不支持键值冗余if (Find(kv.first))return false;//何时扩容负载因子到1就扩容插入数据个数if (_n _table.size()){vectorHashNode* newtable(2 * _table.size());//不再重新申请创建结点而是搬运for (size_t i 0; i _table.size(); i){HashNode* cur _table[i];while (cur){HashNode* next cur-_next;size_t hashi hs(cur-_kv.first) % newtable.size();cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable);}//计算插入位置size_t hashi hs(kv.first) % _table.size();//头插HashNode* newnode new HashNode(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;
}//查找
HashNode* Find(const K key)
{for (size_t i 0; i _table.size(); i){HashNode* cur _table[i];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}}return nullptr;
}//删除
bool Erase(const K key)
{size_t hashi hs(key) % _table.size();HashNode* cur _table[hashi];HashNode* prev nullptr;while (cur){if (cur-_kv.first key){if (prev){prev-_next cur-_next;}else{_table[hashi] cur-_next;}delete cur;_n--;return true;}prev cur;cur cur-_next;}return false;
}2.3.3 哈希桶的迭代器与key值处理仿函数
迭代器结构
//将迭代器代码写于哈希桶之前
//迭代器与哈希桶存在互相引用添加前置声明
templateclass K, class V, class hash
class HashTable;templateclass K, class V, class hash HashFuncK
struct Hash_iterator
{typedef HashNodeK, V HN;typedef HashTableK, V, hash HT;typedef Hash_iterator Self;HN* _node;HT* _ht;hash hs;Hash_iterator(HN* node, HT* ht):_node(node),_ht(ht){}//前置Self operator();V operator*();pairK, V* operator-();bool operator!(const Self it);};操作实现
//前置
Self operator()
{if (_node-_next){_node _node-_next;}else{size_t hashi hs(_node-_kv.first) % _ht-_table.size() 1;_node nullptr;//注while (hashi _ht-_table.size()){if (_ht-_table[hashi]){_node _ht-_table[hashi];break;}hashi;}//后续没有元素越界//_node _ht-_table[hashi];}return *this;
}V operator*()
{return _node-_kv.second;
}pairK, V* operator-()
{return _node-_kv;
}bool operator!(const Self it)
{return _node ! it._node;
}缺省的key值处理仿函数
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//特化常用string类型
template
struct HashFuncstring
{size_t operator()(const string str){size_t key 0;for (auto e : str){key e;key * 131;}return key;}
};3. unordered_set与unordered_map的封装
3.1 哈希桶的细节调整 使用哈希桶unordered_set与unordered_map的封装方式与红黑树封装mapset相似调整模板参数使得仅用一套模板即可封装出u_map与u_set具体操作如下 数据结点结构的调整
template class T//改
struct HashNode
{T _kv;HashNodeT* _next;HashNode(const T kv):_kv(kv),_next(nullptr){}
};迭代器结构的调整
templateclass K, class T, class KeyOfT, class hash HashFuncK
struct Hash_iterator
{typedef HashNodeT HN;typedef HashTableK, T, KeyOfT, hash HT;typedef Hash_iterator Self;HN* _node;HT* _ht;hash hs;KeyOfT kot;//其后细节随之调整
};哈希桶结构的调整
//将hash模板参数的缺省值提维
template class K, class T, class KeyOfT, class hash
class HashTable
{typedef HashNodeT HashNode;typedef Hash_iteratorK, T, KeyOfT, hash iterator;
private:vectorHashNode* _table;size_t _n;hash hs;KeyOfT kot;friend struct iterator; public://其他内部方法细节随之调整//为适配上层unordered_map的operator[]返回值与实现细节做调整pairiterator, bool Insert(const T kv);iterator Find(const K key);
};3.2 具体封装
unordered_set
//缺省提维的原因
//并非直接使用哈希桶而是通过usum来间接使用**
templateclass K, class hash HashFuncK
class myordered_set
{struct KeyOfT{K operator()(const K key){return key;}};typedef Hash_iteratorK, K, KeyOfT, hash iterator;typedef HashNodeK HashNode;
public:iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool Insert(const K key){return _ht.Insert(key);}iterator Find(const K key){return _ht.Find(key);}bool Erase(const K key){return _ht.Erase(key);}
private:HashTableK, K, KeyOfT, hash _ht;
};unordered_map
templateclass K, class V, class hash HashFuncK
class myordered_map
{struct KeyOfT{K operator()(const pairK, V kv){return kv.first;}};typedef Hash_iteratorK, pairK, V, KeyOfT, hash iterator;typedef HashNodepairK, V HashNode;
public:iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool Insert(const pairK, V kv){return _ht.Insert(kv);}iterator Find(const K key){return _ht.Find(key);}V operator[](const K key){pairiterator, bool ret Insert(make_pair(key, V()));return (ret.first)-second;}bool Erase(const K key){return _ht.Erase(key);}private:HashTableK, pairK, V, KeyOfT, hash _ht;
};
