joomla可以做预订类网站吗,什么网站可以在线做考教师岗位的题,做网站成本,设计本推荐前言
学完了二叉树#xff0c;我们要学当前阶段数据结构的最后一个内容了#xff1a;哈希#xff01;#xff01;
引入
先来介绍两个用哈希封装的两个容器#xff1a;unordered_map unordered_set
与map和set的不同#xff1a;
map/set是双向迭代器#xff0c;而另…前言
学完了二叉树我们要学当前阶段数据结构的最后一个内容了哈希
引入
先来介绍两个用哈希封装的两个容器unordered_map unordered_set
与map和set的不同
map/set是双向迭代器而另外两个是单向的map/set有序另外两个没有顺序
unordered_map
unordered_map是存储key, value键值对的关联式容器其允许通过keys快速的索引到与其对应的value。在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问value。它的迭代器至少是前向迭代器。
哈希
哈希就是散列 就是这些值key和存储位置之间存在着映射的关联关系
哈希函数
哈希函数的内容也就是一个哈希是如何设计的
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单 直接定址法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀缺点需要事先知道关键字的分布情况使用场景适合查找比较小且连续的情况 除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址 平方取中法–(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况 折叠法–(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况 随机数法–(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。 通常应用于关键字长度不等时采用此法 数学分析法–(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。
说明
对于第一种方法的弊端很明显 比如存两个值1和1000那我是不是要开1001个空间空间太浪费了
我们用第二种方法就能大大的节省空间
哈希碰撞
但还是有问题 如果取余之后有了同样的余数怎么办
对于两个数据元素的关键字 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) 即**不同关键字通过相同哈希哈数计算出相同的哈希地址**该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢
解决哈希冲突
补充 哈希不会填满到超过自己设定的负载因子的时候会按照一定倍数扩容 负载因子/载荷因子 存进去的数据个数/表的大小 闭散列一般是0.7
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢
基本结构
enum State
{EMPTY,//空EXIST,//存在DELETE//删除
};templateclass K, class V
struct HashData
{pairK, V_kv; //键值对State _state EMPTY; //初始为空
};线性探测
从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
插入 先找到对应的位置找到空位置或者遍历完停止查找要注意循环到尾部的时候下一个是头部 bool Insert(const pairK, V kv) //线性探测版本{if (Find(kv.first) nullptr){return false;}if (_n*10 / _tables.size() 7){//方法2:比较神奇的写法HashTableK, VnewHT(_tables.size() * 2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);//把新的交换给旧的//旧的还能自动释放}size_t hashi kv.first % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}查找 HashDataconst k, V* Find(const K key){size_t hashi key % _tables.size();while (_tables[hashi]._state ! EMPTY){if (key _tables[hashi]._kv.first _tables[hashi]._state EXIST){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}这里的返回值给指针是为了方便删除
删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影 响。 因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;return true;}return false;}扩容 当超过负载因子的时候我们就要扩容 但是扩容之后可能原来不冲突的冲突了。 所以建议是开一个新的空间来重新一一映射 在此提供两种思路 开一个新空间遍历旧表将值给新表 //方法1size_t newSize _tables.size() * 2;vectorHashDatanewTables(newSize);_tables.swap(newTables);这种方法比较普通这种方法更巧妙每次插入新的值都去调用一次Insert但是是用扩容后的新表调用所以不用再扩容直接找到合适的位置存入即可 并且交换新表和旧表 //方法2:比较神奇的写法HashTableK, VnewHT(_tables.size() * 2);for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);//把新的交换给旧的//旧的还能自动释放优化1
我们要想一想如果参数是string这种无法进行%运算的类型怎么办 所以我们要增加一个模板参数来讲他们转化成可以运算的整形
那么我们可以将每一位的ASCII码值分别乘以131来作为关键码去取余这个131来自BKDRHash函数我们可以看这篇文章的分析
字符串哈希算法 struct HashFuncString{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash e;hash * 131;}return hash;}};优化2
因为string经常作为key所以我们可以进行特化 // 特化templatestruct HashFuncstring{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash e;hash * 131;}return hash;}};这样就不用再单独去写一个HashFuncString函数了
二次探测
找下一个空位置的方法为 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是表的大小。 也就是说先对关键码进行加减运算然后再取余
但是闭散列这种方式还是不够好
总结
闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。 下一篇文章将实现哈希桶。
