如何做房产网站,制作网页站点的具体流程案例,海淀深圳网站建设公司,炎陵网站建设unordered系列关联式容器
在C98中#xff0c;STL提供了底层为红黑树结构的一系列关联式容器#xff0c;在查询时效率可达到log_2 N#xff0c;即最差情况下需要比较红黑树的高度次#xff0c;当树中的节点非常多时#xff0c;查询效率也不理想。最好 的查询是#xff0c…unordered系列关联式容器
在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到log_2 N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好 的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是 其底层结构不同。因为unordered_set与unordered_map使用方式类似我们着重见介绍unordered_mapunordered_set见文档。 unordered_map(文档)
unordered_map是存储key, value键值对的关联式容器其允许通过keys快速的索引到与其对应的value。在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。unordered_map实现了直接访问操作符(operator[])它允许使用key作为参数直接访value。unordered_map是单向迭代器
接口
unordered_map容量相关
bool empty()const (检测unordered_map是否为空)size_t size()const (获取unordered_map的有效元素个数)
unordered_map的元素访问
operator[] (返回与key对应的value没有一个默认值)注意该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中将key对应的value返回。
unordered_map的查询
iterator find(const K key) (返回key在哈希桶中的位置)size_t count(const K key) (返回哈希桶中关键码为key的键值对的个数)
unordered_map的修改操作
insert (向容器中插入键值对)erase (删除容器中的键值对)void clear() (清空容器中有效元素个数)void swap(unordered_map) (交换两个容器中的元素)
unordered_map的桶操作
size_t bucket_count()const (返回哈希桶中桶的总个数)size_t bucket_size(size_t n)const (返回n号桶中有效元素的总个数)size_t bucket(const K key) (返回元素key所在的桶号) 使用
#include iostream
using namespace std;
#include map
#include set
#include unordered_map
#include unordered_set
void test_unordered_set()
{unordered_setint us;us.insert(4);us.insert(2);us.insert(1);us.insert(5);us.insert(6);/*us.insert(6);us.insert(6);*///可以去重 不能排序unordered_setint::iterator it us.begin();while (it ! us.end()){cout *it ;it; }cout endl;
}
void test_op()
{unordered_setint us;setint s;const int n 1000000;vectorint v;v.reserve(n);srand(time(0));for (size_t i 0; i n; i){v.push_back(rand());} size_t begin1 clock();for (size_t i 0; i n; i){us.insert(v[i]);}size_t end1clock();size_t begin2 clock();for (size_t i 0; i n; i){s.insert(v[i]);}size_t end2 clock();size_t begin3 clock();for (size_t i 0; i n; i){us.find(v[i]);}size_t end3 clock();size_t begin4 clock();for (size_t i 0; i n; i){s.find(v[i]);}size_t end4 clock();size_t begin5 clock();for (size_t i 0; i n; i){us.erase(v[i]);}size_t end5 clock();size_t begin6 clock();for (size_t i 0; i n; i){s.erase(v[i]);}size_t end6 clock();cout set:(insert) end2 - begin2 endl;cout unordered_set:(insert) end1 - begin1 endl;cout set:(find) end4 - begin4 endl;cout unordered_set:(find) end3 - begin3 endl;cout set:(erase) end6 - begin6 endl;cout unordered_set:(erase) end5 - begin5 endl;
}
从运行结果可以看出unordered_set容器增删查的效率比set快
相关OJ题
重复n次的元素两个数组的交集I两个数组的交集II存在重复元素两句话中不常见的单词 底层结构
unordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。 哈希是一种映射的对应关系将存储的数据根存储的位置使用哈希函数建立出的映射关系方便我们进行查找。在查找字符串中只出现过一次的字符中就可以创建一个256的int数组去统计次数因为字符总共只有256种这里就建立了字符(char)与字符的值(int)的映射关系直接定址法映射只跟关键字直接相关或者间接相关。 其次计数排序也是统计次数建立类似的映射进行排序。 1259100000088888823存起来方便查找,怎么存?(不使用搜索树) 如果每个值直接进行映射那么我们要创建一个100w大小的数组空间浪费十分严重。基于这个原因哈希引申出一些映射的方式进行补救。
除留余数法(最常用) 不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 现在我们要存11就会发生冲突了这种冲突叫做哈希冲突。(不同的值映射到了相同的位置)哈希通过映射关系进行查找效率非常高但是哈希最大的问题就是如何解决哈希冲突这里就引入了很多种方法来解决哈希冲突。
哈希冲突解决
解决哈希冲突两种常见的方法是闭散列和开散列 闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢
线性探测(从发生冲突的位置开始依次向后探测直到找到下一个空位置为止) key % 表大小 i (i 0,1,2,3,4,...)二次探测(按2次方往后找空位置) key % 表大小 i^2 (i 0,1,2,3,...) 线性探测
插入
通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素
删除
采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素,可能会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
enum State{EMPTY,EXITS,DELETE}; 线性探测的实现
#include iostream
#include vector
using namespace std;
enum State
{EMPTY,EXITS,DELETE
};
templateclass T
struct HashData
{T _data;State _stateEMPTY;
};templateclass K
struct SetOfT
{const K operator()(const K key){return key;}
};
//unordered_setK -HashTableK,K
//unordered_mapK,V -HashTableK,pairK,V
templateclass K,class T,typename KOfT
class HashTable
{
public:bool Insert(const T d){KOfT koft;/*if (Find(koft(d)))return false;*///闭散列哈希表不能满了再增容//因为如果哈希表快满了的时候插入数据冲突的概率很大效率会很低//快接近满的时候就增容//因此提出负载因子的概念表中数据个数比上表的大小//一般情况下负载因子越小冲突的概率特低效率越高//但是控制的太小会导致大量的空间浪费以空间换时间/*if (_tables.size()0||_num * 10 / _tables.size() 7){*/// //第一次会出现除0的问题// //1.开两倍大小的新表// //2.遍历旧表的数据重新计算表中的位置// //3.释放旧表// size_t newsize _tables.size() 0 ? 10 : 2 * _tables.size();// vectorHashDataT newtables;// newtables.resize(newsize);// for (size_t i 0; i _tables.size(); i)// {// if (_tables[i]._state EXITS)// {// //计算新表中的位置并处理冲突// int index koft(_tables[i]._data) % newtables.size();// while (newtables[index]._state EXITS)// {// index;// if (index newtables.size())// index 0;// }// newtables[index] _tables[i];// }// }// _tables.swap(newtables);//}if (_tables.size() 0 || _num * 10 / _tables.size() 7){HashTableK, T, KOfT newht;size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;newht._tables.resize(newsize);for (auto data : _tables){if (data._state EXITS){newht.Insert(data._data);}}_tables.swap(newht._tables);}size_t index koft(d) % _tables.size();while (_tables[index]._state EXITS){index;if (index _tables.size())index 0;}_tables[index]._data d;_tables[index]._state EXITS;_num;return true;}HashDataT* Find(const K key){KOfT koft;size_t index key % _tables.size();while (_tables[index]._state ! EMPTY){if (koft(_tables[index]._data) key){if (_tables[index]._state EXITS){return _tables[index];}else if (_tables[index]._state DELETE)return nullptr;}index;if (index _tables.size())index 0;}return nullptr;}bool Erase(const K key){HashDataT* ret Find(key);if (ret){ret-_state DELETE;--_num;return true;}else{return false;}}
private:vectorHashDataT _tables;size_t _num0; //有效数据的个数
};
void test_HashTable()
{HashTableint,int, SetOfTint ht;ht.Insert(4);ht.Insert(14);ht.Insert(24);ht.Insert(5);ht.Insert(15);ht.Insert(25);ht.Insert(6);ht.Insert(16);
}
线性探测的问题 线性探测的思路就是如果我的位置被占用了我就挨着往后去占别人的位置可能会导致一片一片的冲突洪水效应。
线性探测优点实现非常简单线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢 二次探测 开散列
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中。
开散列中每个桶中放的都是发生哈希冲突的元素。 开散列实现
templateclass T
struct HashNode
{HashNode(const T data):_next(nullptr),_data(data){}T _data;HashNodeT* _next;
};templateclass K
struct _Hash
{
public:const K operator()(const K key){return key;}
};//特化 HashTablestring,string,SetOfTstring ht;
template
struct _Hashstring
{size_t operator()(string key){size_t hash 0;for (size_t i 0; i key.size(); i){hash * 131;hash key[i];}return hash;}
};
//HashTablestring,string,SetOfTstring,_HashString ht;
/*struct _HashString
{
public:size_t operator()(string key){size_t hash 0;for (size_t i 0; i key.size(); i){hash * 131;hash key[i];}return hash;}
};*/
templateclass K,class T,class KOFT,class Hash_HashK
class HashTable
{typedef HashNodeT Node;
public:~HashTable(){Clear();}void Clear(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* _next cur-_next;delete cur;cur _next;}}}const size_t HashFunc(const K key){Hash hash;return hash(key);}bool Insert(const T data){KOFT koft;//增容 负载因子if (_num _tables.size()){size_t newsize (_tables.size() 0 ? 10 : 2 * _num);vectorNode* newtables;newtables.resize(newsize);for (int i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){size_t index HashFunc(koft(cur-_data)) % newsize;Node* next cur-_next;cur-_next newtables[index];newtables[index] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtables);}//计算在表中的映射位置size_t index HashFunc(koft(data))%_tables.size();Node* cur _tables[index];//查找这个值在不在表中while (cur){if (koft(cur-_data) koft(data)){return false;}else{//头插到表中cur cur-_next;}}Node* ret new Node(data);ret-_next _tables[index];_tables[index] ret;_num;return true;}Node* Find(const K key){KOFT koft;size_t index HashFunc(key) % _tables.size();Node* cur _tables[index];while (cur){if (koft(cur-_data) key){return cur;}else{cur cur-_next;}}return nullptr;}bool Erase(const K key){KOFT koft;size_t index HashFunc(key) % _tables.size();Node* cur _tables[index];Node* prev nullptr;while (cur){if (koft(cur-_data) key){if (prev nullptr){_tables[index] cur-_next;}else{prev-_next cur-_next;}delete cur;_num--;return true;}else{prev cur; cur cur-_next;}}return false;}
private:vectorNode* _tables;size_t _num0; 假设总有一些桶挂的数据很多冲突很厉害怎么解决
针对单个桶一个桶链的长度超过一定值就将挂链表改为挂红黑树。(Java HashMap就是当桶长度超过8就改成挂红黑树)针对整体控制负载因子
仿函数Hash将对应的key转成可以取余的整型默认的仿函数直接返回key因为有些类型的key直接就可以取余如果是其他自定义类型我们就自己构造一个哈希函数作为仿函数传入Hash模板中。(常见字符串哈希算法) 开散列与闭散列比较 应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。 unordered_set与unordered_map的模拟实现
哈希表的改造
模板参数列表的改造增加迭代器操作增加通过key获取value操作
#pragma once
#include iostream
#include vector
#include string
using namespace std;
namespace wxy
{templateclass Tstruct HashNode{HashNode(const T data):_next(nullptr),_data(data){}T _data;HashNodeT* _next;};//前置声明 两者如果相互依赖就需要对其中一个进行前置声明templateclass K, class T, class KOFT, class Hashclass HashTable;templateclass Kstruct _Hash{size_t operator()(const K key){return key;}};// 特化templatestruct _Hashstring{// int insert // 字符串转成对应一个整形值因为整形才能取模算映射位置// 期望-字符串不同转出的整形值尽量不同// abcd bcad// abbb abcasize_t operator()(const string s){// BKDR Hashsize_t value 0;for (auto ch : s){value ch;value * 131;}return value;}};templateclass K, class T, class KOFT, class Hashstruct HTIterator{public:typedef HTIteratorK, T, KOFT, Hash Self;typedef HashNodeT Node;typedef HashTableK, T, KOFT, Hash HT; //这里会往前找 找不到HashTable? 怎么办 Node* _node;const HT* _pht;HTIterator(Node* node, HT* pht):_node(node), _pht(pht){}T operator*(){return _node-_data;}T* operator-(){return (_node-_data);}bool operator!(const Self s){return (_node ! s._node);}Self operator(){if (_node-_next){//当前桶还有数据走到下一个节点_node _node-_next;}else{KOFT koft;Hash hash;//如果一个桶走完了找到下一个桶继续遍历size_t index hash(koft(_node-_data))%_pht-_tables.size();index;/*for (; index _pht-_tables.size(); index){Node* cur _pht-_tables[index];if (cur){_node cur;return *this;}}*/while (index _pht-_tables.size()){_node _pht-_tables[index];if (_node)break;elseindex;}if(index_pht-_tables.size())_node nullptr;}return *this;}};templateclass K, class T, class KOFT, class Hashclass HashTable {public://友元声明 templateclass K, class T, class KeyOfT, class Hashfriend struct HTIterator;typedef HTIteratorK, T, KOFT, Hash Iterator;typedef HashNodeT Node;size_t HashFunc(K key){Hash hash;return hash(key);}Iterator begin(){if (_num 0)return end();for (size_t i 0; i _tables.size(); i){if (_tables[i]){return Iterator(_tables[i],this);}}return end();}Iterator end(){return Iterator(nullptr,this);}~HashTable(){Clear();}void Clear(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* _next cur-_next;delete cur;cur _next;}}}pairIterator,bool Insert(const T data){KOFT koft;Hash hash;//增容 负载因子if (_num _tables.size()){size_t newsize (_tables.size() 0 ? 10 : 2 * _num);vectorNode* newtables;newtables.resize(newsize);for (int i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){size_t index HashFunc(koft(cur-_data)) % newsize;Node* next cur-_next;cur-_next newtables[index];newtables[index] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtables);}//计算在表中的映射位置size_t index HashFunc(koft(data))%_tables.size();Node* cur _tables[index];//查找这个值在不在表中while (cur){if (koft(cur-_data) koft(data)){return make_pair(Iterator(cur,this),false);}else{//头插到表中cur cur-_next;}}Node* ret new Node(data);ret-_next _tables[index];_tables[index] ret;_num;return make_pair(Iterator(ret,this), true);}Iterator Find(const K key){KOFT koft;size_t index HashFunc(koft(key)) % _tables.size();Node* cur _tables[index];while (cur){if (koft(cur-_data) key){return Iterator(cur,this);}else{cur cur-_next;}}return end();}bool Erase(const K key){KOFT koft;size_t index HashFunc(koft(key)) % _tables.size();Node* cur _tables[index];Node* prev nullptr;while (cur){if (koft(cur-_data) key){if (prev nullptr){_tables[index] cur-_next;}else{prev-_next cur-_next;}delete cur;_num--;return true;}else{prev cur;cur cur-_next;}}return false;}private:vectorNode* _tables;size_t _num 0;};
} unordered_set的模拟实现
namespace wxy {templateclass K,class Hash_HashKclass unordered_set{public:struct SetOfT{const K operator()(const K key){return key;}};typedef typename HashTableK,K,SetOfT,Hash::Iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K key){return _ht.Insert(key);}private:HashTableK,K,SetOfT,Hash _ht;};void test_unorderedset(){unordered_setint s;s.insert(1);s.insert(5);s.insert(4);s.insert(2);unordered_setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;}
} unordered_map的模拟实现
namespace wxy {templateclass K, class V,class Hash_HashKclass unordered_map{struct MapOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename HashTableK,pairK, V,MapOfT, Hash::Iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator,bool insert(const pairK,V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}iterator Find(const K key){return _ht.Find(key);}bool Erase(const K key){return _ht.Erase(key);}private:wxy::HashTableK, pairK, V, MapOfT,Hash _ht;};void test_unorderedmap(){unordered_mapstring, string dict;dict.insert({ sort, 排序 });dict.insert({ sort, 排序 });dict.insert({ left, 左边 });dict.insert({ right, 右边 });dict[left] 左边剩余;dict[insert] 插入;dict[string];for (auto kv : dict){cout kv.first : kv.second endl;}cout endl;}
}
