哈希算法与HashMap

Question

在堆栈溢出和网络中有几个主题，我无法清楚地理解它们。我在尼可拉斯的“堆积如山”中找到了这个答案，他的陈述让我对这个话题有了一些有意义的见解。

一些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. 那个哈希表是什么？它是一个对象数组吗?如果是的话，每个对象都有一个键、value1和一个引用属性吗？

任何人都可以一步一步地重新解释上面的图表.我无法理解HashMap背后的散列机制.

Answer 1

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

1. 让你有一些搜索的钥匙。例如，键只是文本字符串，比如"hello“。
2. 让我们为这个字符串计算一些“校验和”--例如，只需将ASCII符号代码相加就可以了。让我们(例如，我实际上没有数)这个总数是1009。
3. 让我们有固定大小的数组，例如SZ=10。将这个数组命名为"hash_table“。每个数组元素都包含桶--这是一组可能的键。
4. 因此，我们可以通过以下方法计算数组中的偏移量索引，即哈希表： 偏移量=和% SZ = 1009 % 10 = 9；
5. 让我们通过以下方式将“你好”这个词存入街头艺人#9： Hash_table9.add_to_list(“你好”)；

在那里，我们只有单键"hello"，存储在单元格hash_table9中；

1. 想象一下，需要插入第二个键，例如，"world“。让我们计算和，它将是37。同样，计算偏移量= 37 % 10 = 7。因此，通过该算法，我们将键"world“放入hashtable7中。
2. 碰撞。想象一下，你决定添加第三个字-键，“碰撞”让这个词的和将是3007。当你计算偏移量时，它将是7。因此，单词“冲突”必须存放在桶中，在那里已经存在单词"world“。这样就可以了。您只需在链接列表(头或尾)中添加具有世界“冲突”的元素。所以： hashtable7 -> "world“-> "collistion”->NULL；hashtable9 -> "hello“->NULL；
3. 当您需要搜索一个键"hello“时，您再次计算校验和，它将再次是1009。然后，计算偏移量= 9，然后直接转到桶#9，然后，迭代链接列表，在那里你会找到你的单词"hello“。与“世界”或“碰撞”类似的情况。

当您搜索表中省略的word时，您将转到空桶或桶，后者不包含您的键。所以，搜索失败。

如果哈希表太宽(例如，大小与字典相同)，则平均桶大小为~1元素(如果散列函数具有良好的扩展性)。所以，搜索一个键将是快速的-只需计算哈希和，转到桶，并迭代桶中的1-2个元素。

第二，我将回答你的问题：

1. 偏移量-只是数组中的索引。数组是“哈希表”。每个数组元素都包含指向链表的指针，包含存储在同一个桶中的键。
2. 桶方案中的哈希表--只是数组，包含指向桶头的指针。使用另一个散列方案(例如，多个散列，等等)-它可以包含自己的对象，而不需要链接列表。