18

我知道有一种散列技术应用于键以将其值存储在内存地址中。

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

4

4 回答 4

47

的基本思想HashMap是这样的：

  1. AHashMap实际上是一个包含 Key 和 Value 的特殊对象数组。
  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 号存储桶中。
    • 如果还没有另一对，没关系。
    • 如果有一个 Key 等于我们拥有的 Key，我们删除旧的。
    • 如果有另一个键值对（冲突），我们将新的在旧的之后链接到一个链表中。
  6. 如果后备数组变得太满，那么我们将不得不创建太多的链表，我们创建一个长度加倍的新数组，重新散列所有元素并将它们添加到新数组中，然后处理旧数组。这很可能是 上最昂贵的操作HashMap，因此如果您以前知道的话，您想告诉您Maps将使用多少个存储桶。
  7. 如果有人试图获取一个值，他会提供一个键，我们对其进行散列、修改，然后通过潜在的链表进行精确匹配。

图片由维基百科提供： 图形

在这种情况下，

  • 有一个包含 256 个桶的数组（编号，当然是 0-255）
  • 有五个人。它们的哈希码在通过后mod 256，指向数组中的四个不同的插槽。
  • 你可以看到 Sandra Dee 没有空位，所以她被锁在 John Smith 之后。

现在，如果您尝试查找 Sandra Dee 的电话号码，您将散列她的姓名，将其修改为 256，然后查看存储桶 152。在那里您会找到 John Smith。那不是 Sandra，再看远点……啊哈，Sandra 被锁在 John 身后。

于 2012-06-05T09:45:21.807 回答
4

这里Hash并不意味着MD5Hashing等技术。它是用于存储特定键的内存位置的HashCode 。Object

读数：

这是对 HashMap 如何工作的更清晰的解释？

于 2012-06-05T09:17:40.190 回答
1

作为类中的默认实现 hashCode()函数，Object将内存地址作为哈希值返回，用作HashTable&中的键HashMap。

于 2012-06-05T09:14:20.140 回答
0

经过@Slanec 的回答后，请查看 Java-8 中的 javadoc，因为有重大变化。例如：“TREEIFY”，其中 LinkedList 被转换为 TreeMap，以防达到每个桶的条目数阈值（当前为 8）。

于 2015-10-22T19:44:38.500 回答