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

yulihua49

lxyscls 发表于 2014-05-16 11:22
回复 13# yulihua49

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

那要看你的具体算法的安排和实际的数据，你无法保证不劣化，好的话可能会劣化的慢一些。

lxyscls

回复 19# yulihua49

请问您这里讲的静态HASH是不是指针对一个静态集合（数据个数固定，只支持查找，譬如说一般的字典？）

使用完美哈希的方式


   

lxyscls

回复 21# yulihua49

谢谢，大概明白一些了

暂时抛开哈希函数的选择问题，只谈数据

实际应用中的数据无法保证数学上面的真正均匀分布，因此哈希无法保证不劣化？是不是可以这么理解部分？

   

yulihua49

lxyscls 发表于 2014-05-16 11:29
回复 19# yulihua49

请问您这里讲的静态HASH是不是指针对一个静态集合（数据个数固定，只支持查找，譬如 ...

是这样的。容易设计出最小冲突键。

有意思的是，无论如何选择，冲突率总是在1/3左右，二次冲突占一次冲突的1/3,......很奇怪。

yulihua49

lxyscls 发表于 2014-05-16 11:32
回复 21# yulihua49

谢谢，大概明白一些了

我感觉应该是的。
而平衡树永远不会劣化。
所以数据库通常使用B+树而较少使用hash。

folklore

回复 19# yulihua49


    所谓O （X) 是指动态增长时的函数关系。
也就是当 数据量是1（好吧，你这里的1是百万）时复杂度是1，
数据量为n时， 复杂度是多少， 对树来说， Log(n)是没有疑问的，
这也是我见过的在现在数学上能做到的最好的查找复杂度。
百万是 O（1）， 那百万的百万呢？

HASH表，无论你做几层HASH，
HASH的表项有几个（如比一亿个），
随着数据量的增加， 它的复杂度将变成 O(n),
因为平均每个表项上冲突的数据将是： n/表项数。 而表项数无论如何都是常数
（就算它能自动增长，对数据量来说， 它也是低价函数或者常数，
因为HASH表本来就是基于这个原理的， 不然HASH表就被"优化"成线性表了。
对于查找算法来说， o(n)是数学上最高的复杂度，
它和线性查找的复杂度一样：也就是说使用HASH表不会降低复杂度。

folklore

回复 20# lxyscls


    你的复杂度算法比较先进～～

folklore

回复 17# windoze


    因为无论HASH表项有多大， 但总是一个常数a。
这样，最终在大数据量的情况下， 复杂度是 n/a ，也就是 o(n).
一次HASH是这样， n 次HASH的复杂度是
o（n)/(1的n次方)， 还是o(n).
也就是说HASH不会减小算法的时间复杂度。
它只是表项相对多， 数据量相对小的情况下改善时间性能一种“技巧”。

yulihua49

回复 26# folklore
补充一点，O(1)就是与数据量无关，静态hash,不管数据量多大，都能做到O（1）。当然要选取良好的hash函数。(f(key)%n)
动态的，劣化以后就不好说了，可能会 O(n)吧。


   

cjaizss

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

这里的O(n)前面最好加个“伪”字