Hashtable解釋

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將是空插槽。 我們只是重新散列，如果它不是空的而且鍵不存在，再次重新散列？

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

如果鍵已經存在，爲什麼被替換的數據？

這就是哈希表正常表現的原因，因爲人們通常希望他們表現得那麼好。設置一個已經存在的密鑰「覆蓋」以前的值。

此外，有人可以解釋這一部分？ Nextslot將是空插槽。

Nextslot不保證是空的，它只是我們要檢查的下一個插槽。可以這樣想：只要我們檢查的插槽是由不同的密鑰取得的，我們需要繼續嘗試下一個插槽（通過重新散列選取）。如果我們找到一個空的插槽，太棒了，請使用它。如果我們發現該插槽已被佔用，但它是同一個密鑰，則將其覆蓋。因此，該循環不斷重新散列，直到它找到一個空的插槽或具有相同密鑰（我們可以覆蓋）的插槽。