So implementieren Sie eine Hash-Tabelle in Python

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.

1. Was ist eine Hash-Tabelle?

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.

2. Implementieren einer Hash-Tabelle

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 = None

Als 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.next

Im 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.

3. Testen Sie die Hash-Tabelle

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')) # None

Im 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.

4. Zusammenfassung

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!