1

在 stackoverflow 和 web 中有几个关于此的主题，我无法清楚地理解它们。我在 Nicklas 的 stackoverflow 和他的代表中找到了这个答案，这让我对这个话题有了一些有意义的见解。

一些 ASCII 艺术

key.hashCode()
     |
     | 32-bit value
     |                          hash table
     V                        +------------+    +----------------------+
HashMap.hash() ----+          | reference  | -> | key1 | value1 | null |
                   |          |------------|    +----------------------+
                   |          | null       |
                   | offset   |------------|    +---------------------+
                   +--------> | reference  | -> | key1 | value1 | ref |
                              |------------|    +---------------------+
                              |    ....    |                       |
                                                  +----------------+
                                                  V
                                                +----------------------+
                                                | key2 | value2 | null |
                                                +----------------------+

Java 使用什么散列函数来实现 Hashtable 类？

Map aMap = new HashMap();
aMap.put(key,value);
  1. 谁能解释一下'什么是偏移量及其价值？偏移值在哪里被映射？
  2. 那个哈希表是什么？它是一个对象数组吗？如果是，每个对象是否都有一个键、值 1 和一个引用属性？

任何人都可以一步一步地重新解释上图。我无法理解 HashMap 背后的哈希机制。

4

1 回答 1

6

首先，让我解释一下哈希搜索的概念：

  1. 让您有一些搜索键。例如，key 只是文本字符串，如“hello”。

  2. 让我们为这个字符串计算一些“校验和”——举个简单的例子，只需将符号的 ASCII 码相加即可。让我们（例如，我没有实际计算）这个总和是 1009。

  3. 让我们有固定大小的数组，例如 SZ=10。将此数组命名为“hash_table”。每个数组元素都包含 BUCKET——这是一组可能的键。

  4. 因此，我们可以通过以下方式计算 OFFSET - 数组中的索引，即哈希表：

    偏移量 = 总和 % SZ = 1009 % 10 = 9；

  5. 让我们通过以下方式将“你好”这个词存入 busker #9：

    hash_table[9].add_to_list("你好");

在那里，我们只有一个键“hello”，存储在单元格 hash_table[9] 中；

  1. 想象一下，需要插入第二个键，例如“world”。让我们计算总和，它将是 37。同样，计算偏移量 = 37 % 10 = 7。因此，通过该算法，我们将密钥“世界”存入哈希表 [7]。

  2. 碰撞。想象一下，你决定添加第 3 个词键，“collision”，让这个词的总和为 3007。当你计算偏移量时，它会是 7。所以，词“collision”必须存入桶中，其中已经存在词“世界”。还行吧。您只需将具有世界“碰撞”的元素添加到链接列表（头部或尾部）中。所以：

    哈希表[7] -> “世界” -> “碰撞” -> NULL；哈希表[9]->“你好”->NULL；

  3. 当您需要搜索键“hello”时，您再次计算校验和，它将再次为 1009。此后，您计算偏移量 = 9，并直接转到 #9 存储桶。并且，迭代链接列表，你会在那里找到你的单词“hello”。与“世界”或“碰撞”类似的情况。

当您搜索表中省略的单词时，您会转到空桶或不包含您的密钥的桶。所以，搜索不成功。

如果您使哈希表太宽（例如，大小与您的字典相同），则平均桶大小将是 ~1 个元素（如果哈希函数具有良好的传播）。因此，搜索密钥会很快——只需计算哈希和，转到存储桶，然后迭代存储桶中的 1-2 个元素。

第二 - 我会回答你的问题：

  1. 偏移量 - 只是数组中的索引。数组是一个“哈希表”。每个数组元素包含指向链表的指针，包含键，存储在同一个桶中。

  2. 桶方案中的哈希表 - 只是数组，包含指向桶头的指针。使用另一种散列方案（例如，多重散列等） - 它可以包含对象本身，而不包含链接列表。

于 2013-09-24T23:10:15.780 回答