[PYTHON] Hash-Kette wollte ich vermeiden (1)
Guten Abend (* ´ω ｀) Der Titel hat eine Stimme meines Herzens (lacht) Ich denke, es war schwierig für Leute, die zum ersten Mal studierten, einschließlich mir. Machen Sie es so einfach wie möglich zu verstehen und lassen Sie uns einspringen.
Ich bereitete hastig eine entsprechende Vereinbarung vor.
Von nun an werden wir die entsprechenden Daten im folgenden Array speichern.
Normalerweise werden die Daten in der Reihenfolge vom Zeiger 0 (= x [0]) gespeichert, aber diesmal ändern wir den Geschmack.
Die Hash-Kette fordert diesmal heraus
** Es konnten nur eine Daten an einer Adresse gespeichert werden.
Kann man nicht mehr packen? !! ** (Ist es ein bisschen rau ...)
Wenn Sie sich die Materialien von Experten ansehen, sehen Sie häufig die folgenden Abbildungen.
Wenn es x [0] ist, sieht es so aus, als ob die Daten durch insgesamt drei Ketten verbunden und verbunden sind.
Als ich es zum ersten Mal sah, fand ich es sehr schön, es ist erstaunlich, das zu können !!
Aber wie schreibst du es? (; ´ ･ ω ･)
Beginnen wir mit der grundlegenden Definition von Hash. Wie bestimmen Sie den Speicherzielzeiger? Ja, das ist es.
** "Benutzerdefinierte Ganzzahl"% Array-Länge **
Wenn Sie beispielsweise ** 14 ** eingeben, beträgt die diesmal vorbereitete Array-Länge 7, sodass 0 angezeigt wird. OK, was möchten Sie in x [0] speichern?
Lassen Sie uns vorerst auch ** 1 ** eingeben. Nein, hör auf !! x [0] Nicht nur 1 wird gespeichert, ** 14 ** wird auch zusammen gespeichert!
Fragen werden zu Tode kommen, aber lasst uns weitermachen.
Wie der Titel schon sagt, handelt es sich um eine Kette. Geben Sie also die Adresse des Verbindungsziels ein.
Wenn key = 14, value = 1, np (nächster Zeiger) = none ist, wird die folgende Abbildung erhalten.
Was passiert also, wenn Sie key = 21 mit der folgenden Eingabe eingeben?
21%7 = 0
Auch ** 0 ** ('Д')
Was soll ich machen. .. ..
Wenn Sie ein Problem haben, schreiben Sie es vorerst und es wird Ihre Stimmung ändern.
test.py
class Node:
def __init__(self,key,value,next):
self.key = key #Jede vom Benutzer eingegebene Ganzzahl
self.value = value #Wert, den Sie speichern möchten
self.np = np # next pointer
Als Knoten definiert, hat es drei Argumente. Bereiten wir ein Array zum Speichern dieses Knotens vor.
test.py
class ChainedHash:
def __init__(self,capacity):
self.capacity = capacity #Da es sich um die Array-Länge handelt, werden wir später 7 ersetzen.
self.table = [None]*self.capacity #Nennen Sie das Array, in dem die Nodes-Tabelle gespeichert ist
Weisen Sie beispielsweise Node den Schlüssel = 14, value = 1, np = None zu. Ordnen Sie es dann der Tabelle [0] zu und drucken Sie es aus. Dann war ich überrascht, Folgendes zu sehen.
test.py
[<__main__.Node object at 0x00000282E2DA9D60>, None, None, None, None, None, None]
Was ist falsch daran, der Tabelle [0] einen Knoten zuzuweisen? Als ich es zum ersten Mal sah, wäre ich fast hingefallen (lacht) Aber jetzt, wo ich darüber nachdenke, denke ich, dass dies auch eine der Möglichkeiten ist, die Kette zu konfigurieren.
Was denken Sie zum Beispiel, wenn Sie diese Beschreibung sehen?
test.py
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
Fügen Sie dem zu Beginn vorbereiteten Knoten drei Schlüssel, value und self.table [Vhash] hinzu. Ersetzen und temp zuweisen. Schlüssel und Wert sind die Werte, die Sie eingeben möchten. Aber self.table [Vhash], was ist das? Ja, dies ist der Wert, der ursprünglich in Tabelle [0] gespeichert war. Natürlich hat der Wert der Tabelle [0], der ursprünglich gespeichert wurde, den Schlüssel, den Wert, self.table [Vhash]. Es wird gespeichert (der Anfangswert von Tabelle [0] ist Keine). Was bedeutet das. .. Ich habe ein Bild gemacht, um die schlechte Erklärung zu ergänzen.
Das erste, was ich geschrieben habe, ist A, weil die Daten (Schlüssel, Wert, np) lang sind. Danach schrieb ich Daten wie B nach x [0], aber sehen Sie sich Bs np in der Abbildung an. Sind die Daten von A selbst eingebettet? ?? Wenn Sie also endlich den Inhalt des in Tabelle [0] gespeicherten Werts B erfassen, können Sie auch den nächsten Wert von A sehen. Wenn Sie den Vorgang des Einbettens von Daten in die Daten wie folgt fortsetzen, sehen Sie nicht viele verbundene Daten? Für alle Fälle lesen Sie bitte die Beschreibung unter Berücksichtigung der obigen Erklärung noch einmal.
test.py
# ↓ Data A = self.table[0]
temp = Node(key,value,self.table[Vhash])
#self.table[0]Neu vorbereiteter Schlüssel+ value +Daten A in einem Paket und zugewiesen
self.table[Vhash] = temp
#Aus der obigen Tabelle[0]Der Wert von wird von A nach B aktualisiert
Richtig? (Lol) Es werden nur eine Daten an eine Adresse geschrieben. Weil die Daten wie eine Kette in die Daten eingebettet sind Es sieht so aus, als wären sie verbunden. Es ist interessant (≧ ▽ ≦)
Mit diesem Bild ist das nächste einfacher. Vor dem Einbetten von Daten Ursprünglich benötigt Tabelle [0] eine Beschreibung, um zu überprüfen, ob doppelte Daten vorhanden sind, oder? Vielleicht wird es so sein.
test.py
def add(self,key,value):
Vhash = key % self.capacity #Berechnen Sie, welcher Zeiger in der Tabelle angegeben werden soll
p = self.table[Vhash] #Wenn es 0 ist, Tabelle[0]Ersetzen Sie den Wert von in p
#Wobei p der Schlüssel ist,value,Enthält np
while p is not None:
#p.Schlüssel extrahiert nur den Schlüssel in p
#p.Wenn der Schlüssel dem Schlüssel entspricht, den Sie dieses Mal eingegeben haben
#Es kann nicht verwendet werden, da es dupliziert ist und daher False zurückgibt.
if p.key == key:
return False
#Rufen Sie np in p,
#Eingebetteter Datenschlüssel, value,Ordnen Sie np p neu zu.
p = p.np
#Gehen Sie zurück zu während am Anfang und fahren Sie fort, bis keine mehr vorhanden sind
#Suchen Sie nach doppelten Schlüsseln.
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
Nun, ich bin endlich da. Ich werde das ganze Bild zusammenfassen.
test.py
class Node:
def __init__(self,key,value,np):
self.key = key
self.value = value
self.np = np
class ChainedHash:
def __init__(self,capacity):
self.capacity = capacity
self.table = [None]*self.capacity
def add(self,key,value):
Vhash = key % self.capacity
p = self.table[Vhash]
while p is not None:
if p.key == key:
return False
p = p.np
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
def dump(self):
for i in range(self.capacity):
p = self.table[i]
print(i,end="")
while p is not None:
print(f"=>{p.key}({p.value})",end="")
p = p.np
print()
test = ChainedHash(7)
while True:
num = int(input("select 1.add, 2.dump "))
if num == 1:
key = int(input("key: "))
val = int(input("val: "))
test.add(key,val)
elif num == 2:
test.dump()
else:
break
Ausführungsergebnis.py
select 1.add, 2.dump 1# 1.Wählen Sie Hinzufügen
key: 7
val: 1
select 1.add, 2.dump 1 # 1.Wählen Sie Hinzufügen
key: 14
val: 2
select 1.add, 2.dump 2# 2.Wählen Sie Dump
0=>14(2)=>7(1) #Fertigstellung der Kette('Д')!!
1
2
3
4
5
6
Nun, die lange Erklärung tut mir leid. Die Fortsetzung geht weiter zu dem (2) ...
Recommended Posts