请问平衡搜索树，在哈希之外能够存在原因是不是”有序“？

lxyscls

哈希的插入、删除、查找都足够得好了，空间上的占用也不见得就比平衡树多

请问除了”有序“这个因素外，还有其他原因吗？

再加一个问题，标题写不下了：

链表哈希的并发是不是简单得用链表的并发来处理就可以了？类似这种的？

folklore

看数据量，
数据量比较小或不是很大很大时用Hash。
数据量很大时， 就不能用Hash了。
大数据时，
平衡树的平均性能和最大延迟相对于Hash比来说，
都更容易预测。

windoze

回复 2# folklore

说反了吧……

folklore

回复 3# windoze


    没反， 这是数据库为什么使用红黑树 而不是Hash表的原因。

windoze

回复 4# folklore

数据库用的是B+树，不是红黑树，再说用树就是为了实现ordered index，现在Oracle还有MySQL、Postgres都支持Hash/unordered index了。

lxyscls

两位大侠，能给个结论吗？

我理解的“有序”算不算一个比较重要的因素？

二楼说得大数据量还真没考虑到，因为涉及过的最多220K，所以也不算太大的HASH了{:3_188:}

lxyscls

folklore 发表于 2014-05-15 19:27
看数据量，
数据量比较小或不是很大很大时用Hash。
数据量很大时， 就不能用Hash了。

HASH O(1+a) a:装填因子

red-black O(logn)

平衡树的平均性能和最大延迟相对于Hash比来说，
都更容易预测。

为什么说平衡树比HASH更容易预测呢？是因为HASH的装填因子？

lxyscls

两位大侠，第二个关于并发的问题，如果知道的话，也麻烦给小弟解答一下嘛

windoze

回复 6# lxyscls

当然算啊，“有序”和“操作时间可预期”，就是红黑树之类的平衡树最大的优点。

Hash最大的问题实际是分布，不恰当的hash函数会导致hash分布不均匀，平均时间复杂度O(1)的查找操作，在最坏情况下会退化为O(N)，而红黑树之类的结构没有这个问题。如果你选取了适当的hash函数，随着数据量的增加，统计意义上分布会越来越均匀，此时hash可以达到最高的效率。

数据库用B+树，从原理上说其实和红黑树有很多相似的地方，这是一个有序的索引结构，所以数据库可以支持where a>100 and b<50这一类条件。
新的NoSQL大多数不支持range query，就是因为它们用了hash这种无序的索引结构。

lxyscls

windoze 发表于 2014-05-16 09:43
回复 6# lxyscls

当然算啊，“有序”和“操作时间可预期”，就是红黑树之类的平衡树最大的优点。

谢谢！

在不考虑“使用了不恰当的哈希函数”的前提下，如果数据不存在顺序或者是不需要涉及“顺序”的操作，哈希应该还是首选