哈希表和哈希映射的键值是如何存储在内存中的？

Question

我知道在将键存储到内存地址时会应用哈希技术。

但我不明白碰撞是如何发生的？Java使用哪种哈希算法来创建内存空间？是MD5吗？

- Sahal

Answer 1

HashMap 的基本思想如下：

1. HashMap 实际上是一个特殊对象的数组，该数组同时保存键和值。
2. 该数组有一定数量的桶（槽），例如16个。
3. 哈希算法由每个对象都有的 hashCode() 方法提供。因此，在编写新的 Class 时，您应注意适当的 hashCode() 和 equals() 方法的实现。默认情况下（Object 类的方法），它将内存指针作为数字。但对于我们大多数想使用的类来说，这并不好。例如，String 类使用一种从字符串中所有字符生成哈希的算法 - 可以这样理解：hashCode = 1.char + 2.char + 3.char...（简化）。因此，即使两个相等的字符串位于内存中的不同位置，它们也具有相同的 hashCode()。
4. hashCode() 的结果，比如 "132"，就是如果我们有一个那么大的数组，对象应该存储在哪个桶中的编号。但我们没有，我们的数组只有16个桶。因此，我们使用明显的计算 'hashcode % array.length = bucket' 或 '132 mod 16 = 4' 并将键值对存储在桶编号为4的位置。
5. • 如果没有其他键值对，那就没问题。
   • 如果存在一个键等于我们拥有的键，则删除旧的键值对。
   • 如果存在另一个键值对（冲突），则将新键值对链接到旧键值对后面形成链表。

如果支持数组变得太满，我们会有太多的链接列表，那么我们就会创建一个两倍长度的新数组，重新计算所有元素的哈希值并将它们添加到新数组中，然后我们销毁旧的数组。这很可能是HashMap上最昂贵的操作，因此如果您知道要使用多少个桶，您需要告诉您的Map。

如果有人尝试获取值，他会提供一个键（key），我们对其进行哈希运算、取模，然后遍历潜在的链表以寻找确切的匹配。

维基百科上的图片：

在这个例子中，

• 有一个包含256个桶的数组（当然编号为0-255）
• 有五个人，将他们的哈希码通过mod 256处理之后，指向数组中的四个不同位置。
• 你可以看到桶152已经没有空闲位置了，所以桶152后面的Sandra Dee被链接在John Smith之后。

现在，如果你尝试查找Sandra Dee的电话号码，你会对她的名字进行哈希运算并对256取模，然后查看桶152。在那里，你会找到John Smith。这不是Sandra，继续查找...啊哈，在John之后链接了Sandra。

- Petr Janeček

---

如果您找到任何带有图片解释的链接，请在此处放置。那将非常有帮助。 - Sahal

完成。这段内容来自维基百科的文章（http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_list_heads）。 - Petr Janeček

现在，当你了解这一点时，这就是String的真正hashCode()实现。还有一些关于hashCode()中素数选择的链接，包括一些随机链接。 - Petr Janeček

不幸的是，这并不是 HashMap 实际上所做的。首先，它将 hashCode() 的高16位和低16位进行异或运算。HashTable 也不是这样做的。 - user207421

@EJP 对的。它使用异或运算而不是使用模运算，因此仅在高位哈希不同的密钥将始终发生冲突，没有这种技术。当溢出条目的链接列表变得太长时，它可以将冲突键树化到单个桶中。在实践中，可能有数十个额外的实现细节有助于使HashMap非常快。但显然，这个答案并不包含它们，以免混淆OP。我相信他当时是个新手，需要了解算法基础，而不是低级优化。 - Petr Janeček

Answer 2

这里的“哈希”并不是指哈希技术，例如MD5。它是用于存储特定键的Object的内存位置的HashCode。

阅读材料：

• Java hashmap如何工作？
• Java中HashMap的工作原理

这个更加清晰地解释了HashMap的工作原理吗？

- Asif

---

例如，如果您在HashTable中有100个记录，并且您想查找一个名为“ Men In Black”的键，它会多快地找到它的值？我认为不需要超过一次迭代来找到它Q(1)。我的感觉是编译器会创建“ Men In Black”的哈希码，并将其存储在特定的内存位置中。稍后当我们尝试检索它时，它使用哈希码来查找它的值.....我错过了什么吗？如果不是这种情况，那么键搜索的运行时间如何是一，即Q(1)？ - Sahal

Map中的键存储在数组（内存）的给定位置下。位置由运行时（而不是编译器）设置，使用转换后对象的哈希码和数组长度的算法。检索元素所需的时间为O(1)，不需要任何迭代。 - Damian Leszczyński - Vash

它不是内存位置的 'hashCode'。'hashCode' 通过涉及进一步计算的过程 产生 内存位置。答案的其余部分仅包含链接。 - user207421

Answer 3

作为默认实现，Object类中的 hashCode() 函数返回内存地址，用作 HashTable 和 HashMap 中作为键的哈希值。该函数与 IT 相关。

- ejb_guy

---

例如，如果您在HashTable中有100个记录，并且您想查找一个名为'Men In Black'的键，它会多快地找到它的值？我认为不需要超过一次迭代来找到它Q(1)。我的感觉是编译器会创建'Men In Black'的哈希码并将其存储在特定的内存位置中。稍后当我们尝试检索它时，它使用哈希码来查找它的值.....我是否遗漏了什么？如果不是这种情况，那么键搜索的运行时间如何是一，即Q(1)？ - Sahal

它将查看存储有值为“Men In Black”的String对象的内存位置。这个内存位置成为哈希码，用于检索值。理想情况下，它应该是Q(1)，但通常由于冲突和优化内存使用，会有轻微变化，对于所有实际目的而言，可以视为Q(1)。变化取决于从哈希码计算的索引处桶中的项目数。并不是所有哈希映射中的100个项目都具有唯一的索引，这是不必要的。 - ejb_guy

此外，String类有它自己的hashCode()实现，它不是使用内存位置，而是使用算法从字符串中的实际字符生成哈希值。 - Petr Janeček

哎呀，我有点困惑了。对于字符串，它会从自己的键创建哈希值...但是对于整数键呢？ - Sahal

@Sahal 我想你今天已经知道了，但是每个对象都有自己的 hashCode 方法，甚至包括 Integer（其中 hashCode == value）。 - Petr Janeček

Answer 4

阅读完@Slanec的答案后，一定要查看Java-8的javadoc，因为有重大变化。例如：'TREEIFY'，当每个桶（目前为8）中的条目数量达到阈值时，LinkedList将转换为TreeMap。

- Biman Tripathy

---

这个问题是关于 HashMap 和 HashTable 的，而不是关于 TreeMap 的，因为 TreeMap 根本不使用哈希。 - user207421

@EJP 这里的作者意思是，如果一个单一的 bin 发生了大量的碰撞，那么在某个时候，与 TreeMap 类似（具有明显和不明显的差异，例如非可比较键按其 hashCode() 排序），碰撞的键会被重组成树形结构，而不是一个单链表。这有助于防止许多碰撞的灾难性情况，在这种情况下，Java 8 之前的 HashMap 会缓慢地退化为一个链接列表。 - Petr Janeček