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

bruceteen

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

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

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

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

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

bruceteen

回复 35# windoze

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

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