免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 数据结构？哈希表和红黑树对字符串键，哪个快？
1234下一页
最近访问板块 发新帖
查看: 13319 | 回复: 33
打印 上一主题 下一主题

数据结构？哈希表和红黑树对字符串键，哪个快？ [复制链接]

starwing83

论坛徽章:
5
狮子座 日期:2013-08-20 10:12:24午马 日期:2013-11-23 18:04:102015年辞旧岁徽章 日期:2015-03-03 16:54:152015亚冠之德黑兰石油 日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆 日期:2024-02-21 10:00:53
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2012-06-27 14:30 |只看该作者 |倒序浏览
RT，字符串键分别是英文单词，以及随机的25长度的ASCII码，这两种情况下，分别在不同的数量级下，哈希表和红黑树哪个快呀……额，我懒得都自己写一份了……
wwwsq

论坛徽章:
0
2楼 [报告]
发表于 2012-06-27 14:37 |只看该作者

通常是哈希表更快。

因为红黑树需要四处去找字符串，找出来做strcmp。通常这些字符串都不在cpu cache里面的，结果会比较悲剧。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
hellioncu

论坛徽章:
324
射手座 日期:2013-08-23 12:04:38射手座 日期:2013-08-23 16:18:12未羊 日期:2013-08-30 14:33:15水瓶座 日期:2013-09-02 16:44:31摩羯座 日期:2013-09-25 09:33:52双子座 日期:2013-09-26 12:21:10金牛座 日期:2013-10-14 09:08:49申猴 日期:2013-10-16 13:09:43子鼠 日期:2013-10-17 23:23:19射手座 日期:2013-10-18 13:00:27金牛座 日期:2013-10-18 15:47:57午马 日期:2013-10-18 21:43:38
3楼 [报告]
发表于 2012-06-27 14:39 |只看该作者
一般是哈希表快
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
nilgod

论坛徽章:
0
4楼 [报告]
发表于 2012-06-27 14:41 |只看该作者
3楼所的对，但是要试验，还要考虑特殊数据分布。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
三月廿七

论坛徽章:
0
5楼 [报告]
发表于 2012-06-27 14:51 |只看该作者
据说STL的 map 是用 rbtree实现的， map是一个哈希表，
也就是说， 可以用 rbtree 实现 哈希表，
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
hellioncu

论坛徽章:
324
射手座 日期:2013-08-23 12:04:38射手座 日期:2013-08-23 16:18:12未羊 日期:2013-08-30 14:33:15水瓶座 日期:2013-09-02 16:44:31摩羯座 日期:2013-09-25 09:33:52双子座 日期:2013-09-26 12:21:10金牛座 日期:2013-10-14 09:08:49申猴 日期:2013-10-16 13:09:43子鼠 日期:2013-10-17 23:23:19射手座 日期:2013-10-18 13:00:27金牛座 日期:2013-10-18 15:47:57午马 日期:2013-10-18 21:43:38
6楼 [报告]
发表于 2012-06-27 15:06 |只看该作者
三月廿七 发表于 2012-06-27 14:51
据说STL的 map 是用 rbtree实现的， map是一个哈希表，
也就是说， 可以用 rbtree 实现 哈希表，


不知道你在说个啥，有单独的hash_map的实现
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
_Rayx

论坛徽章:
0
7楼 [报告]
发表于 2012-06-27 16:10 |只看该作者
回复 1# starwing83


    这两种情况下最快的都是Trie Tree啊
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
starwing83

论坛徽章:
5
狮子座 日期:2013-08-20 10:12:24午马 日期:2013-11-23 18:04:102015年辞旧岁徽章 日期:2015-03-03 16:54:152015亚冠之德黑兰石油 日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆 日期:2024-02-21 10:00:53
8楼 [报告]
发表于 2012-06-27 16:27 |只看该作者
回复 7# _Rayx


    trie的内存嘛……

本质上，其实trie如果只要单级的话，就是一个哈希表吧……
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
_Rayx

论坛徽章:
0
9楼 [报告]
发表于 2012-06-27 20:27 |只看该作者
回复 8# starwing83


    内存又不值钱
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
starwing83

论坛徽章:
5
狮子座 日期:2013-08-20 10:12:24午马 日期:2013-11-23 18:04:102015年辞旧岁徽章 日期:2015-03-03 16:54:152015亚冠之德黑兰石油 日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆 日期:2024-02-21 10:00:53
10楼 [报告]
发表于 2012-06-27 20:36 |只看该作者
回复 9# _Rayx


    内存是不值钱，但是分配动态内存是个很慢的活儿，或者可能让后面的内存分配变得很慢= =
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP