2020最有效的网络推广方式,东莞seo优化排名,个人申请注册公司需要多少钱,html5手机网站整套模板一.Unordered_map,Unordered_set介绍
在之前我们已经介绍过set,map,multiset等等关联式容器#xff0c;它们的底层是红黑树进行模拟实现的#xff0c;在查询时效率可达到 l o g 2 N log_2 N log2N#xff0c;即最差情况下需要比较红黑树的高度次#xff0c;当树中的节点…一.Unordered_map,Unordered_set介绍
在之前我们已经介绍过set,map,multiset等等关联式容器它们的底层是红黑树进行模拟实现的在查询时效率可达到 l o g 2 N log_2 N log2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到 因此在C11中又引入了unordered系列的关联式容器它们的用法和map,set非常类似不过底层实现上有所不同后者是用红黑树模拟实现的而前者则是用一种名叫哈希的数据结构
二.简单性能对比
我们分别创建set对象和unordered_set对象然后生成一大堆随机数进行插入通过时间上实现find,erase,insert等操作进行对比来简单对比两者性能上的差别
#include unordered_map
#include unordered_set
#include time.h
#include set
#include mapusing namespace std;
int main()
{const size_t N 200000;unordered_setint s1;setint s2;vectorint v1;v1.reserve(N);srand(time(0));for (size_t i 0; i N; i){//v1.push_back(rand());v1.push_back(rand()i);//v1.push_back(i);}//插入时间对比size_t begin1 clock();for (auto e : v1){s2.insert(e);}size_t end1 clock();cout set insert: end1 - begin1 endl;size_t begin2 clock();for (auto e : v1){s1.insert(e);}size_t end2 clock();cout unordered_set insert: end2 - begin2 endl;//寻找时间对比size_t begin3 clock();for (auto e : v1){s2.find(e);}size_t end3 clock();cout set find: end3 - begin3 endl;size_t begin4 clock();for (auto e : v1){s2.find(e);}size_t end4 clock();cout unordered_set find: end4 - begin4 endl endl;//删除时间对比size_t begin5 clock();for (auto e : v1){s2.erase(e);}size_t end5 clock();cout set erase: end5 - begin5 endl;size_t begin6 clock();for (auto e : v1){s1.erase(e);}size_t end6 clock();cout unordered_set erase: end6 - begin6 endl endl;return 0;
}可以看到在insert,erase等操作上哈希实现的unordered系列具有一定的显著优势 在cplusplus网站对unordered系列的介绍也直接指出来它的优势所在以及两者的不同这里只简单列举unordered_map为例 前两段指出了unordered_map也是关联式容器(associative containers)支持键值对key和mapped value的类型可以不同 第三段指出它与map系列的不同它的底层实现是一种叫哈希桶(buckets)的数据结构 第四五段也指出了该系列的优势和区别unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭 代方面效率较低同时map我们知道它是支持双向迭代器而unordered_map只支持单向迭代器(forward iterators)
三.哈希概念介绍
2.1哈希概念
对于平衡树来说元素关键字与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。 查找的效率即为平衡树中树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数 那我们是否能建立一种这样的结构将元素的关键字和其存储位置之间建立映射关系从而大大提高查找的效率 就像我们的宿舍号在开学前每位学生都会按照一定的规则(比如说按照学号进行分宿舍按成绩进行分宿舍)分到相应的宿舍 假如班级管理委员要找某位同学他并不会按照顺序一间间宿舍往下找假如一层有十多个宿舍那效率实在太慢了正确的做法就是根据分配的规则比如说按照学号进行分宿舍然后根据学号直接找宿舍名单中对应宿舍即可. 将上述过程中的关键字抽离出来 一定的规则我们称之为哈希函数 宿舍名单我们称之为哈希表HashTable 从上述例子也可以看出哈希函数并不是唯一的 比如说数据集合{176459} 我们将哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小. 我们找4只需要直接去哈希表中的4寻找即可直接一步到位它的关键思想和数组下标映射有点类似.
2.2哈希冲突
虽然理论上我们已经基本建立所谓的哈希表但是实际运用上还有一些问题需要解决 假如我们对上面的例子中的表再插入一个14呢它应该放置在哪个位置 我们把不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞 数学上解释 对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i ! j)有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)我们称之为发生了哈希冲突
2.3哈希函数
引起哈希冲突的其中一个原因可能是哈希函数设计的不够合理 因此哈希函数虽然有很多种类型但是也需要符合一定的设计原则 哈希函数设计原则 1.哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间 2.哈希函数计算出来的地址能均匀分布在整个空间中 3.哈希函数应该比较简单 常见的哈希函数如下 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)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况
注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突
2.4哈希冲突解决
既然出现相应的问题我们就要找相应的办法解决 解决哈希冲突两种常见的方法是闭散列和开散列
2.4.1闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去. 那如何理解闭散列中闭的含义呢 因为哈希表的原始空间是固定大小的比如说我们上述所举的例子对应的哈希表本质是一个vector大小是10个字节后面即便再插入新元素需要打到某种条件才会改变哈希表的大小 那闭散列如何解决哈希冲突的问题 抓住闭散列的定义当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去. 因此假如插入新元素14和4发生冲突就从哈希表中找一个新的位置比如下标为8下标为0的位置等等这些位置都没有元素放置可以用来放置14从而解决哈希冲突的问题 但是怎么找空位置也是有讲究的 常用的探测方式主要是线性探测和二次探测 线性探测 从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止. 用大白话讲就是一个一个从前往后找空位置 比如插入144发生冲突往后找看下标为5的位置有没有放置新元素有于是继续往后找直到到下标为8的位置发现为空所以放置对应的新元素14 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 H i H_i Hi ( H 0 H_0 H0 i 2 i^2 i2 )% m, 或者 H i H_i Hi ( H 0 H_0 H0 - i 2 i^2 i2 )% m。其中i 1,2,3… H 0 H_0 H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小 大白话来说就是跳着找第一次找下标为冲突下标1的位置如果冲突找冲突下标2的位置以此类推 当然还有很多探测方式比如左右交替找等等这里不再过多介绍
2.4.2 负载因子
前面我们提到过哈希表在一定条件下需要扩容那这个一定条件是什么呢 有人会说哈希表全部已经装满了就可以考虑扩容 这固然是一种实现方法但在现实中往往采取的是另一种策略 我们定义 负载因子 α 插入表中元素个数 散列表长度 \alpha \frac{插入表中元素个数}{散列表长度} α散列表长度插入表中元素个数 表中元素个数在哈希表中占据的相对比重越大就越可能发生哈希冲突因此负载因子在等于0.7至0.8的时候就要及时考虑哈希表的扩容问题否则发生哈希冲突的概率将会急剧增大
2.4.3闭散列代码实现
哈希表的本质是一个自定义类型里面包含两个成员变量一个是vector另一个是哈希表大小n(当然也可以采取函数指针的方式不过c本身就实现了vector明显用vector更香) 插入的每一个HashData也不是简单的数字同样也是一个自定义类型里面包含的是pair键值对和对应的元素状态 至于为什么HashData(哈希表中每个对应的元素)的成员变量要这样设计其实背后也蕴含深意 1.插入哈希表中的元素类型并不固定可能是内置类型int或者是自定义类型string再加上需要映射相应的位置所以采取模板pair的方式作为其中一个成员变量是合情合理的 2.那为什么要加入相应的元素状态呢 这主要是为了实现删除和扩容的方便 删除对应的元素只需要将对应的元素状态设为空即可假如用一个不存在的值覆盖反而还不方便 同样的扩容需要重新创建一个新大小n的vector并将旧的原有元素重新映射到新的vector中如何快速判断对应位置是否存在元素呢如果每个元素本身就有一个状态EXIST(存在)or Empty(空)那就能迅速判断是否要将该旧元素映射到新的哈希表中. 具体代码实现如下
namespace OpenAddress {//设三个状态enum State{EMPTY,EXIST,DELETE};template class K,class Vstruct HashData {pairK, V _kv;//初始状态都设为空State _state EMPTY;};template class K,class Vclass HashTable {public://insertbool insert(const pairK, V kv){//如果哈希表中本身已经存在该元素则直接返回falseif (Find(kv.first))return false;//考虑扩容问题表长为0或负载因子超过0.7都要考虑扩容并重新映射if (_tables.size() 0 || _n * 10 / _tables.size() 7){size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK,V new_hash_table;//调整新哈希表size为newsizenew_hash_table._tables.resize(newsize);//重新映射for (auto data : _tables){//假设元素状态为存在则移动到新表if (data._state EXIST){new_hash_table.insert(data._kv);}}_tables.swap(new_hash_table._tables);}//实际的插入代码size_t hashi kv.first % _tables.size();size_t i 1;size_t index hashi;//找到对应插入的位置while (_tables[index]._state EXIST){index hashi i;index % _tables.size();i;}_tables[index]._kv kv;_tables[index]._state EXIST;_n;return true;}//FindHashDataK,V* Find(const K key){//假如哈希表本身大小就为0则直接返回空即可if (_tables.size() 0)return nullptr;//计算应该找的下标 键值%表长size_t hashi key % _tables.size();//线性探测---从前往后找对应元素直到遇到空size_t i 1;size_t index hashi;while (_tables[index]._state ! EMPTY){//如果状态不为删除为存在且键值相等表明相同说明if (_tables[index]._state EXIST _tables[index]._kv.first key){return _tables[index];}//当前位置没找到调整下标位置index hashi i;//下标不能越界及时调整回来index % _tables.size();i;//如果已经遍历了一圈说明全都为空或者删除则直接break即可if (index hashi){break;}}return nullptr;}//Erasebool Erase(const K key){HashDataK, V* ret Find(key);//找到对应的元素状态设为删除即可if (ret){ret-_state DELETE;//调整容量--_n;return true;}else{return false;}}private://哈希表本质是一个vector,里面存放的都是HashData自定义类型数据vector HashDataK,V _tables;//存储的数据个数size_t _n 0;//HashData* tables;//size_t _size;//size_t _capacity;};
}2.4.4开散列
闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷 于是有人想到用开散列的方式来实现哈希表 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶(Bucket)各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中
从上面的定义我们就可以看出来开散列中的开是什么意思 虽然也需要考虑扩容问题但是开散列有一个很显著的特征它处理哈希冲突的方式简单又粗暴直接挂到相应的桶即可不需要再进行诸如线性探测二次探测等等的操作
2.4.4.1 开散列增容
桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容 那该条件怎么确认呢 开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容
2.4.4.2 映射方案
还有一些细节需要思考 第一个就是映射元素的问题在闭散列中我们故意忽略了该问题实际上实现哈希表是无法躲开的 比如说下面的代码假如是字符串我们是无法挂到相应的桶的需要人为将key转为整型(下面例子的key对应的就是string类型) //哈希表不能映射字符串只能映射整型void TestHashTable3(){//HashTablestring, string, HashStr ht;HashTablestring, string ht;ht.insert(make_pair(sort,排序));ht.insert(make_pair(left, 左边));ht.insert(make_pair(right, 右边));ht.insert(make_pair(, 右边));}所以我们设计时需要加入相应的模板让用户自己传递相应的哈希函数实现使得我们的哈希表能够适应不同类型的数据 具体如何将字符串映射为相应的整型可以参照下面这篇文章 链接: 字符串Hash函数 在模拟实现开散列时我们采取的是BKDR算法
template class Kstruct HashFunc {size_t operator()(const K key){return key;}};//特化template struct HashFuncstring{ //BKDRsize_t operator()(const string s){size_t hashi 0;for (auto ch : s){hashi hashi * 131 ch;}return hashi;}};还有另外一个细节我们扩容时采取的策略是扩2倍的方式这当然没有问题不过出于某种原因(效率上),现代大多采取开辟邻近相应的最大素数的方式 所以我们下面的模拟实现开散列也是直接仿照stl库中的方式直接给出对应的素数大小空间一旦超过元素和旧表大小相同则开辟邻近最大素数大小的新表
size_t GetNextPrime(size_t prime){// SGIstatic const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i 0;for (; i __stl_num_primes; i){if (__stl_prime_list[i] prime)return __stl_prime_list[i];}return __stl_prime_list[i];}2.4.5 开散列代码实现
namespace HashBucket {templateclass K,class V //其实就类似于链表中的节点struct HashNode {HashNodeK, V* _next;pairK, V _kv;//构造函数HashNode(const pairK,V kv):_next(nullptr),_kv(kv){}};template class Kstruct HashFunc {size_t operator()(const K key){return key;}};//特化由于整型和字符串作为Key值最为常用整型Hash函数直接作为//默认模板而字符串Hash函数直接特化template struct HashFuncstring{ //BKDRsize_t operator()(const string s){size_t hashi 0;for (auto ch : s){hashi hashi * 131 ch;}return hashi;}};template class K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public://析构函数~HashTable(){for (auto cur : _tables){while (cur){Node* next cur-_next;delete cur;cur next;}cur nullptr;}}//Find函数实现Node* Find(const K key){//如果哈希表本身为空if (_tables.size() 0){return nullptr;}Hash hash;//找到对应的数组下标size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];//遍历链表while (cur){if (cur-_kv.first key)return cur;cur cur-_next;}return nullptr;}//Erase函数实现bool Erase(const K key){//如果哈希表本身为空if (_tables.size() 0){return false;}//先确定对应的下标size_t hashi key % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){ //假设找到对应要删除的元素if (cur-_kv.first key){//假设就为头节点直接调整头节点if (prev nullptr){_tables[hashi] cur-_next;}//不为头节点,让prev指向cur的下一个节点即可else{prev-_next cur-_next;}//删除当前节点delete cur;return true;}//没有找到对应要删除的元素cur和prev往后移动else{prev cur;cur cur-_next;}}return false;}//insert函数实现bool insert(const pairK, V kv){//如果找到对应相同的元素则直接返回falseif (Find(kv.first))return false;Hash hash;//哈希表长度为0或负载因子为1时扩容尽量让每条链不超过三个节点if (_n _tables.size()){//size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;size_t newsize GetNextPrime(_tables.size());//与闭散列不同哈希桶扩容释放旧哈希桶不断析构代价还是有点大的//所以我们采取直接将节点挂到新哈希桶的方法vector Node* newtables(newsize, nullptr);for (auto cur : _tables){//只要cur不为空,则将链表挂到新哈希桶上while (cur){Node* next cur-_next;//找到需要挂的新位置size_t hashi hash(cur-_kv.first) % newtables.size();//头插挂到新哈希桶cur-_next newtables[hashi];newtables[hashi] cur;//向后一个节点移动cur next;}}_tables.swap(newtables);}//正式插入代码//找到需要挂的新位置size_t hashi hash(kv.first) % _tables.size();//建新节点Node* newnode new Node(kv);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}size_t GetNextPrime(size_t prime){// SGIstatic const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i 0;for (; i __stl_num_primes; i){if (__stl_prime_list[i] prime)return __stl_prime_list[i];}return __stl_prime_list[i];}size_t MaxSizeBucket(){size_t max 0;//遍历每一个哈希桶for (size_t i 0;i _tables.size();i){auto cur _tables[i];size_t size 0;//一直到空指针为止while (cur){size;cur cur-_next;}printf([%d] -- %d\n, i, size);//如果比最大值要大则更新最大桶值if (size max){max size;}}return max;}private://自定义类型的指针数组vectorNode* _tables;//数组大小(有效数据个数)size_t _n 0;};}
