Hash-Tabelle ist eine wichtige Datenstruktur, die in der Informatik weit verbreitet ist. Es kann schnell ein bestimmtes Element in großen Datenmengen finden, einfügen oder löschen. Die Verwendung von Python zur Implementierung einer Hash-Tabelle kann Ihnen nicht nur ein tiefes Verständnis des internen Arbeitsmechanismus einer Hash-Tabelle vermitteln, sondern auch Ihre Programmierfähigkeiten verbessern. In diesem Artikel erfahren Sie, wie Sie eine Hash-Tabelle in Python implementieren.
Hash-Tabelle wird auch Hash-Tabelle genannt und ist eine Methode zur Speicherung von Schlüsselwerten. Es greift auf Daten zu, indem es den Schlüssel einer Indexposition des Werts zuordnet. Zu seinen Grundoperationen gehören Einfügen, Löschen und Suchen.
Die Kernidee einer Hash-Tabelle besteht darin, mithilfe einer Hash-Funktion jeden Schlüssel einer Tabelle fester Größe zuzuordnen. Eine Hash-Funktion ist eine Funktion, die eine Eingabenachricht beliebiger Länge in eine Ausgabe fester Länge umwandelt. Zu den gängigen Hash-Funktionen gehören MD5, SHA1, SHA256 usw.
Wir verwenden Python, um eine einfache Hash-Tabelle zu implementieren, einschließlich grundlegender Operationen der Hash-Tabelle, wie Einfügen, Löschen und Suchen.
Definieren Sie zunächst eine Node-Klasse, um den Knoten der Hash-Tabelle darzustellen. Jeder Knoten enthält einen Schlüssel und einen Wert.
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = NoneAls nächstes definieren wir eine HashTable-Klasse. Wir verwenden die Python-Liste, um die zugrunde liegende Datenstruktur zu implementieren. Beim Einfügen eines Schlüssel-Wert-Paares müssen wir den Hash-Wert basierend auf dem Schlüssel berechnen und das Schlüssel-Wert-Paar an der entsprechenden Stelle in der Hash-Tabelle speichern.
class HashTable:
def __init__(self):
self.size = 100
self.table = [None] * self.size
def hash_func(self, key):
return sum([ord(c) for c in key]) % self.size
def insert(self, key, value):
hash_value = self.hash_func(key)
if self.table[hash_value] is None:
self.table[hash_value] = Node(key, value)
else:
cur = self.table[hash_value]
while cur.next is not None:
cur = cur.next
cur.next = Node(key, value)
def search(self, key):
hash_value = self.hash_func(key)
if self.table[hash_value] is None:
return None
else:
cur = self.table[hash_value]
while cur is not None:
if cur.key == key:
return cur.val
else:
cur = cur.next
return None
def delete(self, key):
hash_value = self.hash_func(key)
if self.table[hash_value] is None:
return
elif self.table[hash_value].key == key:
self.table[hash_value] = self.table[hash_value].next
else:
cur = self.table[hash_value]
while cur.next is not None:
if cur.next.key == key:
cur.next = cur.next.next
return
else:
cur = cur.nextIm obigen Code berechnet die hash_func-Methode den Hash-Wert basierend auf dem Schlüssel, die Einfügemethode fügt das Schlüssel-Wert-Paar an der entsprechenden Position in der Hash-Tabelle ein, die Suchmethode findet den Wert basierend auf dem Schlüssel und Die Löschmethode löscht den entsprechenden Schlüssel basierend auf dem Schlüssel-Wert-Paar.
Als nächstes testen wir die oben implementierte Hash-Tabelle.
ht = HashTable()
ht.insert('apple', 2.5)
ht.insert('banana', 1.3)
ht.insert('orange', 0.7)
print(ht.search('apple')) # 2.5
print(ht.search('banana')) # 1.3
print(ht.search('orange')) # 0.7
print(ht.search('lemon')) # None
ht.delete('apple')
print(ht.search('apple')) # NoneIm obigen Code erstellen wir ein HashTable-Objekt ht und fügen drei Schlüssel-Wert-Paare in ht ein. Dann verwenden wir die Suchmethode, um Werte mit den Schlüsseln „Apfel“, „Banane“ und „Orange“ zu finden und löschen ein Schlüssel-Wert-Paar mit dem Schlüssel „Apfel“. Schließlich suchen wir mit dem Schlüssel „apple“ nach dem Wert, der None zurückgeben sollte.
Dieser Artikel stellt vor, wie man eine Hash-Tabelle in Python implementiert. Wir haben eine Node-Klasse definiert, um einen Knoten der Hash-Tabelle darzustellen, und dann eine HashTable-Klasse definiert, um die Hash-Tabelle darzustellen, und die grundlegenden Operationen der Hash-Tabelle implementiert, wie z. B. Einfügen, Löschen und Suchen. Durch die Implementierung einer Hash-Tabelle können wir den internen Arbeitsmechanismus der Hash-Tabelle tiefgreifend verstehen und unsere Programmierfähigkeiten verbessern.
Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine Hash-Tabelle in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
