gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-29 07:04:52 25 4
gpt4 key购买 nike

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

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

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

最佳答案

您可以通过阅读 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的HashMapHashSet及相关类对hashcode()equals(Object)提出了如下要求:

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

(出于性能原因的最后一个要求。如果您的哈希函数“很差”,导致不同的键很可能对相同的哈希码进行哈希处理,那么您会遇到很多冲突。哈希链将变得不平衡,并且您不会获得散列表操作通常预期的平均 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() 方法满足我上面列出的所有要求。它可以值得信赖。

关于java - 阐明 Java 实现 HashSet/HashMap 背后的事实,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20849809/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com