Java HashMap如何处理具有相同哈希代码的不同对象?

2022-08-31 05:32:00

根据我的理解,我认为:

  1. 两个对象具有相同的哈希码是完全合法的。
  2. 如果两个对象相等(使用 equals() 方法),则它们具有相同的哈希码。
  3. 如果两个对象不相等,则它们不能具有相同的哈希码

我说的对吗?

现在,如果正确的话,我有以下问题:内部使用对象的哈希码。因此,如果两个对象可以具有相同的哈希码,那么如何跟踪它使用的密钥呢?HashMapHashMap

有人可以解释内部如何使用对象的哈希码吗?HashMap


答案 1

哈希映射的工作原理是这样的(这有点简化,但它说明了基本机制):

它具有许多“存储桶”,用于存储键值对。每个存储桶都有一个唯一的编号 - 这是标识存储桶的内容。当您将键值对放入映射中时,哈希映射将查看密钥的哈希代码,并将该对存储在标识符为密钥的哈希代码的存储桶中。例如:密钥的哈希代码为 235 ->该对存储在存储桶编号 235 中。(请注意,一个存储桶可以存储多个键值对)。

当您在哈希映射中查找值时,通过为其提供一个键,它将首先查看您提供的密钥的哈希代码。然后,哈希映射将查看相应的存储桶,然后将您提供的密钥与存储桶中所有对的密钥进行比较,方法是将它们与 .equals()

现在,您可以看到这对于在映射中查找键值对非常有效:通过键的哈希代码,哈希映射立即知道要在哪个存储桶中查找,因此它只需要针对该存储桶中的内容进行测试。

看看上面的机制,你还可以看到对键和方法有哪些要求:hashCode()equals()

  • 如果两个键相同 (比较它们时返回),则它们的方法必须返回相同的数字。如果键违反了此规定,则相等的键可能存储在不同的存储桶中,并且哈希映射将无法找到键值对(因为它将查找到同一存储桶中)。equals()truehashCode()

  • 如果两个密钥不同,则它们的哈希代码是否相同并不重要。如果它们的哈希代码相同,它们将存储在同一个存储桶中,在这种情况下,哈希映射将用于区分它们。equals()


答案 2

你的第三个断言是不正确的。

两个不相等的对象具有相同的哈希代码是完全合法的。它被用作“首次通过过滤器”,以便地图可以快速找到具有指定键的可能条目。然后测试具有相同哈希代码的密钥是否与指定密钥相等。HashMap

您不希望要求两个不相等的对象不能具有相同的哈希代码,否则这会将您限制为232个可能的对象。(这也意味着不同类型的人甚至不能使用对象的字段来生成哈希代码,因为其他类可以生成相同的哈希。