Ein Leitfaden für Python-Hashmaps

Wenn Datenexperten heute über Datenspeicherung sprechen, beziehen sie sich meist darauf, wo die Daten gespeichert werden, ob in lokalen Dateien, SQL- oder NoSQL-Datenbanken oder in der Cloud. Ein weiterer wichtiger Aspekt im Zusammenhang mit der Datenspeicherung ist jedoch, wie die Daten gespeichert werden.

Das Wie der Datenspeicherung findet oft auf einer niedrigeren Ebene statt, nämlich im Kern der Programmiersprachen. Das hat eher mit der Gestaltung der Tools zu tun, die Datenpraktiker/innen verwenden, als damit, wie sie diese Tools einsetzen. Dennoch ist es für Datenexperten wichtig zu wissen, wie Daten gespeichert werden, um die zugrunde liegenden Mechanismen zu verstehen, die ihre Arbeit möglich machen. Darüber hinaus kann dieses Wissen ihnen helfen, bessere Entscheidungen zu treffen, um die Rechenleistung zu verbessern.

In diesem Artikel werden wir über Hashmaps sprechen. Ein Hashmap ist eine Datenstruktur, die Hashing-Techniken nutzt, um Daten assoziativ zu speichern. Hashmaps sind optimierte Datenstrukturen, die schnellere Datenoperationen wie Einfügen, Löschen und Suchen ermöglichen.

Viele moderne Programmiersprachen, wie Python, Java und C++, unterstützen Hashmaps. In Python werden Hashmaps durch Dictionaries implementiert, eine weit verbreitete Datenstruktur, die du wahrscheinlich kennst. In den folgenden Abschnitten werden wir die Grundlagen von Wörterbüchern behandeln, wie sie funktionieren und wie man sie mit verschiedenen Python-Paketen implementiert.

Was ist eine Hashmap?

Um einen Hashmap zu definieren, müssen wir zunächst verstehen, was Hashing ist. Hashing ist der Prozess der Umwandlung eines beliebigen Schlüssels oder einer Zeichenkette in einen anderen Wert. Das Ergebnis ist normalerweise ein kürzerer Wert mit fester Länge, der rechnerisch einfacher zu verarbeiten ist als der ursprüngliche Schlüssel.

Hashmaps, auch bekannt als Hashtabellen, sind eine der häufigsten Implementierungen von Hashing. Hashmaps speichern Schlüssel-Wert-Paare (z. B. Mitarbeiter-ID und Mitarbeitername) in einer Liste, auf die über ihren Index zugegriffen werden kann.

Die Idee hinter Hashmaps ist es, die Einträge (Schlüssel/Wertpaare) auf ein Array von Buckets zu verteilen. Bei einem Schlüssel berechnet eine Hash-Funktion einen eindeutigen Index, der angibt, wo der Eintrag gefunden werden kann. Durch die Verwendung eines Indexes anstelle des ursprünglichen Schlüssels eignen sich Hashmaps besonders gut für mehrere Datenoperationen, z. B. für das Einfügen, Entfernen und Suchen von Daten.

Wie eine Hashmap funktioniert.

Zur Berechnung des Hash-Werts, oder einfach Hash, erzeugt eine Hash-Funktion neue Werte nach einem mathematischen Hashing-Algorithmus. Da Schlüssel-Wert-Paare theoretisch unbegrenzt sind, ordnet die Hash-Funktion die Schlüssel auf der Grundlage einer bestimmten Tabellengröße zu.

Es gibt mehrere Hash-Funktionen, die jeweils ihre Vor- und Nachteile haben. Das Hauptziel einer Hash-Funktion ist es, für dieselbe Eingabe immer denselben Wert zurückzugeben.

Die häufigsten sind die folgenden:

• Teilungsmethode. Es ist der einfachste und schnellste Weg, Hash-Werte zu berechnen. Dazu wird der Schlüssel durch die Tabellengröße geteilt und der Rest als Hashwert verwendet.
• Mid Square Methode. Es findet das Quadrat des angegebenen Schlüssels, nimmt dann die mittleren Ziffern und verwendet diese Ziffern als Index für das Element.
• Multiplikationsmethode. Sie setzt den Hash-Index aus dem Bruchteil der Multiplikation des Schlüssels mit einer großen reellen Zahl.
• Methode zum Falten. Der Schlüssel wird zunächst in gleich große Stücke geteilt, das Ergebnis wird addiert und das Ergebnis wird durch die Größe des Tisches geteilt. Die Raute ist die Erinnerung.

Hashmap in Python

Python implementiert Hashmaps durch den eingebauten Wörterbuch-Datentyp. Wie Hashmaps speichern Dictionaries Daten in {Schlüssel:Wert}-Paaren. Sobald du das Wörterbuch erstellt hast (siehe nächster Abschnitt), wendet Python unter der Haube eine praktische Hash-Funktion an, um den Hash-Wert jedes Schlüssels zu berechnen.

Python-Wörterbücher verfügen über die folgenden Funktionen:

• Wörterbücher sind veränderbar. Das bedeutet, dass wir Elemente ändern, hinzufügen oder entfernen können, nachdem das Wörterbuch erstellt worden ist.
• Die Elemente sind geordnet. In Python 3.6 und früher waren Dictionaries ungeordnet, d.h. die Elemente hatten keine bestimmte Reihenfolge. Mit der Veröffentlichung von Python 3.7 wurden die Wörterbücher jedoch auftragserhaltend. Wenn du jetzt ein Python-Wörterbuch erstellst, folgen die Schlüssel der Reihenfolge, die im Quellcode angegeben ist. Wenn du mehr über die Gründe für diese Änderung wissen willst, lies diese Notiz von Raymond Hettinger, einem der Kernentwickler von Python.
• Schlüssel sind unveränderlich. Das bedeutet, dass Schlüssel immer Datentypen sind, die nicht verändert werden können. Mit anderen Worten: In Wörterbüchern sind nur Datentypen erlaubt, die hashfähig sind, wie Strings, Zahlen und Tupel. Im Gegenteil, Schlüssel können niemals ein veränderbarer Datentyp sein, wie z.B. eine Liste.
• Schlüssel sind einzigartig. Schlüssel sind innerhalb eines Wörterbuchs eindeutig und können innerhalb eines Wörterbuchs nicht dupliziert werden. Wenn er mehr als einmal verwendet wird, überschreiben die nachfolgenden Einträge den vorherigen Wert.

Wenn du dich also jemals über die Unterschiede zwischen Hashmaps und Wörterbüchern gewundert hast, ist die Antwort einfach. Ein Wörterbuch ist nur Pythons native Implementierung von Hashmaps. Während eine Hashmap eine Datenstruktur ist, die mit verschiedenen Hash-Verfahren erstellt werden kann, ist ein Wörterbuch eine spezielle, auf Python basierende Hashmap, deren Design und Verhalten in der Python-Klasse dict festgelegt ist.

Wie man Python-Wörterbücher verwendet

Schauen wir uns einige der häufigsten Wörterbuchoperationen an. Mehr über die Verwendung von Wörterbüchern erfährst du in unserem Python Dictionaries Tutorial.

Ein Wörterbuch erstellen

Das Erstellen von Wörterbüchern in Python ist ziemlich einfach. Du musst nur geschweifte Klammern verwenden und die Schlüssel-Wert-Paare durch Kommas getrennt einfügen. Alternativ kannst du auch die eingebaute Funktion dict() verwenden. Lass uns ein Wörterbuch erstellen, das die Hauptstädte den Ländern zuordnet:

# Create dictionary
dictionary_capitals = {'Madrid": 'Spain", 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Um den Inhalt des Wörterbuchs zu drucken:

print(dictionary_capitals)

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

Es ist wichtig, daran zu denken, dass ein Schlüssel in einem Wörterbuch eindeutig sein muss; es sind keine Duplikate erlaubt. Bei doppelten Schlüsseln gibt Python jedoch keine Fehlermeldung aus, sondern nimmt die letzte Instanz des Schlüssels als gültig an und ignoriert das erste Schlüssel-Wert-Paar einfach. Sieh es dir selbst an:

dictionary_capitals = {'Madrid': 'China', 'Lisboa': 'Portugal', 
                       'London': 'United Kingdom','Madrid':'Spain'}

print(dictionary_capitals)

{'Madrid': 'Spain', 'Lisboa': 'Portugal', 'London': 'United Kingdom'}

In einem Wörterbuch suchen

Um nach Informationen in unserem Wörterbuch zu suchen, müssen wir den Schlüssel in Klammern angeben, und Python gibt den zugehörigen Wert zurück, wie folgt:

# Search for data
dictionary_capitals['Madrid']

'Spain'

Wenn du versuchst, auf einen Schlüssel zuzugreifen, der nicht im Wörterbuch vorhanden ist, gibt Python einen Fehler aus. Um dies zu verhindern, kannst du alternativ mit der Methode .get() auf die Schlüssel zugreifen. Wenn der Schlüssel nicht existiert, wird einfach der Wert None zurückgegeben:

print(dictionary_capitals.get('Prague'))

None

Hinzufügen und Löschen von Werten in einem Wörterbuch

Fügen wir ein neues Hauptstadt-Länder-Paar hinzu:

# Create a new key-value pair
dictionary_capitals['Berlin'] = 'Italy'

Dieselbe Syntax kann verwendet werden, um den mit einem Schlüssel verbundenen Wert zu aktualisieren. Lass uns den Wert für Berlin festlegen:

# Update the value of a key
dictionary_capitals['Berlin'] = 'Germany'

Löschen wir nun eines der Paare in unserem Wörterbuch

# Delete key-value pair
del dictionary_capitals['Lisboa']

print(dictionary_capitals)

{'Madrid': 'Spain', 'London': 'United Kingdom', 'Berlin': 'Germany'}

Wenn du alle Schlüssel-Wert-Paare im Wörterbuch löschen möchtest, kannst du auch die Methode .clear() verwenden:

dictionary_capitals.clear()

Schleifen durch Wörterbücher

Wenn du alle Schlüssel-Wert-Paare abrufen willst, verwende die Methode .items(), und Python wird eine iterierbare Liste von Tupeln abrufen:

dictionary_capitals.items()

dict_items([('Madrid', 'Spain'), ('London', 'United Kingdom'), ('Berlin', 'Germany')])

# Iterate over key-value pairs
for key, value in dictionary_capitals.items():
    print('the capital of {} is {}'.format(value, key))

the capital of Spain is Madrid
the capital of United Kingdom is London
the capital of Germany is Berlin

Wenn du eine iterierbare Liste mit den Schlüsseln und Werten abrufen willst, kannst du die Methoden .keys() und .values() verwenden:

dictionary_capitals.keys()

dict_keys(['Madrid', 'London', 'Berlin'])

for key in dictionary_capitals.keys():
    print(key.upper())

MADRID
LONDON
BERLIN

dictionary_capitals.values()

dict_values(['Spain', 'United Kingdom', 'Germany'])

for value in dictionary_capitals.values():
    print(value.upper())

SPAIN
UNITED KINGDOM
GERMANY

Anwendungen von Hashmaps in der realen Welt

Hashmaps sind mächtige Datenstrukturen, die fast überall in der digitalen Welt verwendet werden. Im Folgenden findest du eine Liste mit praktischen Anwendungen von Hashmaps:

• Datenbank-Indizierung. Hashmaps werden oft zum Indizieren und Durchsuchen großer Datenmengen verwendet. Gängige Webbrowser verwenden Hashmaps, um indizierte Webseiten zu speichern.
• Cache-Verwaltung. Moderne Betriebssysteme verwenden Hashmaps, um den Cache-Speicher zu organisieren und einen schnellen Zugriff auf häufig verwendete Informationen zu ermöglichen.
• Kryptographie. Hashmaps spielen eine wichtige Rolle in der Kryptografie. Kryptografische Algorithmen nutzen Hashmaps, um Datenintegrität, Datenvalidierung und sichere Transaktionen in Netzwerken zu ermöglichen.
• Blockchain. Hashmaps sind das Herzstück der Blockchain. Wann immer eine Transaktion im Netzwerk stattfindet, werden die Daten dieser Transaktion als Eingabe für die Hash-Funktion verwendet, die dann eine eindeutige Ausgabe erzeugt. Jeder Block in der Blockchain enthält den Hash des vorherigen Blocks und bildet eine Kette von Blöcken.

Bewährte Praktiken und häufige Fehler bei der Hashmap

Hashmaps sind unglaublich vielseitige und effiziente Datenstrukturen. Sie bringen jedoch auch Probleme und Einschränkungen mit sich. Um die häufigen Herausforderungen im Zusammenhang mit Hashmaps zu bewältigen, ist es wichtig, einige Überlegungen und bewährte Praktiken zu beachten.

Schlüssel müssen unveränderlich sein

Das macht Sinn: Wenn sich der Inhalt des Schlüssels ändert, gibt die Hash-Funktion einen anderen Hashwert zurück, sodass Python den Wert, der mit dem Schlüssel verknüpft ist, nicht mehr finden kann.

Umgang mit Hashmap-Kollisionen

Hashing funktioniert nur, wenn jedes Element auf eine eindeutige Stelle in der Hashtabelle abgebildet wird. Aber manchmal können Hash-Funktionen für unterschiedliche Eingaben die gleiche Ausgabe liefern. Wenn du zum Beispiel eine Divisions-Hash-Funktion verwendest, können verschiedene ganze Zahlen die gleiche Hash-Funktion haben (sie können den gleichen Rest zurückgeben, wenn sie das Modul Division anwenden), wodurch ein Problem namens Kollision entsteht. Kollisionen müssen aufgelöst werden, und dafür gibt es verschiedene Techniken. Zum Glück kümmert sich Python im Falle von Wörterbüchern um mögliche Kollisionen unter der Haube.

Belastungsfaktor verstehen

Der Auslastungsfaktor ist definiert als das Verhältnis zwischen der Anzahl der Elemente in der Tabelle und der Gesamtzahl der Eimer. Es ist ein Maß, um abzuschätzen, wie gut die Daten verteilt sind. Als Faustregel gilt: Je gleichmäßiger die Daten verteilt sind, desto geringer ist die Wahrscheinlichkeit von Kollisionen. Bei Wörterbüchern wiederum passt Python die Tabellengröße automatisch an, wenn neue Schlüssel-Wert-Paare eingefügt oder gelöscht werden.

Sei dir der Leistung bewusst

Eine gute Hash-Funktion sollte die Anzahl der Kollisionen minimieren, einfach zu berechnen sein und die Elemente in der Hash-Tabelle gleichmäßig verteilen. Dies könnte durch eine Erhöhung der Tabellengröße oder der Komplexität der Hash-Funktion erreicht werden. Obwohl dies bei einer kleinen Anzahl von Gegenständen praktisch ist, ist es bei einer großen Anzahl von möglichen Gegenständen nicht machbar, da es zu speicherintensiven, weniger effizienten Hashmaps führen würde.

Sind Wörterbücher das, was du brauchst?

Wörterbücher sind großartig, aber andere Datenstrukturen können für deine spezifischen Daten und Bedürfnisse besser geeignet sein. Schließlich unterstützen Wörterbücher keine gängigen Operationen wie Indizierung, Slicing und Verkettung, was sie weniger flexibel und in bestimmten Szenarien schwieriger zu handhaben macht.

Alternative Python-Hashmap-Implementierungen

Wie bereits erwähnt, implementiert Python Hashmaps durch eingebaute Wörterbücher. Es ist jedoch wichtig zu wissen, dass es auch andere Python-Tools und Bibliotheken von Drittanbietern gibt, mit denen du die Möglichkeiten von Hashmaps nutzen kannst.

Sehen wir uns einige der beliebtesten Beispiele an.

Standarddiktat

Jedes Mal, wenn du versuchst, auf einen Schlüssel zuzugreifen, der nicht in deinem Wörterbuch vorhanden ist, gibt Python einen KeyError zurück. Eine Möglichkeit, dies zu verhindern, ist die Suche nach Informationen mit der Methode .get(). Ein optimierter Weg, dies zu tun, ist die Verwendung eines Standarddiktats, das in den Modulsammlungen verfügbar ist. Standarddiktate und Wörterbücher sind fast dasselbe. Der einzige Unterschied ist, dass defaultdict nie einen Fehler auslöst, weil es einen Standardwert für nicht existierende Schlüssel liefert.

from collections import defaultdict 

# Defining the dict 
capitals = defaultdict(lambda: "The key doesn't exist") 
capitals['Madrid'] = 'Spain'
capitals['Lisboa'] = 'Portugal'
  
print(capitals['Madrid']) 
print(capitals['Lisboa']) 
print(capitals['Ankara']) 

Spain
Portugal
The key doesn't exist 

Zähler

Counter ist eine Unterklasse eines Python-Dictionarys, die speziell für das Zählen von hashfähigen Objekten entwickelt wurde. Es ist ein Wörterbuch, in dem Elemente als Schlüssel und ihre Anzahl als Wert gespeichert werden.

Es gibt verschiedene Möglichkeiten, Counter zu initialisieren:

• Durch eine Abfolge von Gegenständen.
• Nach Schlüsseln und Anzahlen in einem Wörterbuch.
• Name:Wert-Zuordnung verwenden.

from collections import Counter 

# a new counter from an iterable
c1 = Counter(['aaa','bbb','aaa','ccc','ccc','aaa'])
# a new counter from a mapping
c2 = Counter({'red': 4, 'blue': 2})     
# a new counter from keyword args
c3 = Counter(cats=4, dogs=8)       
# print results
print(c1)
print(c2)
print(c3)

Counter({'aaa': 3, 'ccc': 2, 'bbb': 1})
Counter({'red': 4, 'blue': 2})
Counter({'dogs': 8, 'cats': 4})

Die Zählerklasse verfügt über eine Reihe von praktischen Methoden, um gängige Berechnungen durchzuführen.

print('keys of the counter: ', c3.keys())
print('values of the counter: ',c3.values()) 
print('list with all elements: ', list(c3.elements())) 
print('number of elements: ', c3.total()) # number elements
print('2 most common occurrences: ', c3.most_common(2)) # 2 most common occurrences 

dict_keys(['cats', 'dogs'])
dict_values([4, 8])
['cats', 'cats', 'cats', 'cats', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs']
12
[('dogs', 8), ('cats', 4)]

Scikit-learn Hashing-Methoden

Scikit-learn, auch bekannt als sklearn, ist eine robuste Open-Source-Bibliothek für maschinelles Lernen in Python. Es wurde entwickelt, um den Prozess der Implementierung von maschinellem Lernen und statistischen Modellen in Python zu vereinfachen.

Sklearn verfügt über verschiedene Hashing-Methoden, die für die Entwicklung von Merkmalen sehr nützlich sein können.

Eine der gängigsten Methoden ist die CountVectorizer Methode. Sie wird verwendet, um einen gegebenen Text in einen Vektor umzuwandeln, der auf der Häufigkeit jedes Worts basiert, das im gesamten Text vorkommt. CountVectorized ist besonders hilfreich bei der Textanalyse.

from sklearn.feature_extraction.text import CountVectorizer
 
documents = ["Welcome to this new DataCamp Python course",
            "Welcome to this new DataCamp R skill track",
            "Welcome to this new DataCamp Data Analyst career track"]
 
# Create a Vectorizer Object
vectorizer = CountVectorizer()

X = vectorizer.fit_transform(documents)

# print unique values 
print('unique words: ', vectorizer.get_feature_names_out())


#print sparse matrix with word frequency
pd.DataFrame(X.toarray(), columns = vectorizer.get_feature_names_out())

unique words:  ['analyst' 'career' 'course' 'data' 'datacamp' 'new' 'python' 'skill' 'this' 'to' 'track' 'welcome']

Es gibt noch andere Hashing-Methoden in Sklearn, darunter FeatureHasher und DictVectorizer. Unser Kurs "Schulbudgetierung mit maschinellem Lernen in Python" ist ein großartiges Beispiel, bei dem du lernen kannst, wie sie in der Praxis funktionieren.

Fazit

Herzlichen Glückwunsch zum Abschluss dieses Tutorials über Hashmaps. Wir hoffen, du hast jetzt ein besseres Verständnis von Hashmaps und Python-Wörterbüchern. Wenn du mehr über Wörterbücher und ihre Verwendung in realen Szenarien erfahren möchtest, empfehlen wir dir, unser spezielles Python-Wörterbuch-Tutorial und unser Python-Wörterbuch-Verständnis-Tutorial zu lesen.

Wenn du gerade erst mit Python anfängst und mehr darüber erfahren möchtest, besuche den DataCamp-Kurs "Einführung in die Datenwissenschaft in Python" und schau dir unser Python-Tutorial für Anfänger/innen an.