Hashtable Erklärung

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 

Ich habe dieses Bit der Datenstruktur auf Hashtable gelesen, und brauchen Erklärung in diesem Teil unten.

Wenn der Schlüssel bereits vorhanden ist, warum werden Daten ersetzt?

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

Kann auch jemand diesen Teil erklären? Nextslot wäre ein leerer Slot. Und wir nur rehash und wenn es nicht leer ist und Schlüssel nicht vorhanden ist, wieder aufrüsten?

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

Wenn Schlüssel bereits vorhanden ist, warum Daten ersetzt werden?

So verhalten sich Hashtabellen normalerweise, weil die Leute normalerweise wollen, dass sie sich so verhalten. Das Setzen eines bereits vorhandenen Schlüssels überschreibt den vorherigen Wert.

Kann auch jemand diesen Teil erklären? Nextslot wäre ein leerer Slot.

Nextslot ist nicht garantiert leer zu sein, es ist nur der nächste Slot, den wir überprüfen werden. Stellen Sie sich Folgendes vor: Solange der zu überprüfende Steckplatz von einem verschiedenen Schlüssel belegt wird, müssen wir den nächsten Steckplatz (der durch erneutes Laden ausgewählt wird) weiterverwenden. Wenn wir einen leeren Platz finden, großartig, benutze ihn. Wenn wir feststellen, dass der Slot genommen wurde, aber es ist derselbe Schlüssel, dann überschreiben Sie es. Diese Schleife wird so lange wiederholt, bis sie einen freien Platz findet ODER einen Platz, der denselben Schlüssel hat (den wir überschreiben können).