java - 阐明 Java 实现 HashSet/HashMap 背后的事实

Question

1. 我了解不同的 HashMap 机制以及处理 key 冲突的方式(开放寻址 - 线性/二次探测、链接、可扩展哈希等。HashSet/HashMap 使用哪一种？

2。 我意识到一个好的 HashMap 依赖于一个好的哈希函数。 Java 的 HashSet/HashMap 是如何对对象进行哈希处理的？我知道有一个散列函数，但到目前为止，对于字符串，我还不需要实现它。如果我现在想对我创建的 Java 对象进行哈希处理，我需要实现哈希函数吗？或者 Java 是否具有创建哈希码的内置方法？

我知道不能依赖默认实现，因为它基于不是常量的内存地址来计算哈希函数。

Answer 1

您可以通过阅读 the source code for HashMap 自己回答其中的许多问题。 .

(提示:您通常可以使用 Google 找到 Java SE 类的源代码；例如搜索“java.util.HashMap source”。)

I understand the different hash map mechanisms and the ways in which key collisions are handled (either open addressing -linear/quadratic probing, chaining, extendable hashing, etc. Which one does HashSet/HashMap make use of?

链接。查看源代码。 (我链接到的版本中的第 154 行)。

How does Java's HashSet/HashMap hash the objects?

事实并非如此。调用对象的 hashCode 方法来执行此操作。查看源代码。 (第 360 行)。

如果您查看代码，您会发现一些有趣的问题:

• 代码(在我链接到的版本中)使用特殊方法散列字符串。 (这似乎是为了允许在平台级别“调整”字符串的散列。我没有深入研究这个......)

• Object.hashCode() 调用返回的哈希码被进一步“加扰”以减少冲突的机会。 (阅读评论!)

What if I now want to Hash a Java Object that I create - do I need to implement the hash function?

你可以做到。

您是否需要这样做取决于您如何为类定义equals。具体来说，Java的HashMap、HashSet及相关类对hashcode()和equals(Object)提出了如下要求:

1. 如果 a.equals(b) 则 a.hashCode() == b.hashCode()。
2. 当 a 在 HashSet 中或者是 HashMap 中的键时，a.hashCode() 返回的值 不得更改。
3. 如果 !a.equals(b)，那么 a.hashCode() == b.hashCode() 的概率应该很低，尤其是如果 a 和 b 可能是应用程序的哈希键。

(出于性能原因的最后一个要求。如果您的哈希函数“很差”，导致不同的键很可能对相同的哈希码进行哈希处理，那么您会遇到很多冲突。哈希链将变得不平衡，并且您不会获得散列表操作通常预期的平均 O(1) 性能。在最坏的情况下，性能将为 O(N)；即相当于链表的线性搜索。)

Or does Java have a built in way of creating a hash code?

每个类都从 Object 继承一个默认的 hashCode() 方法(除非它被覆盖)。它使用所谓的“身份哈希码”；即基于对象身份(其引用)的哈希值。这与 equals(Object) 的默认实现匹配......它只使用 == 来比较引用。

I know that the default implementation cannot be relied on as it bases the hash function on the memory address which is not constant.

这是不正确的。

默认的 hashCode() 方法返回“身份哈希码”。这通常基于对象在某个时间点的内存地址，但它不是对象的内存地址。

特别是，如果一个对象被垃圾收集器移动，它的“身份哈希码”保证不会改变。是的。没错，它不会改变......即使对象被移动了!

^{(他们如何有效地实现这一点相当聪明。有关详细信息，请参阅 https://stackoverflow.com/a/3796963/139985。)}

底线是默认的 Object.hashCode() 方法满足我上面列出的所有要求。它可以值得信赖。