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

cjaizss

hash为非通用算法
而平衡树为通用算法
另外，在极致的情况下，hash的搜索复杂度为线性

lxyscls

cjaizss 发表于 2014-05-16 10:43
hash为非通用算法
而平衡树为通用算法
另外，在极致的情况下，hash的搜索复杂度为线性

请问这个地方“通用”和“非通用”是怎么定义的？

是不是讲平衡树的算法是“基本”固定的，而哈希为“非”固定，哈希函数需要选择？

yulihua49

lxyscls 发表于 2014-05-15 17:52
哈希的插入、删除、查找都足够得好了，空间上的占用也不见得就比平衡树多

请问除了”有序“这个因素外， ...

可以这么说。
我们有时需要比较>,>=,<,<=，这时hash就不灵了，必须平衡树。
看我们tree.h的一部分：

1. //返回=key的节点
   
2. T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
   
3.         int (*Cmp_rec)(void *sp_content,void *content_key,int len));
   
4. //返回>key的节点
   
5. T_Tree * BB_Tree_GT(T_Tree *sp,void *content_key,int len,
   
6.         int (*Cmp_rec)(void *s1,void *s2,int len));
   
7. //返回>=key的节点
   
8. T_Tree * BB_Tree_GTEQ(T_Tree *sp,void *content_key,int len,
   
9.         int (*Cmp_rec)(void *s1,void *s2,int len));
   
10. //返回<key的节点
    
11. T_Tree * BB_Tree_LT(T_Tree *sp,void *content_key,int len,
    
12.         int (*Cmp_rec)(void *s1,void *s2,int len));
    
13. //返回<=key的节点
    
14. T_Tree * BB_Tree_LTEQ(T_Tree *sp,void *content_key,int len,
    
15.         int (*Cmp_rec)(void *s1,void *s2,int len));
    
16. T_Tree * BB_Tree_Del(T_Tree *tp,void *content_key,int size_key,
    
17.             int (*Comp)(void *node,void *content,int size_content),
    
18.             int (*user_free)(void *content),int *flg);
    
19. T_Tree * BB_Tree_MAX(T_Tree *sp);
    
20. T_Tree * BB_Tree_MIN(T_Tree *sp);
    
21. 
    

复制代码

是我们内存数据库工具的一部分，hash怎么玩？
还有hash表动态插、删节点，导致性能劣化。

楼主大有“既生瑜何生亮”的感慨。事实上，瑜和亮都是需要的，各有各的用处。

cjaizss

lxyscls 发表于 2014-05-16 10:55
请问这个地方“通用”和“非通用”是怎么定义的？

是不是讲平衡树的算法是“基本”固定的，而哈希为 ...

\
恩，可以这么说.

folklore

回复 5# windoze


    用树是基本， HASH最多只能是辅助。
大数据下：
树的复杂度： O (log(n))
HASH无论HASH函数如何选， 是 O (n)。
当然，小数据下， HASH要以做到 o(1).

选择一个通用的HASH函数是不可能的。

windoze

回复 14# cjaizss

其实也不一定啊，平衡树要求元素必须能定义全序关系，hash反倒没这个要求，理论上说任何一个函数都可以拿来做hash function，无非是性能差点。

windoze

回复 15# folklore

hash是O(n)怎么讲？

lxyscls

回复 13# yulihua49

还有hash表动态插、删节点，导致性能劣化

请问这个怎么解释？

针对最常用的链表哈希，如果输入键值为随机的，那么无论怎么插入、删除，应该都是均匀的分布在每一个桶里面吧

为什么会劣化？

   

yulihua49

folklore 发表于 2014-05-16 11:13
回复 5# windoze

多大数据量叫“大”
我们在百万级的数据里使用hash，静态hash。
依然是O(1),关键是hash算法。

lxyscls

folklore 发表于 2014-05-16 11:13
回复 5# windoze

链表哈希的插入是O(1)
删除和查找是O(1+a) a:装载因子

您的O(n）是针对哪种哈希而言的？