哈希表，非空槽已包含密钥，奇数数据值被新数据值替换

Question

我在python中学习哈希表，这里有一个问题。

当哈希函数开始时，我应该在列表中生成一个空的“map”哈希。但是为什么“非空槽已经包含密钥，奇数数据值被新数据值替换”，是不是应该找到下一个空槽并存储在那里，为什么要更换？

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

hashfunction实现简单的余数方法。冲突解决技术是线性探测，具有“加1”重新散列功能。 put函数（参见清单3）假定最终将有一个空槽，除非self.slots中已存在该键。它计算原始哈希值，如果该槽不为空，则迭代rehash函数，直到出现空槽。如果非空槽已包含密钥，则旧数据值将替换为新数据值。处理没有空槽的情况是一项练习。

Answer 1

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

Hash value是哈希表中槽的ID，它由哈希函数生成。

Key是您要映射的数据。

value是您要映射到的数据。

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

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

它具有获取列表中插槽ID的密钥，如果具有此ID的插槽为空，则插入成功完成，否则有两个路径：

1-找到的插槽不是空的，但是它的键不等于新键，这意味着2个不同的键具有相同的hash value，因此这被认为是碰撞，并且它通过您发送的链接中提到的方式解决。

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

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

"foo": 5
"bar": 7

然后你试图插入hash["foo"] = 10，这将散列密钥（foo）并在散列表（列表）中找到它的插槽ID，它也会发现存在一个带有密钥foo的插槽，因此它将替换值和哈希表将变成这样：

"foo": 10
"bar": 7

但是如果你试图插入hash["abc"] = 7，这将散列密钥abc，如果hash value映射到一个非空的槽，其密钥不同于abc，在这种情况下put函数会认为这是一个碰撞并将尝试查找另一个空槽。

Answer 2

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

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

这里“a”是关键，10是它的价值。所以，如果我们更新

dictionary['a'] = 15

而不是把它放入一个新的插槽，它将更新该位置'a'。

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

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