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

lxyscls

folklore 发表于 2014-05-16 12:25
回复 17# windoze

大概明白你说的意思了

n/a 即 装载因子

当槽位数a相对n可以作为一个常数因子的时候，就可以看做是O（n）了

bruceteen

hashtable的效率高，这个“效率”仅指“统计效率”，相比较于平衡搜索树，有两个半不足：
a. 具体到某个单次的操作，可能因为“碰撞”和“二次碰撞”的原因，耗时 远远远远远远远远远远远远远远 超过 平衡搜索树的操作，时间要求严格的场合就不适用。
b. 可以针对具体的哈希函数设计攻击用的输入数据，从而使得效率降低。
c. 缺乏输入统计信息时，无法设计出一个高效的哈希函数。
以上原因，就是C++为什么先有std::map，而后才加入std::unordered_map的原因。

一一举例：
a. 曾用过一个国产的，号称速度最快的实时数据库。拿来测试后发现，虽然它整体效率是其它数据库的5到8倍，但它插入数据时有可能会停滞几毫秒。
这就没法用了，因为几毫米的时间就会丢失上万的数据，整个生产线上的设备会因为这几毫秒而报废。
因此只能选用那些虽然单次操作效率不高，但一定能在规定时间完成的实时数据库。

b. 有一家游戏公司需要用户在网上注册用户名。对手公司就根据其hash函数设计出了攻击数据，也就是反向算出一系列名字不同，但hash之后值一样的用户名。
短短几分钟后，就让那家游戏公司的网页无法注册了，用户注册时超时失败，已经注册过的用户进入游戏时也是超时失败。

c. 曾经要保存客户单位的油路温度，一个小头目脑子进水一定要用hashtable，然后就问客户：“温度下限是多少，上限是多少，每个温度的分布比率是多少，……？”，客户烦了，违反保密要求给了它某个采集点去年全年的数据，它回公司兴匆匆的统计了几天，设计出一个效率最高的hash函数，它告诉我它的hash函数能将前十个最可能的温度范围扩大，从而减少hash碰撞率。
实测的时候，客户单位的老总来也参观，但我们的系统比其公司的老系统更慢，而且上下限也是错的，丢人丢到姥姥家了。原因是不同采集点的数据其统计特点都不相同，即使是同一个采集点，每隔几年的统计特性也不同，更换设备会导致不同，大旱和大雨会导致不同，油品会导致不同，某个城市用油量变化会导致不同，……。
总之吧，一般很少有办法能够事先知道输入数据的统计信息，从而无法设计出一个优秀的hash函数，只能牺牲效率设计一个较为通用的哈希函数，即使“牺牲效率”了，还要防止自然状态下出现数据攻击。

总之吧，在正式场合，除非已经考虑到所有一切的可能，决不能用hash。

lxyscls

bruceteen 发表于 2014-05-16 13:06
hashtable的效率高，这个“效率”仅指“统计效率”，相比较于平衡搜索树，有两个半不足：
a. 具体到某个单 ...

受教了，您说的A情况确实从来没有考虑过，可能碰到的应用场景都比较简单，只追求统计效率吧

关于情况B，CLRS上面有讲，全域哈希，使用一组哈希函数，随机的选取哈希函数。不是很理解的是：同一个数据如何保证每次都哈希到同一个桶

非常感谢！

windoze

回复 28# folklore

因为无论HASH表项有多大， 但总是一个常数a。

错了，bucket的数量不是常数，每个bucket的大小才（近似）是常数，当平均的bucket size达到某个临界值(max load factor)之后需要rehash。

windoze

回复 32# bruceteen

攻击神马的也不是每个场合都要考虑，很多场合数据都是安全的。
在互联网应用上，相当多的情况下key是系统生成的seq id、UUID或者MD5/SHA1摘要之类的东西，分布真的不是问题。

案例a：你们需要的是“实时性”，那个数据库的优点是“吞吐量”，考察点都没搞清就把责任推到别人身上了。
案例b：用户注册这种东西难道系统不生成一个内部ID？难道外人还能攻击这个ID的生成？如果有内部ID，难道还有人愿意用用户输入的用户名做key？
案例c：最后那个场景，不管是hash还是平衡树，拿“温度”做key真的大丈夫？

在我看来你提到的失败案例都是设计错误，hash躺枪了，而且你最后的结论适用于任何东西，不只是hash。

bruceteen

回复 35# windoze

a. 难道这个主题不就是在讨论hashtable和平衡树的差别？结论就是在实时性要求高的场合，不适用hashtable。
b. 用户名和id怎么一一对应？我举的例子就是在用hash从用户名到id的转化。你说当用户输入用户名后怎么返回这个用户的游戏数据？
c. 你以为温度值是无限精度的实数呀？起码这世界上没有这样的传感器。这个案例说明的是：当无法获得统计信息时，就无法设计出较优的hash。

楼主的问题是：请问平衡搜索树，在哈希之外能够存在原因是不是”有序“？
你回答的是：哈希存在的原因。

井蛙夏虫

hash简单，平衡树复杂。
hash无序，平衡树有序。
hash时，桶的大小选择如果太大，空间浪费；如果太小，碰撞增加，查找性能差。可以使桶的大小动态可变(rehash),但rehash需要花费时间。
hash较适合数据比较固定，查找多，增删少的情况。在频繁增删时，性能可能很差。
hash较依赖hash函数的选择。
hash在碰撞较少时的查找性能比平衡树好，但一般情况下，hash比平衡树要有更多的空间浪费。

yulihua49

井蛙夏虫 发表于 2014-05-19 13:42
hash简单，平衡树复杂。
hash无序，平衡树有序。
hash时，桶的大小选择如果太大，空间浪费；如果太小，碰 ...

前边说过的。
hash只能查找相等。树可以查找不等式，MAX，MIN什么的。

快乐的土豆

hash号称是O(1),仅仅是表示在常量时间内查找，事实上，某些场合，计算hash的代价并非可以忽略不计的。而且，世界上并不存在一个通用的hash算法，能够保证不冲突或者冲突极少。
平衡搜索树的问题，我觉得是在平衡这个点，平衡的时候必须要锁定整个树，代码非常的昂贵啊。

yulihua49

快乐的土豆 发表于 2014-05-19 14:03
hash号称是O(1),仅仅是表示在常量时间内查找，事实上，某些场合，计算hash的代价并非可以忽略不计的。而且， ...

对的，树，在变更时必须锁，但hash变更时同样要锁，这点二者没区别。