数据结构？哈希表和红黑树对字符串键，哪个快？

wwwsq

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

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

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

yulihua49

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

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

yulihua49

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

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

wwwsq

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

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

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

yulihua49

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

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

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


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

hbmhalley

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

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

yulihua49

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

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

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

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

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

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

inet_addr

单词有500个的话, 用多叉树可能最快
  struct Mtree
  {
     int value
     Mtree *child[128];
  };

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

  hash的话光算hash值就需要25个数值操作(乘法), 后面是一个常数次的指针操作和数值比较.
  
单词有100万个, 可能多叉树就放不下了, hash会比各种树快, 原因是这是个典型的静态hash表
  查找问题. hash表的建立和查找都比树快.

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

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

wwwsq

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是比较好的折中。