Java中的哈希是如何工作的？

Question

我正在尝试了解Java中的哈希技术。例如，如果我想在HashMap中存储一些数据，它是否会有某种基础哈希表与哈希值？或者，如果有人能给出一个好的简单解释哈希是如何工作的，我将不胜感激。

- Langkiller

---

据我理解，在你使用的上下文中，哈希（Hashing）会产生一个值，保证对于两个相等的对象来说这个值是相等的，而对于不相等的对象来说这个值是不相等的。这加速了.contains()和其他调用.equals()方法的问题。一个简单的例子是，如果一个类有成员x和y，那么哈希码可能是71 *（x + 71 * y），但当你重写equals时，IDE会为你生成一个好的哈希码。 - Richard Tingle

但是在计算哈希码后，它确切地放在哪里呢？ 它是否存储在某种底层哈希表中？ - Langkiller

你了解哈希表吗？这并不是一句挖苦的话；说真的，如果你想真正理解哈希如何工作，你需要了解数据结构。维基百科文章和算法设计手册中的解释都非常棒。 - jason

我可以回答这个问题，但维基百科已经有一个关于哈希表的优秀页面，涵盖了一般数据结构的概念 - http://en.wikipedia.org/wiki/Hash_table - Nick Holt

非常感谢！希望我能弄清楚。 - Langkiller

Answer 1

HashMap基本上在内部实现为一个Entry[]数组。如果你了解什么是linkedList，那么这个Entry类型就是一个linkedList实现。这个类型实际上存储了键和值。

要将元素插入到该数组中，需要索引。如何计算索引？这就是哈希函数（hashFunction）派上用场的地方。在这里，您将一个整数传递给这个哈希函数。现在，为了获得这个整数，Java会调用要添加为映射键的对象的hashCode方法。这个概念被称为预哈希（preHashing）。

现在一旦知道了索引，就可以将元素放置在这个索引上。这基本上被称为BUCKET，因此如果元素被插入到Entry [0]中，则表示它落在bucket 0下。

现在假设哈希函数以相同的索引0返回另一个要插入为映射键的对象。这就是调用equals方法的地方，即使equals返回true，也意味着存在hashCollision。因此，在此情况下，由于Entry是链接列表实现，因此在此索引上，在已经可用的条目的链接列表中，您向此链接列表添加了一个节点(Entry)。因此，在哈希冲突时，通过链接列表在特定索引上存在不止一个元素。

当您要从映射中获取键时，也适用相同的情况。根据哈希函数返回的索引，如果只有一个条目，则返回该条目，否则调用条目的链接列表的equals方法。

希望这有助于了解它是如何工作的 :)

- zerocool

Answer 2

如果我想在哈希映射中存储一些数据，它会有某种基础的哈希表和哈希值吗？ HashMap 是一种哈希表（HashTable 是另一种）。它们通过使用 HashMap 键类型提供的 hashCode() 和 equals(Object) 方法来工作。根据您希望键如何运作，您可以使用由 java.lang.Object 实现的 hashCode/equals 方法...或者您可以覆盖它们。

或者，如果有人能够给出一个关于哈希如何工作的好而简单的解释，我将不胜感激。

我建议您阅读维基百科页面 Hash Tables 以了解它们的工作原理。（顺便说一下，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.

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

---

但是哈希值存储在哪里呢？它不是HashMap的一部分，那么与HashMap相关联的数组在哪里呢？

哈希值通常不会被存储。相反，它们会在需要时计算。

在HashMap类的情况下，每个键的哈希码实际上被缓存在条目的Node.hash字段中。但这是一种性能优化...为了使哈希链搜索更快，并避免在调整哈希表大小时重新计算哈希值。但如果您想要这种理解水平，您真的需要阅读源代码而不是提问。

- Stephen C

---

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

Answer 3

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

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

- Jack

Answer 4

这是Java中最基本的合约：.equals()/.hashCode()合约。 其中最重要的部分是，被认为相等的两个对象应该返回相同的.hashCode()。

反之则不成立：不被认为相等的对象可能会返回相同的哈希码。但这种情况应该尽可能少发生。考虑以下.hashCode()实现，虽然完全合法，但却是一种最糟糕的实现：

@Override
public int hashCode() { return 42; } // legal!!

这个实现虽然遵守了合约，但基本上是无用的...因此，一个好的哈希函数非常重要。

现在：Set 合约规定一个 Set 不应包含重复元素; 然而，Set 实现的策略留给了实现者。如果您查看 Map 的 javadoc，您会注意到它的键可以通过一个叫做 .keySet() 的方法来检索。因此，在这方面，Map 和 Set 是非常相关的。

如果我们以 HashSet（最终会涉及到 HashMap）为例，它依赖于 .equals() 和 .hashCode()：在添加一个元素时，它首先计算该元素的哈希码，然后根据该哈希码，尝试将该元素插入到给定的桶中。相比之下，TreeSet（和 TreeMap）则依赖于元素的自然排序（请参阅 Comparable）。

但是，如果要插入一个对象，并且该对象的哈希码会触发其插入到非空哈希桶中（请参见上面合法但有问题的 .hashCode() 实现），那么就会使用 .equals() 来确定该对象是否真正唯一。

请注意，在内部，HashSet 是一个 HashMap...

- fge

---

我认为“equals”定义等价关系的要求更加基本，但“hashCode”函数也非常重要。可能有助于说明，“hashCode”应该尽可能快地返回不同对象的不同数字，并且不违反匹配值必须具有匹配哈希的要求。每次发生哈希冲突都会减慢散列集合查找方法的速度。如果一个包含50,000个项的集合有十几个冲突，那么速度会稍微变慢。如果集合中的20,000个项都返回相同的哈希，则速度会大大降低。 - supercat

@supercat 是的，我知道，我已经用一个例子说明了不应该做什么 ;) - fge

返回一个在每次调用时递增的静态计数器比返回42更容易出错。在某些情况下，如果类型实现了可变值相等性，则返回一个常量（尽管可能不如42或8675309“受欢迎”）可能是明智的选择。如果类型具有可变的“名称”字段，并且如果对象的“名称”匹配则被视为“相等”，则如果在HashSet中存储对象的名称没有更改，则让hashCode()返回name.hasCode()是可行的，但是返回一个常量hashCode将允许找到所有具有当前名称的对象，即使它们在存储时具有其他名称。 - supercat

@supercat 我都知道这些...而且，如果你依赖于.hashCode()/.equals()与可变字段，那么你有一个更深层次的问题要处理 ;) 我没有这个问题，因为我创建的所有实例都是不可变的，或者如果它们不是，就留给Object处理.... - fge

我只是在评论你的陈述中说返回一个常量是“最糟糕的hashCode实现”；它并不是，有时候这样做可能是合理的（例如，如果需要在包装hashSet<T>的类中存储对象，但线性搜索集合类型可能更好）。实际上，快速返回一个常量甚至不是最糟糕的“合法”hashCode方法；一个需要很长时间才能得出每个实例相同答案的方法会更糟糕[顺便说一句，我认为.NET的某些类型意外地就是这样做的]。 - supercat

Answer 5

哈希是一种在对变量/对象的属性应用任何函数/算法后为其分配唯一代码的方法。

- Kamal Kashyap

Answer 6

HashMap在Map.Entry静态嵌套类实现中存储键值对。 HashMap使用哈希算法，并在put和get方法中使用hashCode()和equals()方法。

当我们通过传递键值对调用put方法时，HashMap使用Key hashCode()进行哈希处理以找到 存储键值对的索引。Entry存储在LinkedList中，因此如果已经存在条目，则使用equals()方法检查是否已经存在传递的键，如果是，则覆盖 值，否则创建一个新条目并存储此键值Entry。

当我们通过传递Key调用get方法时，它再次使用hashCode()查找索引 在数组中，然后使用equals()方法查找正确的Entry并返回其值。 下面的图像将清楚地解释这些细节。

HashMap的其他重要知识点包括容量、负载因子和阈值调整。HashMap的初始默认容量为16，负载因子为0.75。阈值是容量乘以负载因子，每当我们尝试添加一个条目时，如果映射的大小大于阈值，HashMap会将映射内容重新哈希到一个具有更大容量的新数组中。容量始终是2的幂，所以如果你知道你需要存储大量的键值对，例如从数据库缓存数据，最好使用正确的容量和负载因子来初始化HashMap。

- mayur biradar