免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: VIP_fuck

[C++] 请教:STL的map为什么用红黑树而不是哈希 [复制链接]

论坛徽章:
12
2015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之同曦
日期:2017-03-17 19:13:162016科比退役纪念章
日期:2016-11-07 08:28:12luobin
日期:2016-06-17 17:46:36wusuopu
日期:2016-06-17 17:43:4515-16赛季CBA联赛之福建
日期:2016-01-14 12:49:22程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:002015年亚洲杯之科威特
日期:2015-03-24 14:21:272015年迎新春徽章
日期:2015-03-04 09:57:092016科比退役纪念章
日期:2018-04-10 16:20:18
发表于 2015-05-30 23:23 |显示全部楼层
回复 9# egmkang


   
多谢,多谢指教。

论坛徽章:
12
巳蛇
日期:2013-09-16 15:32:242015年辞旧岁徽章
日期:2015-03-03 16:54:152015年亚洲杯之约旦
日期:2015-02-11 14:38:37双鱼座
日期:2015-01-05 11:05:47戌狗
日期:2014-12-08 09:41:18戌狗
日期:2014-08-15 09:29:29双子座
日期:2014-08-05 09:17:17卯兔
日期:2014-06-08 15:32:18巳蛇
日期:2014-01-27 08:47:08白羊座
日期:2013-11-28 21:04:15巨蟹座
日期:2013-11-13 21:58:012015年亚洲杯之科威特
日期:2015-04-17 16:51:51
发表于 2015-06-01 10:56 |显示全部楼层
呵呵,笑了。

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2015-06-05 20:49 |显示全部楼层
回复 9# egmkang


    红黑树比Hash更省内存,同时速度更快。

Hash仅在小数据量下, 可能比红黑树快。

Hash不会降低算法复杂度, 它的复杂度是 n/Hash队列数。 也就是O(N)。和遍历数组的复杂度是一样的。

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2015-06-08 09:52 |显示全部楼层
folklore 发表于 2015-06-05 20:49
回复 9# egmkang


你是不是弄错了什么?

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2015-06-08 10:27 |显示全部楼层
回复 14# egmkang


    HASH的复杂度是O(N), 你不信就再想想, 不点违反常识?

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2015-06-09 10:27 |显示全部楼层
folklore 发表于 2015-06-08 10:27
回复 14# egmkang


buckets数的选择应该和N成比例的么?

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2015-06-09 10:33 |显示全部楼层
lxyscls 发表于 2015-06-09 10:27
buckets数的选择应该和N成比例的么?

不想跟你扯

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2015-06-09 14:06 |显示全部楼层
回复 17# egmkang


    你看错了

论坛徽章:
154
2022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:5720周年集字徽章-年
日期:2022-10-26 16:44:2015-16赛季CBA联赛之深圳
日期:2022-11-02 14:02:4515-16赛季CBA联赛之八一
日期:2022-11-28 12:07:4820周年集字徽章-20	
日期:2023-07-19 08:49:4515-16赛季CBA联赛之八一
日期:2023-11-04 19:23:5115-16赛季CBA联赛之广夏
日期:2023-12-13 18:09:34
发表于 2015-06-14 09:49 来自手机 |显示全部楼层
现在技术大环境是,内存越来越不值钱了,红黑树正在成为过去时


hash的优点很明显,就是方便快,貌似复杂度o1的说

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2015-06-15 16:44 |显示全部楼层
本帖最后由 yulihua49 于 2015-06-15 16:47 编辑
shang2010 发表于 2015-06-14 09:49
现在技术大环境是,内存越来越不值钱了,红黑树正在成为过去时

完全没有冲突时是。
完全冲突时如folklore 所说。

动态的hash很容易退化,rbtree不会。
如果需要查找不等式,hash就无能为力了。

在以上两种情况,我会选择tree。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP