澄清Java实现HashSet/HashMap背后的事实

Question

1.我了解不同的哈希映射机制和处理密钥冲突的方式（开放寻址-线性/二次探测、链接、可扩展哈希等）。哈希集/哈希映射使用哪一种？

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

我知道不能依赖默认实现，因为它将哈希函数建立在不是恒定的内存地址上。

Answer 1

问题1）

JavaHashMap实现使用链接实现来处理冲突。可以将其视为一个链表数组。

问题2

Object有equals和hashCode的默认实现。equals被实现为返回this==其他和hashcode被实现为（所有意图和目的）为每个实例分配一个随机标识符并将其用作hashCode。

由于 Java 中的所有类都扩展了 Object，因此它们都继承了这些实现。

默认情况下，某些类覆盖这些实现<正如您提到的，code>String是一个很好的例子。另一个是集合API中的类，因此＜code＞ArrayList

就实现一个好的哈希码而言，这有点像黑暗艺术。以下是最佳实践的一个很好的总结。

您的最后评论:

我知道不能依赖默认实现，因为它将哈希函数建立在不是恒定的内存地址上。

这是不正确的。< code>hashCode的默认实现是常量，因为它是方法契约的一部分。从Javadoc:

在一个Java应用程序的执行过程中，只要在同一个对象上多次调用hashCode方法，hashCode方法就必须始终返回同一个整数，前提是在对象的equals比较中使用的信息没有被修改。这个整数不需要从一个应用的一次执行到同一应用的另一次执行保持一致。

Answer 2

通过阅读HashMap的源代码，您可以自己回答其中的许多问题。

（提示：你通常可以使用Google找到Java SE类的源代码;例如，搜索“java.util.HashMap source”。

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

锁链。请参阅源代码。（链接到的版本中的第154行）。

Java的HashSet/HashMap如何对对象进行哈希处理？

没有。为此，调用对象的＜code＞hashCode＜/code＞方法。请参阅源代码。（第360行）。

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

>

代码（在我链接到的版本中）使用特殊方法对字符串进行哈希处理。（这似乎是为了允许在平台级别“调整”字符串的哈希。我没有深入研究这个...）

由< code>Object.hashCode()调用返回的hashcode被进一步“打乱”以减少冲突的机会。(看评论！)

如果我现在想对我创建的Java对象进行散列-我需要实现散列函数吗？

你可以做到。

您是否需要这样做取决于您如何为类定义＜code＞equals＜/code＞。具体来说，Java的＜code＞HashMap、＜code＞hash集和相关类对＜code＞hashcode（）和＜code＞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）；即相当于链表的线性搜索。）

或者Java是否有内置的方法来创建哈希代码？

每个类从＜code＞对象方法（除非被重写）。它使用所谓的“身份哈希码”；i、 e.基于对象标识（其引用）的哈希值。这与＜code＞equals（Object）来比较引用。

我知道不能依赖默认实现，因为它将哈希函数建立在不是恒定的内存地址上。

这是不正确的。

默认的hashCode（）方法返回“标识hashcode”。这通常基于某个时间点对象的内存地址，但它不是对象的内存地址。

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

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

最重要的是，默认的 Object.hashCode（） 方法满足我上面列出的所有要求。这是可以信赖的。