免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2153 | 回复: 8

[C++] stl的hash容器,在实现层面,是如何做到用key来寻址元素的? [复制链接]

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:58:11
发表于 2015-11-28 19:57 |显示全部楼层
20可用积分
stl的unordered_map和unordered_set都是哈希容器,这个我知道。
例如unordered_map<string,A>就是用string作为key,A类型的对象作为值

那么问题来了,哈希容器的内部实现用什么“物理手段”来寻址某个元素呢?

1. 如果容器是用一个连续分配的空间,例如数组和vector那种,那么key算出来,作为一个数组的偏移量,可以寻址。但是显然造成一个极其稀疏的存储。不能这么干。
2. 我看stl的源代码里面,这两个容器内部都是用std::list来存储元素的。我们知道list是不能随机访问的。那么如何从一个计算出来的key,来找到我要的元素呢? 不能把key作为偏移量,因为不是数组;不能把key作为二分查找的手段,因为无序。那key是怎么映射到元素的?

希望我的问题表述清楚了。还请板上的各位高手指教!

最佳答案

查看完整内容

回复 6# asker160 当然不是固定的啦,所以才会有rehash这个过程,就是增加或减少bucket的数量,然后根据新的bucket分布把元素重新插进去。有个术语叫load factor,就是指每个bucket包含的平均元素个数,这个数决定了hash table的查找速度,假设计算hash是个常数时间,那么定位bucket也是个常数时间,但在bucket里面找元素的复杂度就是O(load_factor)了,因为bucket就是个链表。load factor太大说明hash table查找会比较慢,太小往 ...

论坛徽章:
43
15-16赛季CBA联赛之四川
日期:2018-10-13 23:26:5015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:36程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2015-11-28 19:57 |显示全部楼层
回复 6# asker160

当然不是固定的啦,所以才会有rehash这个过程,就是增加或减少bucket的数量,然后根据新的bucket分布把元素重新插进去。
有个术语叫load factor,就是指每个bucket包含的平均元素个数,这个数决定了hash table的查找速度,假设计算hash是个常数时间,那么定位bucket也是个常数时间,但在bucket里面找元素的复杂度就是O(load_factor)了,因为bucket就是个链表。
load factor太大说明hash table查找会比较慢,太小往往说明最上面的那个vector太大了,浪费了内存。

论坛徽章:
1
技术图书徽章
日期:2014-03-06 15:32:30
发表于 2015-11-28 20:37 |显示全部楼层
vector+list

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:58:11
发表于 2015-11-28 21:36 |显示全部楼层
回复 2# selfrun


    如果是vector+list的话,如何解决我上面说的这个问题呢? 如果value在vector里面,那么key是无序的,如何用一个无序的key来定位某个元素的下标,而不需要一个无穷大的vector?
    如果value是在list里面,list不能随机寻址,又如何能定位元素呢?

谢谢。

论坛徽章:
43
15-16赛季CBA联赛之四川
日期:2018-10-13 23:26:5015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:36程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2015-11-29 01:38 |显示全部楼层
unordered_map结构是一个vector of list of pair<key, value>
最上面是一个vector,每个元素都是一个list header,每个list都存了一堆元素,术语叫bucket。
定位过程是通过hash(key)找到bucket,然后遍历bucket找到具体的key和其对应value
hash(key)和bucket的对应关系可以是hash(key) % bucket_count,也就是说hash相同的key一定在同一个bucket里,当然一个bucket可以对应多个hash

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2015-11-29 13:19 |显示全部楼层
回复 4# windoze
高手就是能够将复杂的结构,
采用通俗易懂的词汇,
一下子将问题给说透了。
赞一个!

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:58:11
发表于 2015-11-29 21:49 |显示全部楼层
回复 4# windoze


    谢谢你的回答,我有一个问题,这个vector的大小,在创建的时候就是固定的吗? 我觉得是固定的,因为hash要对这个大小取模,那么不可能这个大小在运行时改变,hash就和原先不一样了。
    但是,这就带来一个问题,vector如果固定大小是个很小的值,容易碰撞,每次遍历一个list不值得。
    如果vector一上来就取一个很大的值,太浪费。如果我是几千个元素的hash,我上来分配一百万个元素岂不是太浪费。而且,即使我上来分配一百万个元素,如果这个hash有一亿个元素,那么每个list也有一百个元素,效率还是太低了。

    我不知道这个问题是如何解决的?

论坛徽章:
43
15-16赛季CBA联赛之四川
日期:2018-10-13 23:26:5015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:36程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2015-12-01 15:52 |显示全部楼层
回复 7# asker160

unordered_map的rehash没有你想的那么聪明,它就是新建一个vector<list<pair<key, value>>>结构,然后把所有现在有的k/v搬过去,这个过程对于巨大的map肯定慢的受不了。
但这个过程的触发是自动的,它有一个max_load_factor属性,如果它发现当前的load_factor超过了max_factor,就自动开始rehash,在此期间你的insert操作就一直挂在那儿,等到它rehash完了才会返回。

所以在实践中,unordered_map最好一上来就估算好大概容量,然后根据这个数字设定好bucket的数量,然后把max_load_factor设成一个巨大的值让它不要做自动rehash。
如果你不这么干程序当然也能转,但时不时会卡一下,而且内存用量会突然暴涨……

评分

参与人数 1信誉积分 +50 收起 理由
asker160 + 50 赞一个!

查看全部评分

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,7折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时七折期:2019年8月31日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP