为什么Java中不同的对象hashCode()可以返回相同的值？

Question

我正在阅读的书中引用Head First Java< /a>:

重点是，哈希码可以相同，但不一定保证对象相等，因为 hashCode() 方法中使用的“哈希算法”可能碰巧为多个对象返回相同的值对象。

为什么 hashCode() 方法可能为不同的对象返回相同的值？这不会造成问题吗？

Answer 1

对对象进行哈希处理意味着“找到一个好的、描述性的值（数字），该值可以由同一实例一次又一次地再现”。由于 Java 的 Object.hashCode() 中的哈希码的类型为 int，因此只能有 2^32 不同的值。这就是为什么当两个不同的对象产生相同的 hashCode 时，根据哈希算法，您将出现所谓的“冲突”。

通常，这不会产生任何问题，因为 hashCode() 主要与 equals() 一起使用。例如，HashMap 将对其键调用 hashCode()，以了解键是否已包含在 HashMap 中。如果 HashMap 没有找到哈希码，则显然该键尚未包含在 HashMap 中。但如果确实如此，则必须使用 equals() 仔细检查具有相同哈希码的所有键。

即

A.hashCode() == B.hashCode() // does not necessarily mean
A.equals(B)

但是

A.equals(B) // means
A.hashCode() == B.hashCode()

如果 equals() 和 hashCode() 正确实现。

有关常规 hashCode 合约的更准确描述，请参阅 Javadoc。

Answer 2

可能的哈希码只有超过 40 亿个（int 的范围），但您可以选择创建的对象数量要大得多。因此，根据鸽子洞原理，某些对象必须共享相同的哈希码。

例如，包含来自 AZ 的 10 个字母的可能字符串数量为 26**10，即 141167095653376。不可能为所有这些字符串分配唯一的哈希码。这也不重要——哈希码不需要是唯一的。它只需要与真实数据没有太多冲突即可。

Answer 3

哈希表的想法是您希望能够以有效的方式实现称为字典的数据结构。字典是一种键/值存储，即您希望能够在某个键下存储某些对象，然后能够使用相同的键再次检索它们。

访问值最有效的方法之一是将它们存储在数组中。例如，我们可以实现一个使用整数作为键和字符串作为值的字典，如下所示：

String[] dictionary = new String[DICT_SIZE];
dictionary[15] = "Hello";
dictionary[121] = "world";

System.out.println(dictionary[15]); // prints "Hello"

不幸的是，这种方法根本不是很通用：数组的索引必须是整数值，但理想情况下我们希望能够使用任意类型的对象作为我们的键，而不仅仅是整数。

现在，解决这个问题的方法是找到一种将任意对象映射到整数值的方法，然后我们可以将其用作数组的键。在 Java 中，这就是 hashCode() 的作用。现在，我们可以尝试实现一个 String->String 字典：

String[] dictionary = new String[DICT_SIZE];
// "a" -> "Hello"
dictionary["a".hashCode()] = "Hello";

// "b" -> "world"
dictionary["b".hashCode()] = "world";

System.out.println(dictionary["b".hashCode()]); // prints world

但是，嘿，如果我们想将某个对象用作键，但它的 hashCode 方法返回一个值怎么办？大于或等于 DICT_SIZE？然后我们会得到一个 ArrayIndexOutOfBoundsException，这是不希望的。那么，我们就让它尽可能大吧？

public static final int DICT_SIZE = Integer.MAX_VALUE // Ooops!

但这意味着我们必须为数组分配大量内存，即使我们只打算存储几个项目。所以这并不是最好的解决方案，事实上我们可以做得更好。假设我们有一个函数 h，对于任何给定的 DICT_SIZE，将任意整数映射到 [0, DICT_SIZE[] 范围内。然后，我们可以将 h 应用于键对象返回的任何 hashCode() 方法，并确保我们停留在底层数组的边界内。

public static int h(int value, int DICT_SIZE) {
    // returns an integer >= 0 and < DICT_SIZE for every value.
}

该函数称为哈希函数。现在我们可以调整字典实现来避免 ArrayIndexOutOfBoundsException：

// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)] = "Hello"

// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)] = "world"

但这引入了另一个问题：如果 h 将两个不同的键索引映射到相同的值怎么办？例如：

int keyA = h("a".hashCode(), DICT_SIZE);
int keyB = h("b".hashCode(), DICT_SIZE);

keyA 和 keyB 可能会产生相同的值，在这种情况下，我们会意外地覆盖数组中的值：

// "a" -> "Hello"
dictionary[keyA] = "Hello";

// "b" -> "world"
dictionary[keyB] = "world"; // DAMN! This overwrites "Hello"!!

System.out.println(dictionary[keyA]); // prints "world"

好吧，你可能会说，那么我们只是必须确保我们以永远不会发生这种情况的方式实现 h。不幸的是，这通常是不可能的。考虑以下代码：

for (int i = 0; i <= DICT_SIZE; i++) {
    dictionary[h(i, DICT_SIZE)] = "dummy";
}

此循环在字典中存储 DICT_SIZE + 1 值（实际上始终是相同的值，即字符串“dummy”）。嗯，但是数组只能存储 DICT_SIZE 不同的条目！这意味着，当我们使用 h 时，我们将覆盖（至少）一个条目。或者换句话说，h 会将两个不同的键映射到相同的值！这些“碰撞”是无法避免的：如果n只鸽子试图进入n-1个鸽子洞，那么至少其中两只必须进入同一个洞。

但我们可以做的是扩展我们的实现，以便数组可以在同一索引下存储多个值。这可以通过使用列表轻松完成。因此，我们不使用：，而是

String[] dictionary = new String[DICT_SIZE];

写：（

List<String>[] dictionary = new List<String>[DICT_SIZE];

旁注：请注意，Java 不允许创建泛型类型的数组，因此上面的行无法编译 - 但您明白了）。

这将改变对字典的访问，如下所示：

// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)].add("Hello");

// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)].add("world");

如果我们的哈希函数 h 为所有键返回不同的值，这将导致列表中每个列表只有一个元素，并且检索元素非常简单：

System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); // "Hello"

但是我们已经知道，通常 h 有时会将不同的键映射到同一个整数。在这些情况下，列表将包含多个值。为了检索，我们必须遍历整个列表才能找到“正确”的值，但是我们如何识别它呢？

好吧，我们可以始终将完整的（键，值）对存储在列表中，而不是单独存储值。然后，查找将分两步执行：

1. 应用哈希函数从数组中检索正确的列表。
2. 迭代存储在检索列表中的所有对：如果找到具有所需键的对，则返回该对中的值。

现在添加和检索已经变得如此复杂，以至于为这些操作单独处理方法并不不雅：

List<Pair<String,String>>[] dictionary = List<Pair<String,String>>[DICT_SIZE];

public void put(String key, String value) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex == null) {
        listAtIndex = new LinkedList<Pair<Integer,String>>();
        dictionary[arrayIndex] = listAtIndex;
    }

    for (Pair<String,String> previouslyAdded : listAtIndex) {
        if (previouslyAdded.getKey().equals(key)) {
            // the key is already used in the dictionary,
            // so let's simply overwrite the associated value
            previouslyAdded.setValue(value);
            return;
        }
    }

    listAtIndex.add(new Pair<String,String>(key, value));
}

public String get(String key) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex != null) {
        for (Pair<String,String> previouslyAdded : listAtIndex) {
            if (previouslyAdded.getKey().equals(key)) {
                return previouslyAdded.getValue(); // entry found!
            }
        }
    }

    // entry not found
    return null;
}

因此，为了使这种方法起作用，我们实际上需要两个比较操作：hashCode 方法来查找数组中的列表（这个如果 hashCode() 和 h 都很快，则工作速度很快）以及我们在遍历列表时需要的 equals 方法。

这就是哈希的大致思路，你会从java.util.Map中认识到put和get方法。当然，上面的实施过于简单化，但它应该说明一切的要点。

当然，这种方法不仅限于字符串，它适用于所有类型的对象，因为方法 hashCode() 和 equals 是顶级类 java.lang.String 的成员。 lang.Object 和所有其他类都继承自该类。

正如您所看到的，两个不同的对象在其 hashCode() 方法中返回相同的值并不重要：上述方法始终有效！但仍然希望它们返回不同的值，以降低 h 产生哈希冲突的机会。我们已经看到，这些通常不能 100% 避免，但是冲突越少，哈希表的效率就越高。在最坏的情况下，所有键都映射到相同的数组索引：在这种情况下，所有对都存储在单个列表中，然后查找值将成为成本与哈希表大小呈线性关系的操作。

Answer 4

hashCode() 值可用于通过使用哈希码作为存储对象的哈希表桶的地址来快速查找对象。

如果多个对象从 hashCode() 返回相同的值，则意味着它们将存储在同一个存储桶中。如果许多对象存储在同一个存储桶中，则意味着平均需要更多比较操作来查找给定对象。

相反，使用 equals() 来比较两个对象以查看它们在语义上是否相等。

Answer 5

据我了解，hashcode方法的工作是创建用于散列元素的桶，以便检索速度更快。如果每个对象返回相同的值，则没有必要进行任何散列。

Answer 6

我不得不认为，对于两个具有相同哈希码的对象来说，这是一种非常低效的哈希算法。