哈希地图密钥不是随机的



看来,Java对Hashmap 始终的实现将键放在同一垃圾箱中(至少我用整数键看到了)。IE。哈希是确定性的,在所有运行中都产生相同的值。
我听说某些语言将插入随机化,以便出于安全原因而无法存储键的键。
为什么java键总是相同?

这里感兴趣的攻击是拒绝服务(DOS)。对手选择一组击中同一水桶的钥匙。这将地图操作的性能从O(1)转化为O(n)。做这个n次(构造地图说),然后我们从o(n)到o(n^2)。还可能进行计时攻击,但我会方便地忽略这一点。

通常,大多数库代码都会假定不需要避免DO的措施。但是,最近一些Java实现使用了杂音哈希将String的哈希功能随机化,以避免某些攻击。Murmur将每个进程的随机数混合到哈希代码的生成中,以使该函数在过程中是稳定的,但是很难(尽管不一定是不可能)从外部找出。最近,如果有过多的碰撞,并且钥匙适当地实现了Comparable,则它已替换为树结构。

如果您在发现代码的情况下担心这种攻击,则可以使用其他Map实现,例如java.util.TreeMap

对于Java 7而言,这是不正确的,该Java 7在每个hashmap实例中添加了唯一的哈希种子。关于Java SE 7页的收集框架增强功能的更多信息。

在Java 8中删除了此机制以进行性能,并由将可比较的键(例如字符串)转换为平衡的树以替代了DOS安全问题。关于Java SE 8页的收集框架增强功能的更多信息。

在Java中,单个类负责实现默认的hashcode()方法(或从Object类中继承一个),而复杂的安全方案(例如击败高级DOS攻击)等复杂的安全方案并不是责任诸如ObjectInteger等课程

因此,大多数类都使用非常简单,快速的实现,该实现试图确保在常见情况下分布均匀。

如果您认为实施自定义哈希策略很重要,无论是因为您要避免黑客入侵还是因为您知道您的特定用法可能会通过默认方法引起很多碰撞,you可以使用GNU Trove的THashMap之类的集合,该集合可以提供特定于集合实例的自定义哈希策略。

要完成其他答案,我会提到,当HashMap的键使用内置的Object.hashCode时,i。e。不要覆盖这种方法,这是一种经常的情况,使用随机数生成器计算对象的哈希码,这使整个系统behaivour降低了确定性。请参阅此问题:Java Object.hashCode() - 地址或Random()?有关更多详细信息。

最新更新