哈希表解释

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

我已经阅读了hashtable上的数据结构，需要在下面对这部分进行解释。你知道吗

如果密钥已经存在，为什么要替换数据？你知道吗

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

还有，有人能解释一下这部分吗？下一个插槽将是空插槽。 我们只是重复一遍，如果不是空的，钥匙也不在，再重复一遍？你知道吗

  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不能保证是空的，它只是我们要检查的下一个插槽。这样想：只要我们正在检查的插槽被一个不同的键占用，我们就需要继续尝试下一个插槽（通过重新灰化来选择）。如果我们找到一个空位，很好，用它。如果我们发现插槽被占用，但它是同一个密钥，则覆盖它。因此，循环不断地重新灰化，直到找到一个空的插槽或一个具有相同密钥的插槽（我们可以覆盖它）。你知道吗