哈希码唯一性

两个Object实例是否可能具有相同的哈希码?

理论上,对象的哈希码是从其内存地址派生的,因此所有哈希码都应该是唯一的,但是如果在GC期间移动对象会怎样?

给定合理的对象集合,很可能有两个具有相同哈希码的对象。 在最好的情况下,它成为生日问题,与成千上万的对象发生冲突。 在实践中,使用相对较小的可能哈希码池创建对象,并且仅使用数千个对象就可以容易地发生冲突。

使用内存地址只是获取稍微随机数的一种方法。 Sun JDK源具有一个开关,可以使用安全随机数生成器或常量。 我相信IBM(曾经?)使用快速随机数生成器,但它根本不安全。 内存地址文档中的提及似乎具有历史性(大约十年前,具有固定位置的对象句柄并不罕见)。

这是几年前我写的一些代码,用于演示冲突:

class HashClash { public static void main(String[] args) { final Object obj = new Object(); final int target = obj.hashCode(); Object clash; long ct = 0; do { clash = new Object(); ++ct; } while (clash.hashCode() != target && ct<10L*1000*1000*1000L); if (clash.hashCode() == target) { System.out.println(ct+": "+obj+" - "+clash); } else { System.out.println("No clashes found"); } } } 

RFE澄清了文档,因为这种方式过于频繁: CR 6321873

我认为对象的hashCode方法的文档说明了答案。

“尽管合理实用,但是由Object类定义的hashCode方法确实为不同的对象返回不同的整数。(这通常通过将对象的内部地址转换为整数来实现,但JavaTM不需要这种实现技术)编程语言。)“

想一想。 有无数个潜在对象,只有40亿个哈希码。 显然,无限的潜在对象共享每个哈希码。

Sun JVM要么将Object哈希代码基于Object的稳定句柄,要么缓存初始哈希代码。 GC期间的压缩不会改变hashCode() 。 如果确实如此,一切都会破裂。

可能吗?

是。

是否以合理的频率发生?

没有。

我假设原始问题只是关于默认Object实现生成的哈希码。 事实是,不能依赖哈希码进行相等性测试,并且只在某些特定的哈希映射操作(例如由非常有用的HashMap实现实现的操作)中使用。

因此,它们不需要真正独特 – 它们只需要足够独特,不会产生大量冲突(这将导致HashMap实现效率低下)。

此外,当开发人员实现要存储在HashMaps中的类时,他们将实现一个哈希码算法,该算法对同一类的对象冲突的可能性很小(假设您只在应用程序HashMaps中存储相同类的对象) ),了解数据可以更容易地实现健壮的散列。

另请参阅Ken关于需要相同哈希码的相等性的答案。

您是在谈论实际的类Object还是一般的对象? 你在问题中同时使用两者。 (而真实世界的应用程序通常不会创建很多Object实例)

对于一般的对象,通常编写一个要覆盖equals() ; 如果你这样做,你还必须覆盖hashCode()以便该类的两个不同的“相等”实例也必须具有相同的哈希码。 在这种情况下,您可能会在同一个类的实例中获得“重复”哈希代码。

此外,当在不同的类中实现hashCode()时,它们通常基于对象中的某些内容,因此您最终会得到较少的“随机”值,从而导致不同类的实例之间出现“重复”哈希代码(无论这些对象是否存在)是“平等的”)。

在任何真实世界的应用程序中,使用相同的哈希码找到不同的对象并不罕见。

如果存在与内存地址一样多的哈希码,则需要整个内存来存储哈希本身。 🙂

所以,是的,哈希码有时应该重合。