免费注册	查看新帖 \|


平台论坛博客文库

› 论坛 › 程序设计 › C/C++ › 数据结构？哈希表和红黑树对字符串键，哪个快？

123 4 / 4 页下一页

最近访问板块

发新帖

楼主: starwing83

上一主题

下一主题

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

论坛徽章:: 0

11楼 [报告]

发表于 2012-06-27 20:41 |只看该作者

哈希表挂红黑树

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

论坛徽章:: 2

技术图书徽章
日期:2013-09-04 15:21:51

酉鸡
日期:2013-11-01 21:20:20

12楼 [报告]

发表于 2012-06-28 13:08 |只看该作者

starwing83 发表于 2012-06-27 20:36
内存是不值钱，但是分配动态内存是个很慢的活儿，或者可能让后面的内存分配变得很慢= =

你干嘛总是纠结内存的分配呀，先分出一大块，组成链表，用的时候直接从链表上取就是了。

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

论坛徽章:: 5

狮子座
日期:2013-08-20 10:12:24

午马
日期:2013-11-23 18:04:10

2015年辞旧岁徽章
日期:2015-03-03 16:54:15

2015亚冠之德黑兰石油
日期:2015-06-29 18:11:11

15-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53

13楼 [报告]

发表于 2012-06-28 13:40 |只看该作者

回复 12# mirnshi

好办法，可是预先分配多少呢？如果不够的话，realloc是不行的吧？

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

论坛徽章:: 2

技术图书徽章
日期:2013-09-04 15:21:51

酉鸡
日期:2013-11-01 21:20:20

14楼 [报告]

发表于 2012-06-28 15:11 |只看该作者

回复 13# starwing83

这跟你的数据量有关系。比如预计存储多少个单元数据，如果少于1/3或1/4了，再申请一块大的，追加到链表上就行了。

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

论坛徽章:: 15

射手座
日期:2014-11-29 19:22:49

15-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09

黑曼巴
日期:2017-07-13 19:13:47

15-16赛季CBA联赛之四川
日期:2017-02-07 21:08:57

2015年亚冠纪念徽章
日期:2015-11-06 12:31:58

每日论坛发贴之星
日期:2015-08-04 06:20:00

程序设计版块每日发帖之星
日期:2015-08-04 06:20:00

程序设计版块每日发帖之星
日期:2015-07-12 22:20:00

2015亚冠之浦和红钻
日期:2015-07-08 10:10:13

2015亚冠之大阪钢巴
日期:2015-06-29 11:21:12

2015亚冠之广州恒大
日期:2015-05-22 21:55:41

2015年亚洲杯之伊朗
日期:2015-04-10 16:28:25

15楼 [报告]

发表于 2012-06-28 15:13 |只看该作者

本帖最后由 yulihua49 于 2012-06-28 15:15 编辑

当然是hash快。
不管表多大，hash基本都以不多的比较次数找到，而rb——tree需要多于O(log2(N))的比较次数。
与内存cache无关，大的内存表总是很分散的，基本cache不了。

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

论坛徽章:: 5

狮子座
日期:2013-08-20 10:12:24

午马
日期:2013-11-23 18:04:10

2015年辞旧岁徽章
日期:2015-03-03 16:54:15

2015亚冠之德黑兰石油
日期:2015-06-29 18:11:11

15-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53

16楼 [报告]

发表于 2012-06-28 16:32 |只看该作者

回复 15# yulihua49

我是比较担心在数量级较小的情况下，红黑反而会快。就比如插入排序在排序元素少于16个的情况下比快排快一样。

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

论坛徽章:: 0

17楼 [报告]

发表于 2012-06-28 16:41 |只看该作者

本帖最后由三月廿七于 2012-06-28 16:42 编辑

starwing83 发表于 2012-06-28 16:32
回复 15# yulihua49

随便挑个简单的写，不行再换，

怎么感觉你不会写程序一样？

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

论坛徽章:: 0

18楼 [报告]

发表于 2012-06-28 16:45 |只看该作者

回复 16# starwing83

数量级小，数组就行了，

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

论坛徽章:: 0

19楼 [报告]

发表于 2012-06-28 17:29 |只看该作者

回复 15# yulihua49

n复杂度的平凡排序算法如何？

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

论坛徽章:: 1

射手座
日期:2013-08-21 13:11:46

20楼 [报告]

发表于 2012-07-01 16:53 |只看该作者

starwing83 发表于 2012-06-28 16:32
回复 15# yulihua49

数量小的话,用谁都一样,搞不好数组都可以.
数据量大的话,hash会快很多,如果你的hash函数足够好的话

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

123 4 / 4 页下一页

发新帖

Chinaunix › 论坛 › 程序设计 › C/C++ › 数据结构？哈希表和红黑树对字符串键，哪个快？

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP