如何让网站快速收录,手机怎么搭建网站,阿里云购买网站登录,做网站教程免费unordered系列关联式容器 在之前的博文中介绍过关联式容器中的map与set#xff0c;同map与set一样#xff0c;unordered_set与unordered_set也是关联式容器。 在C98中#xff0c;STL提供了底层为红黑树结构的一系列关联式容器#xff0c;查询效率可以达到logN#xff1b;在…unordered系列关联式容器 在之前的博文中介绍过关联式容器中的map与set同map与set一样unordered_set与unordered_set也是关联式容器。 在C98中STL提供了底层为红黑树结构的一系列关联式容器查询效率可以达到logN在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器的使用方法类似但是其底层的实现不同。 unordered_map与unordered_set的底层实现都是哈希表。unordered关联容器与其他关联容器的区别是
unordered是单项迭代器unordered遍历出来的数据不是有序的unordered_set只能去重。不可以用于排序unordered_map也不可以用于排序无序数据可以使用unordered关联容器具有优势有序数据使用其他容器较快。
unordered_map的介绍
unordered_map的文档介绍 std::unordered_map
unordered_map是存储 key,value 键值对的关联式容器其允许通过keys快速的索引到与其对应的value。在unordered_map中键值通常用于唯一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部unordered_map没有对 key,value 按照任何特定的顺序排序为了可以在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代器方面效率较低。unordered_map实现了直接访问操作符operator[ ]它允许使用key作为参数直接访问value。unordered_map的迭代器至少是前向迭代器。
unordered_map的接口说明
unordered_map的构造
函数说明功能介绍unordered_map构造不同格式的unordered_map的对象
unordered_map的容量
函数说明功能介绍 bool empty() const noexcept; 检测unordered_map是否为空 size_type size() const noexcept; 获取unordered_map的有效元素个数
unordered_map的迭代器
函数说明功能介绍begin返回unordered_map第一个元素的迭代器end返回unordered_map最后一个元素下一个位置的迭代器rbegin返回unordered_map第一个元素的const迭代器rend返回unordered_map最后一个元素下一个位置的const迭代器
unordered_map的元素访问
函数说明功能介绍operator[]返回与key对应的value没有一个默认值
【注意】该函数实际上调用了哈希桶的插入操作用参数key与value构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回value插入失败说明key已经在哈希桶值将key对应的value返回。
unordered_map的查询
函数说明功能介绍 iterator find ( const key_type k ); 返回key在哈希桶中的位置 size_type count ( const key_type k ) const; 返回哈希桶中关键值为key的键值对的个数
【注意】unordered_map中的key是不能重复的因此count函数的返回值最大为1
unordered_map的修改操作
函数说明功能介绍insert向容器中插入键值对erase删除容器中的键值对clear清空容器中有效元素的个数swap交换俩个容器中的元素
unordered_map桶操作
函数说明功能介绍 bucket_count 返回哈希桶中的桶的总数 bucket_size 返回n号桶中有效元素的个数 bucket 返回元素key所在的桶号
哈希底层结构
哈希概念 哈希散列存储的值跟存储位置建立出一个对应关系。
顺序容器以及平衡树中元素关键码与其存储位置之间没有对应关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(logN)搜索的效率取决于搜索过程中的元素的比较次数。
下面介绍一种方法哈希散列方法哈希方法中使用的转换函数称为哈希散列函数构造出来的结构称为哈希表Hash Table或者散列表。
该方法可以不经过任何比较一次直接从表中得到想要的元素通过某种函数使元素的存储位置与其关键码之间能够建立一一映射的关系在查找的时候通过该函数可以很快找到该元素。
插入元素根据待插入的关键码以此函数计算出该元素的存储位置并按照此位置进行存放。
搜索元素对元素的关键码进行同样的计算把求得的函数值当作元素的存储位置在结构中按照此位置取元素比较若关键码相等则搜索成功。
哈希设计介绍
哈希函数设计原则
哈希函数的定义域必须包括存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中。
常见哈希函数
1.直接定址法
取关键字的某个线性函数为散列地址Hash(key) A*key B
【优点】简单均匀
【缺点】需要事先知道关键字的分布情况
【使用场景】适合查找范围小数据集中的情况。
2.除留余数法
设散列表中允许的地址数为m取一个不大于m但是最接近或者等于m的质数p作为除数按照哈希函数Hash(key)key%p(pm)将关键码转换成哈希地址。 哈希冲突
哈希冲突 不同关键字通过相同哈希函数计算出相同的哈希地址这种现象是哈希冲突也称为哈希碰撞。
解决哈希冲突的俩种常见的方法是闭散列和开散列
闭散列
闭散列也叫开放地址法当发生哈希冲突的时候如果哈希表未被填满说明了在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个”空位置中去。
1.线性探测
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置。
插入方式
通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。
删除方式
采用闭散列处理哈希冲突的时候不能随便物理删除哈希表中已经存在的元素这样可能会导致影响其他元素的搜索。可以采用标记的伪删除的方式来删除一个元素 enum STATE{EXIST,EMPTY,DELETE}; 哈希表的扩容
如果使用开放地址法可以利用载荷因子
散列表的载荷因子a 填入表中的元素个数 / 散列表的长度
a是散列表装满程度的标志因子由于散列表的长度是定值a与“填入表中的元素个数”成正比。
负载因子越大冲突概率越大空间利用率更高负载因子越小冲突概率越小空间利用率更低空间浪费越多
哈希表不能满了再扩容控制负载因子再0.7-0.8之间。如果超过0.8查表时的CPU缓存不命中按照指数曲线上升。
在扩容之后映射关系需要改变重新映射这样也会导致哈希冲突的变化。
线性探测的实现
#includeiostream
#includestringusing namespace std;templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct DefaultHashFuncstring
{size_t operator()(const string str){// BKDRsize_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace open_address
{enum STATE{EXIST,EMPTY,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;STATE _state EMPTY;};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}// 扩容//if ((double)_n / (double)_table.size() 0.7)if (_n * 10 / _table.size() 7){size_t newSize _table.size() * 2;// 遍历旧表重新映射到新表HashTableK, V, HashFunc newHT;newHT._table.resize(newSize);// 遍历旧表的数据插入到新表即可for (size_t i 0; i _table.size(); i){if (_table[i]._state EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}// 线性探测HashFunc hf;size_t hashi hf(kv.first) % _table.size();while (_table[hashi]._state EXIST){hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;}HashDataconst K, V* Find(const K key){// 线性探测HashFunc hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key){return (HashDataconst K, V*) _table[hashi];}hashi;hashi % _table.size();}return nullptr;}// 按需编译bool Erase(const K key){HashDataconst K, V* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}return false;}private:vectorHashDataK, V _table;size_t _n 0; // 存储有效数据的个数};
}
【线性探测的优点】实现简单
【线性探测的缺点】一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了棵利用的空位置使得寻找某关键码的位置需要多次比较导致搜索效率低下。
2.二次探测
线性探测的缺点是产生冲突之后会将数据堆积在一起这与其找下一个空位置有关系查找数据需要逐个进行查找可以使用二次探测解决问题。
二次探测
找下一个空位置的方法 hashi key % n hashi i ^2(i为移动的位置) i0 【研究表明】当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任 何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。
闭散列最大的缺陷就是空间利用率低这也是哈希的缺陷。
开散列
开散列开散列法又称为链地址法开链法首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一个子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。
【说明】开散列使用的是哈希桶如果不扩容就会不断插入某些桶就会越来越长效率得不到保障负载因子适当放大一般负载因子控制到1平均下来每一个桶一个数据。
开散列的实现
// 泛型编程不是针对某种具体类型针对广泛的类型(两种及以上) -- 模板
namespace hash_bucket
{templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};// 前置声明templateclass K, class T, class KeyOfT, class HashFuncclass HashTable;templateclass K, class T, class KeyOfT, class HashFuncstruct HTIterator{typedef HashNodeT Node;typedef HTIteratorK, T, KeyOfT, HashFunc Self;Node* _node;HashTableK, T, KeyOfT, HashFunc* _pht;HTIterator(Node* node, HashTableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_next){// 当前桶还没完_node _node-_next;}else{KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_node-_data)) % _pht-_table.size();// 从下一个位置查找查找下一个不为空的桶hashi;while (hashi _pht-_table.size()){if (_pht-_table[hashi]){_node _pht-_table[hashi];return *this;}else{hashi;}}_node nullptr;}return *this;}bool operator!(const Self s){return _node ! s._node;}};// set - hash_bucket::HashTableK, K _ht;// map - hash_bucket::HashTableK, pairK, V _ht;templateclass K, class T, class KeyOfT, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeT Node;// 友元声明templateclass K, class T, class KeyOfT, class HashFuncfriend struct HTIterator;public:typedef HTIteratorK, T, KeyOfT, HashFunc iterator;iterator begin(){// 找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];if (cur){return iterator(cur, this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}HashTable(){_table.resize(10, nullptr);}~HashTable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}bool Insert(const T data){KeyOfT kot;if (Find(kot(data))){return false;}HashFunc hf;// 负载因子到1就扩容if (_n _table.size()){size_t newSize _table.size() * 2;vectorNode* newTable;newTable.resize(newSize, nullptr);// 遍历旧表顺手牵羊把节点牵下来挂到新表for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 头插到新表size_t hashi hf(kot(cur-_data)) % newSize;cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kot(data)) % _table.size();// 头插Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}Node* Find(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}--_n;delete cur;return true;}prev cur;cur cur-_next;}return false;}void Print(){for (size_t i 0; i _table.size(); i){printf([%d]-, i);Node* cur _table[i];while (cur){cout cur-_kv.first : cur-_kv.second -;cur cur-_next;}printf(NULL\n);}cout endl;}private:vectorNode* _table; // 指针数组size_t _n 0; // 存储了多少个有效数据};
}
开散列与闭散列的比较
优先使用开散链的方法。
虽然链地址的方法处理溢出需要增设链接指针但是开地址法必须保持大量的空闲空间以确保搜索效率而表项所占的空间比指针大所以使用链地址法比开地址法节省空间。
