java - 哈希算法和HashMap

Question

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 |
                                                +----------------------+

What hashing function does Java use to implement Hashtable class?

Map aMap = new HashMap();
aMap.put(key,value);

1. 谁能解释一下“什么是偏移量及其值？”。哪里偏移值被映射？
2. 那个哈希表是什么？它是一个对象数组吗？如果是的话，每个对象都是对象有一个键、值1和一个引用属性？

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

Answer 1

首先，让我解释一下哈希搜索的想法:

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

2. 让我们计算这个字符串的一些“校验和” - 举个简单的例子，只需通过将符号的 ASCII 代码相加。让我们(例如，我实际上没有数过)这个总和是 1009。

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

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

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

5. 让我们将单词“hello”存入街头艺人#9:

   hash_table[9].add_to_list("hello");

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

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

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

   hashtable[7] -> “世界” -> “碰撞” -> NULL;hashtable[9] -> “你好” ->NULL;

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

当您搜索表中省略的单词时，您会转到空存储桶或不包含您的 key 的存储桶。所以，搜索失败。

如果哈希表太宽(例如，大小与字典相同)，则平均存储桶大小将约为 1 个元素(如果哈希函数具有良好的扩展性)。因此，搜索键会很快 - 只需计算哈希和，转到存储桶，然后迭代存储桶中的 1-2 个元素。

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

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

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