java中的散列如何工作？

Question

我试图在java中找出关于哈希的东西.例如,如果我想在hashmap中存储一些数据,它是否会有一些带有hashvalues的底层哈希表？或者,如果有人可以对哈希的工作方式做出一个简单明了的解释,我会非常感激.

Answer 1

HashMap基本上在内部实现为Entry []的数组.如果你理解什么是linkedList,那么这个Entry类型只不过是一个链表实现.这种类型实际上存储了键和值.

要将元素插入数组,您需要索引.你如何计算指数？这是散列函数(hashFunction)出现的地方.在这里,您将一个整数传递给此哈希函数.现在为了获得这个整数,java给出了一个对象的hashCode方法的调用,该方法被添加为地图中的一个键.这个概念叫做preHashing.

现在,一旦知道索引,就将元素放在此索引上.这基本上称为BUCKET,因此如果在Entry [0]中插入了元素,则表示它属于桶0.

现在假设hashFunction为您想要在地图中插入的另一个对象返回相同的索引,如0.这是调用equals方法的地方,如果even equals返回true,则简单意味着有一个hashCollision.因此,在这种情况下,由于Entry是一个链接列表实现,在此索引本身上,在此索引的已有条目上,您将向该链接列表添加一个节点(Entry).所以底线,在hashColission上,通过链表在特定索引上有多个元素.

当您谈论从地图获取密钥时,将应用相同的情况.基于hashFunction返回的索引,如果只有一个条目,则在条目的链表上返回该条目,调用equals方法.

希望这有助于内部工作方式:)

Answer 2

例如，如果我想在哈希图中存储一些数据，它是否会有某种带有哈希值的底层哈希表？

AHashMap 是哈希表的一种形式（也是HashTable另一种形式）。它们通过使用s 键类型提供的hashCode()和方法来工作。根据您希望按键的行为方式，您可以使用...实现的/方法，也可以覆盖它们。equals(Object)HashMaphashCodeequalsjava.lang.Object

或者，如果有人能够对哈希的工作原理给出一个很好且简单的解释，我将非常感激。

我建议您阅读有关哈希表的维基百科页面以了解它们的工作原理。（FWIW，HashMap和HashTable类使用“带有链表的单独链接”以及其他一些调整来优化平均性能。从 Java 8 开始，优化包括将长哈希链转换为二叉树。）

哈希函数的工作原理是将对象（即“键”）转换为整数。如何做到这一点取决于实施者。但一种常见的方法是将对象字段的哈希码组合起来，如下所示：

  hashcode = (..((field1.hashcode * prime) + field2.hashcode) * prime + ...)

其中prime是一个较小的素数，例如31。关键是您可以获得不同键的散列码值的良好分布。你不想要的是很多键都散列到相同的值。这会导致“冲突”并且不利于性能。

当您实现hashcode和equals方法时，您需要满足以下约束才能使哈希表正常工作：

 1. O1.equals(o2) => o1.hashcode() == o2.hashcode()
 2. o2.equals(o2) == o2.equals(o1)
 3. The hashcode of an object doesn't change while it is a key in a hash table.

还值得注意的是，提供的默认值hashCode和方法是基于目标对象的身份的。equalsObject

“那么哈希值存储在哪里呢？它不是HashMap的一部分，那么HashMap是否有一个关联的数组呢？”

通常不存储哈希值。相反，它们是根据需要计算的。

对于类来说HashMap，每个键的哈希码实际上缓存在条目的Node.hash字段中。但这是一种性能优化……使哈希链搜索更快，并避免在调整哈希表大小时重新计算哈希值。但如果你想要这种程度的理解，你真的需要阅读源代码而不是提出问题。

Answer 3

public int hashCode()Java中的哈希值是由对象通过在类中声明的实现来提供的Object，并且它是针对所有基本数据类型实现的。一旦您在自定义数据对象中实现了该方法，您就无需担心这些方法在 Java 提供的各种数据结构中的使用方式。

注意：实施该方法还需要public boolean equals(Object o)以一致的方式实施。