A Hash-tabelle ist eine Datenstruktur, die das schnelle Einfügen, Löschen und Abrufen von Daten ermöglicht. Dabei wird eine Hash-Funktion verwendet, um einen Schlüssel einem Index in einem Array zuzuordnen. In diesem Artikel implementieren wir eine Hash-Tabelle in Python mit separater Verkettung zur Handhabung von Kollisionen.
Komponenten des Hashings
Separate Verkettung ist eine Technik zur Behandlung von Kollisionen in einer Hash-Tabelle. Wenn zwei oder mehr Schlüssel demselben Index im Array zugeordnet sind, speichern wir sie in einer verknüpften Liste an diesem Index. Dadurch können wir mehrere Werte im selben Index speichern und sie dennoch mithilfe ihres Schlüssels abrufen.
Möglichkeit zur Implementierung einer Hash-Tabelle mithilfe separater Verkettung
Möglichkeit zur Implementierung einer Hash-Tabelle mithilfe separater Verkettung:
Erstellen Sie zwei Klassen: „ Knoten ' Und ' Hash-tabelle '.
Der ' Knoten Die Klasse „repräsentiert einen Knoten in einer verknüpften Liste.“ Jeder Knoten enthält ein Schlüssel-Wert-Paar sowie einen Zeiger auf den nächsten Knoten in der Liste.
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> |
>
>
Die Klasse „HashTable“ enthält das Array, das die verknüpften Listen enthält, sowie Methoden zum Einfügen, Abrufen und Löschen von Daten aus der Hash-Tabelle.
Python3
class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> |
>
>
Der ' __heiß__ Die Methode initialisiert die Hash-Tabelle mit einer bestimmten Kapazität. Es legt die „ Kapazität ' Und ' Größe ' Variablen und initialisiert das Array auf 'None'.
Die nächste Methode ist die „ _Hash ' Methode. Diese Methode nimmt einen Schlüssel und gibt einen Index im Array zurück, in dem das Schlüssel-Wert-Paar gespeichert werden soll. Wir werden die in Python integrierte Hash-Funktion verwenden, um den Schlüssel zu hashen, und dann den Modulo-Operator verwenden, um einen Index im Array zu erhalten.
Python3
Linux-Befehle
def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> |
>
>
Der 'einfügen' Die Methode fügt ein Schlüssel-Wert-Paar in die Hash-Tabelle ein. Es übernimmt den Index, in dem das Paar gespeichert werden soll, mit dem Befehl „ _Hash ' Methode. Wenn an diesem Index keine verknüpfte Liste vorhanden ist, wird ein neuer Knoten mit dem Schlüssel-Wert-Paar erstellt und als Kopf der Liste festgelegt. Wenn an diesem Index eine verknüpfte Liste vorhanden ist, durchlaufen Sie die Liste, bis der letzte Knoten gefunden wird oder der Schlüssel bereits vorhanden ist, und aktualisieren Sie den Wert, wenn der Schlüssel bereits vorhanden ist. Wenn der Schlüssel gefunden wird, wird der Wert aktualisiert. Wenn der Schlüssel nicht gefunden wird, wird ein neuer Knoten erstellt und am Kopf der Liste hinzugefügt.
Python3
def> insert(>self>, key, value):> >index>=> self>._hash(key)> >if> self>.table[index]>is> None>:> >self>.table[index]>=> Node(key, value)> >self>.size>+>=> 1> >else>:> >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >current.value>=> value> >return> >current>=> current.>next> >new_node>=> Node(key, value)> >new_node.>next> => self>.table[index]> >self>.table[index]>=> new_node> >self>.size>+>=> 1> |
>
>
Der suchen Die Methode ruft den Wert ab, der einem bestimmten Schlüssel zugeordnet ist. Zuerst wird der Index abgerufen, in dem das Schlüssel-Wert-Paar gespeichert werden soll _Hash Methode. Anschließend wird die verknüpfte Liste an diesem Index nach dem Schlüssel durchsucht. Wenn der Schlüssel gefunden wird, wird der zugehörige Wert zurückgegeben. Wenn der Schlüssel nicht gefunden wird, wird ein Fehler angezeigt Schlüsselfehler .
Python3
def> search(>self>, key):> >index>=> self>._hash(key)> >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >return> current.value> >current>=> current.>next> >raise> KeyError(key)> |
>
>
Der 'entfernen' Die Methode entfernt ein Schlüssel-Wert-Paar aus der Hash-Tabelle. Es ruft zuerst den Index ab, in dem das Paar gespeichert werden soll, indem es das ` verwendet _Hash ` Methode. Anschließend wird die verknüpfte Liste an diesem Index nach dem Schlüssel durchsucht. Wenn der Schlüssel gefunden wird, wird der Knoten aus der Liste entfernt. Wenn der Schlüssel nicht gefunden wird, wird ein „`“ ausgegeben Schlüsselfehler `.
Python3
def> remove(>self>, key):> >index>=> self>._hash(key)> > >previous>=> None> >current>=> self>.table[index]> > >while> current:> >if> current.key>=>=> key:> >if> previous:> >previous.>next> => current.>next> >else>:> >self>.table[index]>=> current.>next> >self>.size>->=> 1> >return> >previous>=> current> >current>=> current.>next> > >raise> KeyError(key)> |
>
>
„__str__“ Methode, die eine String-Darstellung der Hash-Tabelle zurückgibt.
string.valueof
Python3
def> __str__(>self>):> >elements>=> []> >for> i>in> range>(>self>.capacity):> >current>=> self>.table[i]> >while> current:> >elements.append((current.key, current.value))> >current>=> current.>next> >return> str>(elements)> |
>
>
Hier ist die vollständige Implementierung der Klasse „HashTable“:
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> > > class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> > >def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> > >def> insert(>self>, key, value):> >index>=> self>._hash(key)> > >if> self>.table[index]>is> None>:> >self>.table[index]>=> Node(key, value)> >self>.size>+>=> 1> >else>:> >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >current.value>=> value> >return> >current>=> current.>next> >new_node>=> Node(key, value)> >new_node.>next> => self>.table[index]> >self>.table[index]>=> new_node> >self>.size>+>=> 1> > >def> search(>self>, key):> >index>=> self>._hash(key)> > >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >return> current.value> >current>=> current.>next> > >raise> KeyError(key)> > >def> remove(>self>, key):> >index>=> self>._hash(key)> > >previous>=> None> >current>=> self>.table[index]> > >while> current:> >if> current.key>=>=> key:> >if> previous:> >previous.>next> => current.>next> >else>:> >self>.table[index]>=> current.>next> >self>.size>->=> 1> >return> >previous>=> current> >current>=> current.>next> > >raise> KeyError(key)> > >def> __len__(>self>):> >return> self>.size> > >def> __contains__(>self>, key):> >try>:> >self>.search(key)> >return> True> >except> KeyError:> >return> False> > > # Driver code> if> __name__>=>=> '__main__'>:> > ># Create a hash table with> ># a capacity of 5> >ht>=> HashTable(>5>)> > ># Add some key-value pairs> ># to the hash table> >ht.insert(>'apple'>,>3>)> >ht.insert(>'banana'>,>2>)> >ht.insert(>'cherry'>,>5>)> > ># Check if the hash table> ># contains a key> >print>(>'apple'> in> ht)># True> >print>(>'durian'> in> ht)># False> > ># Get the value for a key> >print>(ht.search(>'banana'>))># 2> > ># Update the value for a key> >ht.insert(>'banana'>,>4>)> >print>(ht.search(>'banana'>))># 4> > >ht.remove(>'apple'>)> ># Check the size of the hash table> >print>(>len>(ht))># 3> |
>
>Ausgabe
True False 2 4 3>
Zeitkomplexität und Raumkomplexität:
- Der Zeitkomplexität des einfügen , suchen Und entfernen Methoden in einer Hash-Tabelle mit separater Verkettung hängen von der Größe der Hash-Tabelle, der Anzahl der Schlüssel-Wert-Paare in der Hash-Tabelle und der Länge der verknüpften Liste an jedem Index ab.
- Unter der Annahme einer guten Hash-Funktion und einer gleichmäßigen Schlüsselverteilung beträgt die erwartete zeitliche Komplexität dieser Methoden O(1) für jeden Vorgang. Im schlimmsten Fall kann es jedoch zu einer zeitlichen Komplexität kommen An) , wobei n die Anzahl der Schlüssel-Wert-Paare in der Hash-Tabelle ist.
- Es ist jedoch wichtig, eine gute Hash-Funktion und eine geeignete Größe für die Hash-Tabelle zu wählen, um die Wahrscheinlichkeit von Kollisionen zu minimieren und eine gute Leistung sicherzustellen.
- Der Raumkomplexität Die Funktionsweise einer Hash-Tabelle mit separater Verkettung hängt von der Größe der Hash-Tabelle und der Anzahl der in der Hash-Tabelle gespeicherten Schlüssel-Wert-Paare ab.
- Die Hash-Tabelle selbst dauert O(m) Raum, wobei m die Kapazität der Hash-Tabelle ist. Jeder verknüpfte Listenknoten benötigt O(1) Platz, und es können höchstens n Knoten in den verknüpften Listen vorhanden sein, wobei n die Anzahl der in der Hash-Tabelle gespeicherten Schlüssel-Wert-Paare ist.
- Daher beträgt die Gesamtkomplexität des Raums O(m + n) .
Abschluss:
In der Praxis ist es wichtig, eine geeignete Kapazität für die Hash-Tabelle zu wählen, um den Platzbedarf und die Wahrscheinlichkeit von Kollisionen auszugleichen. Wenn die Kapazität zu klein ist, steigt die Wahrscheinlichkeit von Kollisionen, die zu Leistungseinbußen führen können. Ist die Kapazität hingegen zu groß, kann die Hash-Tabelle mehr Speicher verbrauchen als nötig.