python - 哈希表解释

Question

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

def put(self,key,data):
  hashvalue = self.hashfunction(key,len(self.slots))

  if self.slots[hashvalue] == None:
    self.slots[hashvalue] = key
    self.data[hashvalue] = data
  else:
    if self.slots[hashvalue] == key:
      self.data[hashvalue] = data  #replace
    else:
      nextslot = self.rehash(hashvalue,len(self.slots))
      while self.slots[nextslot] != None and \
                      self.slots[nextslot] != key:
        nextslot = self.rehash(nextslot,len(self.slots))

      if self.slots[nextslot] == None:
        self.slots[nextslot]=key
        self.data[nextslot]=data
      else:
        self.data[nextslot] = data #replace

我一直在阅读哈希表上的这段数据结构，下面需要对这部分进行解释。

如果 key 已经存在，为什么要替换数据？

if self.slots[hashvalue] == key:
  self.data[hashvalue] = data  #replace

此外，有人可以解释一下这部分吗？ Nextslot 将是空槽。 我们只是重新散列，如果它不为空且 key 不存在，再次重新散列？

  nextslot = self.rehash(hashvalue,len(self.slots))
  while self.slots[nextslot] != None and \
                  self.slots[nextslot] != key:
    nextslot = self.rehash(nextslot,len(self.slots))

Answer 1

If key is already present, why is data being replaced?

这就是哈希表通常的行为方式，因为人们通常希望它们以这种方式运行。设置一个已经存在的键会“覆盖”之前的值。

Also, can someone explain this part? Nextslot would be empty slot.

Nextslot 不保证为空，它只是我们要检查的下一个插槽。可以这样想:只要我们正在检查的插槽被不同键占用，我们就需要继续尝试下一个插槽(通过重新散列选择)。如果我们找到一个空槽，很好，使用它。如果我们发现slot被占用了但是是同一个key，那么就覆盖掉。因此该循环会不断重新散列，直到它找到一个空槽或一个具有相同 key (我们可以覆盖)的槽。