6

我正在尝试找出有关 java 中的散列的一些事情。例如，如果我想在哈希图中存储一些数据，它会有某种带有哈希值的底层哈希表吗？或者，如果有人可以对哈希的工作原理给出一个简单而简单的解释，我将不胜感激。

4

6 回答 6

10

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

要将元素插入数组，您需要索引。你如何计算指数？这就是散列函数（hashFunction）发挥作用的地方。在这里，您将一个整数传递给此哈希函数。现在为了获取这个整数，java 调用了对象的hashCode方法，该对象被添加为映射中的键。这个概念称为 preHashing。

现在，一旦知道索引，您就可以将元素放在该索引上。这基本上称为BUCKET，因此如果在 Entry[0] 处插入元素，则您说它属于存储桶 0。

现在假设 hashFunction 返回相同的索引，比如 0，对于您想要作为键插入到映射中的另一个对象。这是调用equals方法的地方，如果 even equals 返回 true，则意味着存在hashCollision。所以在这种情况下，由于 Entry 是一个链表实现，在这个索引本身上，在这个索引上已经可用的条目上，你再向这个链表添加一个节点（条目）。所以底线是，在 hashColission 上，通过链表在特定索引处有多个元素。

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

希望这有助于了解它的工作原理:)

于 2013-06-19T16:37:30.030 回答
4

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

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

或者，如果有人可以对哈希的工作原理给出一个简单而简单的解释，我将不胜感激。

我建议您阅读Hash Tables上的 Wikipedia 页面以了解它们的工作原理。（FWIW，HashMapandHashTable类使用“带链表的单独链接”，以及其他一些调整来优化平均性能。）

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

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

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

当您实现hashcodeandequals方法时，您需要以满足以下约束的方式执行此操作，以使哈希表正常工作：

 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和equals方法Object都是基于目标对象的身份。

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

通常不存储散列值。而是根据需要计算它们。

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

于 2013-06-19T16:31:44.177 回答
4

Java 中的散列值是由对象提供的public int hashCode()，其实现在类中声明，Object并为所有基本数据类型实现。一旦您在自定义数据对象中实现了该方法，您就无需担心这些方法如何用于 Java 提供的各种数据结构中。

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

于 2013-06-19T16:15:01.070 回答
2

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

反之则不然：不相等的对象可能返回相同的哈希码。但它应该尽可能少发生。考虑下面的.hashCode()实现，虽然完全合法，但它是一个可能存在的被破坏的实现：

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

虽然这个实现遵守合同，但它几乎没有用......因此，一个好的散列函数开始的重要性。

现在：Set合同规定 aSet不应包含重复的元素；但是，Set实施的策略是……好吧，交给实施。您会注意到，如果您查看 的 javadoc Map，可以通过名为 的方法检索其键.keySet()。因此，Map和Set这方面的关系非常密切。

如果我们以a HashSet（最终是HashMap）的情况为例，它依赖于.equals()and .hashCode()：添加一个item时，它首先计算这个item的hash code，并根据这个hash code尝试将这个item插入到给定的bucket中。相反， a TreeSet(and TreeMap) 依赖于元素的自然排序（参见Comparable）。

但是，如果要插入一个对象并且该对象的哈希码将触发其插入到非空哈希桶中（参见.hashCode()上面的合法但损坏的实现），则.equals()用于确定该对象是否真的唯一。

请注意，在内部， aHashSet是HashMap...

于 2013-06-19T16:24:22.307 回答
0

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

当我们通过传递键值对调用 put 方法时，HashMap 使用带有散列的 Key hashCode() 来找出存储键值对的索引。条目存储在 LinkedList 中，因此如果已经存在条目，则使用 equals() 方法检查传递的键是否已存在，如果存在则覆盖值，否则创建新条目并存储此键值条目.

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

关于 HashMap 需要了解的其他重要事项是容量、负载因子、阈值调整大小。HashMap 初始默认容量为 16，加载因子为 0.75。阈值是容量乘以负载因子，每当我们尝试添加条目时，如果映射大小大于阈值，HashMap 会将映射的内容重新散列到具有更大容量的新数组中。容量始终是 2 的幂，因此如果您知道需要存储大量键值对，例如在缓存数据库中的数据时，最好使用正确的容量和负载因子初始化 HashMap。

于 2018-06-26T06:34:50.917 回答
0

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

于 2017-07-27T07:28:44.077 回答