hash table , 非空slot 已经包含key , 奇数据值被新数据值替换

Question

我正在 python 中学习哈希 table，这里出现一个问题。

当哈希函数开始时，我应该生成一个空的"map"哈希list.But为什么"nonempty slot already contains the key ,the odd data value is replaced with the new data value"，它不是应该找到下一个空槽并存储在那里，为什么替换？

https://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

hashfunction implements the simple remainder method. The collision resolution technique is linear probing with a “plus 1” rehash function. The put function (see Listing 3) assumes that there will eventually be an empty slot unless the key is already present in the self.slots. It computes the original hash value and if that slot is not empty, iterates the rehash function until an empty slot occurs. If a nonempty slot already contains the key, the old data value is replaced with the new data value. Dealing with the situation where there are no empty slots left is an exercise.

Answer 1

首先，我们需要区分hash value、key和value。

Hash value是hash中slot的IDtable，由hash函数生成

Key 是您要映射的数据。

value 是您要映射到的数据。

因此，映射意味着您有一个引用某个值的唯一键，并且这些值不一定不同。

当您尝试使用 key 和 value 添加新插槽时，put 函数将执行以下操作：

对key进行散列得到列表中slot的ID，如果这个ID的slot为空，则插入成功，否则有两条路径：

1- 找到的槽不为空但它的键不等于新键，这意味着 2 个不同的键具有相同的 hash value，所以这被认为是冲突并且由您发送的 link 中提到的方法。

2- 找到的插槽不为空，但其密钥等于新密钥，这意味着您正在更新此插槽，因此它将用新的替换旧的value。

示例：如果哈希包含这些槽：

"foo": 5
"bar": 7

然后你尝试插入hash["foo"] = 10，这将散列键（foo）并在散列table（列表）中找到它的插槽ID，它也会找到存在一个带有键 foo 的插槽，因此它将替换值并且散列 table 将变成这样：

"foo": 10
"bar": 7

但是，如果您尝试插入 hash["abc"] = 7，这将散列键 abc，并且如果 hash value 映射到一个键不同于 abc，在这种情况下，put 函数将认为这是一个冲突，并会尝试找到另一个空槽。

Answer 2

将哈希 Table 视为 python 字典。假设我们创建了一个字典

dictionary = {
    "a":10,
    "b":20,
}

这里 "a" 是键，10 是它的值。所以如果我们更新

dictionary['a'] = 15

它不会将其放入新插槽，而是更新该位置 'a'。

A python 字典是哈希表的一个实现。所以我举了这个例子。因此，对于同一个键，如果它已经存在，我们就更新它。

要了解有关 python 字典如何实现的更多信息，您可以查看此 post

hash table , 非空slot 已经包含key , 奇数据值被新数据值替换

hash table , nonempty slot already contains the key ,the odd data value is replaced with the new data value

python

hash

hashtable

hashmap

data-structures