哈希映射键不是随机的

Question

似乎Java的HashMap实现总是将键放在相同的bin中(至少我用Integer键看到了).即散列是确定性的,并且在所有运行中它产生相同的值.
我听说有些语言将插入随机化,以便出于安全原因,密钥将存储在哪个存储桶中是不可预测的.
为什么Java的密钥总是一样的？

Answer 1

这里感兴趣的攻击是拒绝服务 (DoS)。对手选择一组命中同一个桶的键。这将映射操作的性能从 O(1) 转换为 O(n)。这样做 n 次（比如构建地图），我们从 O(n) 到 O(n^2)。还有时间攻击的可能性，但我会很方便地忽略它。

通常，大多数库代码会假设不需要采取任何措施来避免 DoS。然而，最近一些 Java 实现使用 MURMUR 散列来随机化散列函数String以避免某些攻击。MURMUR 将每个进程的随机数混合到哈希码的生成中，这样函数对于进程来说是稳定的，但很难（虽然不一定不可能）从外部找出来。最近，如果发生过多的冲突并且密钥执行Comparable得当，这已被替换为回退到树结构。

如果您在找到代码的情况下担心此类攻击，则可以使用其他Map实现，例如java.util.TreeMap.

Answer 2

对于Java 7来说,情况并非如此,Java 7为每个HashMap实例添加了唯一的哈希种子.有关Java SE 7页面中的集合框架增强功能的更多信息.

为了提高性能,在Java 8中删除了这种机制,它被替换为将可比较的密钥(例如String)转换为平衡树以替代DoS安全问题的替代方法.有关Java SE 8页面中的集合框架增强功能的更多信息.