最坏情况平衡树稳一些
【 在 allegro 的大作中提到: 】
: 时间复杂度unordered_map吊打。
: 空间复杂度差不多，stl实现里面unordered_map的一个node的额外消耗只有map的node的一半。
: 如果不需要一颗排好序的树，基本没有什么理由使用map了吧？
: ...................
--
FROM 220.249.162.*

查了一下，java 这个是 CVE-2012-2739。

hash造成的性能问题（造成DoS就算安全问题）很底层，影响面就广。当然你说的不错绝大多数应用是不会出问题的，但面对刻意构造恶意数据包的攻击者来说，找到一个利用点就足够了，所以面对安全缺陷讨论条件常见与否就不太重要了。

事实上不止jvm出过这种安全问题，php、ruby等等好多语言或者框架也都有过类似的 CVE 漏洞。与其说是具体实现中hash函数取得不够好（一般是字符串的hash出问题），不如说hash表数据结构本身在性能退化方面风险就更大。

c++11 以前没有一开始定义 hashmap 是历史原因，但先定义有序的 map（下面可以是平衡树、b树或跳表之类），也确实有 hash 函数不好定义以及性能退化方面的考虑。印象里 Stroustrup 在哪儿提过，或者是 tc++pl，或者是《设计与演化》。

说到实现上的困难，即使今天，没有静态反射的 C++ 给自定义键类型添加 hash 重载还是挺繁琐易错的。而有反射的语言通常只要求有 operator== 就行。
【 在 here080 的大作中提到: 】
: hash攻击一般是针对数据库的吧。
: 放到容器里只能说这个系统太小作坊了。
: 【 在 milksea (肥了，又肥了 >>>_<<<) 的大作中提到: 】
: ...................
--
FROM 120.36.50.*