Chinaunix

标题: 数据结构？哈希表和红黑树对字符串键，哪个快？ [打印本页]

作者: starwing83 时间: 2012-06-27 14:30
标题: 数据结构？哈希表和红黑树对字符串键，哪个快？
RT，字符串键分别是英文单词，以及随机的25长度的ASCII码，这两种情况下，分别在不同的数量级下，哈希表和红黑树哪个快呀……额，我懒得都自己写一份了……

作者: wwwsq 时间: 2012-06-27 14:37

通常是哈希表更快。

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

作者: hellioncu 时间: 2012-06-27 14:39
一般是哈希表快

作者: nilgod 时间: 2012-06-27 14:41
3楼所的对，但是要试验，还要考虑特殊数据分布。

作者: 三月廿七 时间: 2012-06-27 14:51
据说STL的 map 是用 rbtree实现的， map是一个哈希表，
也就是说，可以用 rbtree 实现哈希表，

作者: hellioncu 时间: 2012-06-27 15:06

三月廿七发表于 2012-06-27 14:51
据说STL的 map 是用 rbtree实现的， map是一个哈希表，
也就是说，可以用 rbtree 实现哈希表，

不知道你在说个啥，有单独的hash_map的实现

作者: _Rayx 时间: 2012-06-27 16:10
回复 1# starwing83

这两种情况下最快的都是Trie Tree啊

作者: starwing83 时间: 2012-06-27 16:27
回复 7# _Rayx

trie的内存嘛……

本质上，其实trie如果只要单级的话，就是一个哈希表吧……

作者: _Rayx 时间: 2012-06-27 20:27
回复 8# starwing83

内存又不值钱

作者: starwing83 时间: 2012-06-27 20:36
回复 9# _Rayx

内存是不值钱，但是分配动态内存是个很慢的活儿，或者可能让后面的内存分配变得很慢= =

作者: hbmhalley 时间: 2012-06-27 20:41
哈希表挂红黑树

作者: mirnshi 时间: 2012-06-28 13:08

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

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

作者: starwing83 时间: 2012-06-28 13:40
回复 12# mirnshi

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

作者: mirnshi 时间: 2012-06-28 15:11
回复 13# starwing83

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

作者: yulihua49 时间: 2012-06-28 15:13
本帖最后由 yulihua49 于 2012-06-28 15:15 编辑

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

作者: starwing83 时间: 2012-06-28 16:32
回复 15# yulihua49

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

作者: 三月廿七 时间: 2012-06-28 16:41
本帖最后由三月廿七于 2012-06-28 16:42 编辑

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

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

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

作者: 三月廿七 时间: 2012-06-28 16:45
回复 16# starwing83

数量级小，数组就行了，

作者: nilgod 时间: 2012-06-28 17:29
回复 15# yulihua49

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

作者: egmkang 时间: 2012-07-01 16:53

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

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

作者: wwwsq 时间: 2012-07-02 10:12
本帖最后由 wwwsq 于 2012-07-02 10:31 编辑

egmkang 发表于 2012-07-01 16:53
数量小的话,用谁都一样,搞不好数组都可以.
数据量大的话,hash会快很多,如果你的hash函数足够好的话:mr ...

哈希函数都差别不大，包括最近很火的murmur-hash，也只有特定场景才会略快一些。
如果是做比较通用的哈希表，各种哈希算法差别是不大的。

影响哈希表性能的因素主要是bucket的个数，以及哈希表本身的结构。

作者: yulihua49 时间: 2012-07-02 12:04
本帖最后由 yulihua49 于 2012-07-02 12:10 编辑

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

rbtree再小也比hash慢（比较次数多），假定你的hash函数足够好。
只有一个元素时，二者一样。

作者: yulihua49 时间: 2012-07-02 12:07

wwwsq 发表于 2012-07-02 10:12
哈希函数都差别不大，包括最近很火的murmur-hash，也只有特定场景才会略快一些。
如果是做比较通用的 ...

人家说是跟树比。
如果不同的hash方法，除了算法本身的速度，hash冲突的影响更大。

作者: wwwsq 时间: 2012-07-02 13:30
本帖最后由 wwwsq 于 2012-07-02 13:36 编辑

yulihua49 发表于 2012-07-02 12:07
人家说是跟树比。
如果不同的hash方法，除了算法本身的速度，hash冲突的影响更大。

“数据量大的话,hash会快很多”，这句话也是不准确的。无论数据多少，hash表都比rbtree快。

你看看2的乘方就知道了，64个元素的表，二叉树也要比较六次。比较六次就意味着要去六个随机内存地址取内容。虽然会有cpu预读之类的机制，但是还是会有损失。

作者: yulihua49 时间: 2012-07-02 14:28
本帖最后由 yulihua49 于 2012-07-02 14:56 编辑

wwwsq 发表于 2012-07-02 13:30
“数据量大的话,hash会快很多”，这句话也是不准确的。无论数据多少，hash表都比rbtree快。

你看看 ...

数据量大的话,hash会快很多--不是我说的。不过也是可以理解的。hash接近常数，而rbtree在数据量大的时候时间比较长，所以有那谁谁谁的结论。

其他--同意你的意见。

我们的项目需要对内存的各种数据进行检索，有大数据，也有小数据。
我们使用hash表，也使用AVL树。至于使用哪一种，并不取决于数据量的大小，一般都是使用hash表。只有：
当数据是动态的，即在使用过程中会增加一些或减少一些数据的场合，或：
需要对key进行不等比较时（小于，小于等于，大于，大于等于）才使用AVL树。

我们的实际情况，在100000级数据量下，hash的检索时间通常<0.1微秒，而AVL树则需要1.8微秒左右。给各位一个数量级方面的概念。

二叉树：
当仅使用二叉树排序时（建立，遍历，删除，并不用于检索），或对树的内容经常进行调整时，rbtree是最快的。
但是需要大量检索时，应该AVL树最合适。
所以我认为STL map使用AVL树更合适些。

作者: wwwsq 时间: 2012-07-02 15:10
本帖最后由 wwwsq 于 2012-07-02 15:14 编辑

yulihua49 发表于 2012-07-02 14:28
数据量大的话,hash会快很多--不是我说的。不过也是可以理解的。hash接近常数，而rbtree在数据量大的时候时 ...

“而rbtree在数据量大的时候时间比较长”，这句话是人云亦云。这多半是做性能测试做出来的结论。因为数据少的时候，数据都可以被cpu给cache住。所以那些人得出了这个似是而非的结论。
实际上在真实环境里面，不论数据多少，就算只有八条数据，二叉树也要三次随机内存读取，肯定是低效的。

AVL和红黑树各有特点，很难说哪个更好了。所以在STL之外，各种容器和数据结构还是毛多毛多的啊。。。。
要想用的爽，在特定的场合是要自己写数据结构的。不过这种场景不常见，一般来说STL就够了。

作者: hbmhalley 时间: 2012-07-02 15:19
本帖最后由 hbmhalley 于 2012-07-02 15:21 编辑

starwing83 发表于 2012-06-28 16:32
回复 15# yulihua49
我是比较担心在数量级较小的情况下，红黑反而会快。就比如插入排序在排序元素少于16个的情况下比快排快一样。

对啊，解决哈希冲突的过程不就像小数量级的插入排序么，rbtree才是类似快排. 比反了.

作者: yulihua49 时间: 2012-07-02 15:32
本帖最后由 yulihua49 于 2012-07-02 15:47 编辑

hbmhalley 发表于 2012-07-02 15:19
对啊，解决哈希冲突的过程不就像小数量级的插入排序么，rbtree才是类似快排. 比反了.

前边已经说了，你不必担心，一般情况就hash吧，不会有错。
除非。。。。。。。。。

hash冲突是在建hash表时处理的，不太影响后边的检索时间。
当然，冲突严重时是影响检索性能的。
所以你需要寻找一下对你来说较好的hash方法，减少冲突。

我们十来个元素就用hash了，如果检索频繁，能看到明显的效果。再少就顺序了。

数据量极少时讨论各种检索算法的性能，没意义吧？

我们也不是明知只有几条记录也弄个hash。只不过知道这个表数据量不大，几十上百的规模，但是查询频繁。就弄个hash，结果有时就几条，甚至1条记录，也就那么的了，不考察性能了。到底谁好谁不好，没意义。

作者: inet_addr 时间: 2012-07-02 17:29
单词有500个的话, 用多叉树可能最快
  struct Mtree
  {
   int value
   Mtree *child[128];
  };

  原因是多叉树最坏情形需要25次数值比较和指针操作.
  平均情形可能会 < 5次(看你的数据集了)

  hash的话光算hash值就需要25个数值操作(乘法), 后面是一个常数次的指针操作和数值比较.

单词有100万个, 可能多叉树就放不下了, hash会比各种树快, 原因是这是个典型的静态hash表
  查找问题. hash表的建立和查找都比树快.

单词有5000万个, 动态hash可能就建立补起来了, 平衡树可以建立起来.

单词有5亿个, 可能要多加4台机器, hash开, 还是hash

作者: wwwsq 时间: 2012-07-02 17:33

yulihua49 发表于 2012-07-02 15:32
前边已经说了，你不必担心，一般情况就hash吧，不会有错。
除非。。。。。。。。。

hash表最大的缺陷是当数据的量难以估计的时候，没法设置合适的bucket值。
元素可能是10个，也可能是10000个，那么hash表怎么初始化bucket个数。

这里有几种思路：
1，设置缺省的起始bucket个数为100左右，然后让hash表自动扩容。缺点是扩容的时候性能要受影响。
2，结合业务，每次给10000的bucket。缺点是浪费内存，而且无法处理100w这种极端情况。
3，把hash表的list变成哈希表。缺点是结构复杂，多次哈希速度慢。

综合来看，方案1是比较好的折中。

作者: wwwsq 时间: 2012-07-02 17:36

inet_addr 发表于 2012-07-02 17:29
单词有500个的话, 用多叉树可能最快
struct Mtree
{

你说的这个是trie树吗？或者稀疏矩阵。

因为cache miss的原因，未必有hash表性能高。不过在某些特定的场景（比如多模匹配），还是很有用的。

作者: inet_addr 时间: 2012-07-02 17:41
回复 31# wwwsq

是trie树, 不是稀疏矩阵, 不过它的缺点就是稀疏, 要不怎么快呢

作者: yulihua49 时间: 2012-07-03 13:16
本帖最后由 yulihua49 于 2012-07-03 13:17 编辑

wwwsq 发表于 2012-07-02 17:33
hash表最大的缺陷是当数据的量难以估计的时候，没法设置合适的bucket值。
元素可能是10个，也可能是 ...

前边25楼说了，动态的，用树。

作者: edgar51774 时间: 2012-07-03 15:55
哈希.............无疑问

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)