珠海模板网站建设公司,互联网网站 数据库,wordpress获取评论回复,网龙网络公司官网#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前学习C和算法 ✈️专栏#xff1a;C航路 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章对你有帮助的话 欢迎 评论#x1f4ac; 点赞#x1… 个人主页Weraphael ✍作者简介目前学习C和算法 ✈️专栏C航路 希望大家多多支持咱一起进步 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注✨ 目录 一、哈希思想二、常见的哈希函数2.1 直接定址法2.2 除留余数法 三、哈希冲突3.1 哈希冲突的原因3.2 如何解决哈希冲突闭散列开放定址法开散列链地址法、开链法、哈希桶 四、unordered系列4.1 与map和set的区别4.2 map/set与unordered_map/unordered_set的性能测试 一、哈希思想
哈希是一种 映射 思想。它是将存储的值跟存储的位置建立映射关系由这种思想而构成的数据结构称为 哈希表散列表
哈希表中插入数据和查找数据 的步骤如下 插入数据根据当前待插入的元素的键值通过哈希函数计算出哈希值并存入相应的位置中 查找数据根据待查找元素的键值计算出哈希值判断对应的位置中存储的值是否与键值相等
例如数据集合{176459}哈希函数设置为hash(key) key % capacitycapacity为存储元素底层空间总的大小 显然这个哈希表并没有把所有位置都填满数据分布无序且分散。
因此哈希表又称为散列表。
那么如何建立映射关系呢这就要涉及到哈希函数了。
二、常见的哈希函数
2.1 直接定址法
函数原型Hash(key) A * key BA, B为常数
适用场景值的分部范围比较集中。例如统计字符字符出现的次数。缺点需要提前知道键值的分布情况。
2.2 除留余数法
函数原型Hash(key) key % m m为哈希表的大小
适用场景范围不集中分布分散的数据缺点容易出现哈希冲突需要借助特定方法解决。
三、哈希冲突
3.1 哈希冲突的原因 哈希冲突又称哈希碰撞不同的值可能会映射到同一个位置。 如果继续插入元素 44哈希值 hash(44) 44 % 10 4此时哈希值为 4 的位置处已经有元素了无法继续存入此时就发生了 哈希冲突。 3.2 如何解决哈希冲突
闭散列开放定址法 当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的下一个空位置中去。 那么如何寻找下一个空位置呢
线性探测法从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
例如我们用除留余数法(hash(key)key%10)将序列{1, 6, 10, 1000, 101, 18, 7, 40}插入到表长为10的哈希表中插入过程如下 通过上图可以看到随着哈希表中数据的增多产生哈希冲突的可能性也随着增加最后在40进行插入的时候更是连续出现了四次哈希冲突。于是如果哈希表接近满的话插入、查找、删除的效率都会越来越低。
优化方案二次探测每次向后探测 i ^ 2 步。尽管如此闭散列的效果还是不尽人意实际中还是 开散列 用的更多一些
开散列链地址法、开链法、哈希桶 所谓 开散列 就在原 存储位置 处带上一个 单链表如果发生 哈希冲突就将 冲突的值依次挂载即可。因此也叫做 链地址法、开链法、哈希桶。 例如我们用除留余数法将序列{1, 6, 15, 60, 88, 7, 40, 5, 10}插入到表长为10的哈希表中当发生哈希冲突时我们采用开散列的形式将哈希地址相同的元素都链接到同一个哈希桶下插入过程如下 开散列 中进行插入时如果对应位置的哈希值被占了那么就在对应位置开一块链表进行存储。开散列中进行查找时需要先根据哈希值找到对应位置并在单链表中进行遍历。
一般情况下单链表的长度不会太长的因为扩容后整体长度会降低。如果单链表真的过长了我们还可以将其转为红黑树此时效率依旧非常高。 值得一提的是 哈希表开散列法最快时间复杂度为 O(N)平均是 O(1)。
哈希表开散列法 和快排一样很特殊时间复杂度不看最坏的看 平均时间复杂度因为 最快的情况几乎不可能出现。
四、unordered系列
4.1 与map和set的区别 哈希表最厉害的地方在于 查找速度非常快比红黑树还快时间复杂度是O(1)后面的性能测试见。因此在 C11 标准中利用 哈希表 作为底层结构重写了 set / map就是 unordered_set / unordered_map。 unordered系列的使用和map以及set几乎没区别使用方面建议大家查文档点击跳转
要说有区别如下 4.2 map/set与unordered_map/unordered_set的性能测试 说到一个容器的性能我们最关心的实际就是该容器增删查改的效率。我们可以通过下列代码测试set容器和unordered_set容器insert、find以及erase的效率。 【测试代码】
#include iostream
#include unordered_set
#include unordered_map
#include set
#include map
#include vector
using namespace std;void Performance_testing()
{// set和unordered_setconst int N 1000000; // 一百万setint s;unordered_setint us;vectorint v;v.reserve(N);srand(time(0));for (int i 0; i N; i){v.push_back(rand());// v.push_back(rand() i);// v.push_back(i);}// 插入测试 size_t begin1 clock();for (auto e : v){s.insert(e);}size_t end1 clock();cout set的插入时间 end1 - begin1 endl;size_t begin2 clock();for (auto e : v){us.insert(e);}size_t end2 clock();cout unordered_set的插入时间 end2 - begin2 endl;// 查找测试 size_t begin3 clock();for (auto e : v){s.find(e);}size_t end3 clock();cout set的find end1 - begin1 endl;size_t begin4 clock();for (auto e : v){us.find(e);}size_t end4 clock();cout unordered_set的find end4 - begin4 endl;cout set插入数据个数: s.size() endl;cout unordered_set插入数据个数: us.size() endl;// 删除测试 size_t begin5 clock();for (auto e : v){s.erase(e);}size_t end5 clock();cout set删除 end5 - begin5 endl;size_t begin6 clock();for (auto e : v){us.erase(e);}size_t end6 clock();cout unordered_set删除 end6 - begin6 endl;
}int main()
{Performance_testing();return 0;
}对1000个数做增删查改操作 我们发现当数据量小的时候它们的效率差不多。
对10000000个数做增删查改操作 当数据量达到一千万的时候明显unordered系列快多了。
根据测试结果可以得出以下结论 当处理数据量小时map/set容器与unordered系列容器增删查改的效率差异不大。 当处理数据量大时map/set容器与unordered系列容器增删查改的效率相比unordered系列容器的效率更高。
因此如果在unordered系列和map/set容器应该首选unordered系列 另外如果需要存储的序列为有序时应该选用map/set容器。
