Hash-Maps sind indizierte Datenstrukturen. Eine Hash-Map verwendet a Hash-Funktion um einen Index mit einem Schlüssel in ein Array von Buckets oder Slots zu berechnen. Sein Wert wird dem Bucket mit dem entsprechenden Index zugeordnet. Der Schlüssel ist einzigartig und unveränderlich. Stellen Sie sich eine Hash-Map als einen Schrank vor, der Schubladen mit Etiketten für die darin aufbewahrten Dinge enthält. Zum Beispiel das Speichern von Benutzerinformationen – betrachten Sie E-Mail als Schlüssel, und wir können Werte, die diesem Benutzer entsprechen, wie Vorname, Nachname usw., einem Bucket zuordnen.
Die Hash-Funktion ist der Kern der Implementierung einer Hash-Map. Es nimmt den Schlüssel auf und übersetzt ihn in den Index eines Buckets in der Bucket-Liste. Ideales Hashing sollte für jeden Schlüssel einen anderen Index erzeugen. Allerdings kann es zu Kollisionen kommen. Wenn das Hashing einen vorhandenen Index ergibt, können wir einfach einen Bucket für mehrere Werte verwenden, indem wir eine Liste anhängen oder erneut aufbereiten.
In Python sind Wörterbücher Beispiele für Hash-Maps. Wir werden uns die Implementierung einer Hash-Map von Grund auf ansehen, um zu lernen, wie man solche Datenstrukturen zur Optimierung der Suche erstellt und anpasst.
Das Hash-Map-Design umfasst die folgenden Funktionen:
- set_val(Schlüssel, Wert): Fügt ein Schlüssel-Wert-Paar in die Hash-Map ein. Wenn der Wert bereits in der Hash-Map vorhanden ist, aktualisieren Sie den Wert.
- get_val(key): Gibt den Wert zurück, dem der angegebene Schlüssel zugeordnet ist, oder „Kein Datensatz gefunden“, wenn diese Zuordnung keine Zuordnung für den Schlüssel enthält.
- delete_val(key): Entfernt die Zuordnung für den spezifischen Schlüssel, wenn die Hash-Zuordnung die Zuordnung für den Schlüssel enthält.
Nachfolgend finden Sie die Implementierung.
Python3
class> HashTable:> ># Create empty bucket list of given size> >def> __init__(>self>, size):> >self>.size>=> size> >self>.hash_table>=> self>.create_buckets()> >def> create_buckets(>self>):> >return> [[]>for> _>in> range>(>self>.size)]> ># Insert values into hash map> >def> set_val(>self>, key, val):> > ># Get the index from the key> ># using hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be inserted> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key to be inserted,> ># Update the key value> ># Otherwise append the new key-value pair to the bucket> >if> found_key:> >bucket[index]>=> (key, val)> >else>:> >bucket.append((key, val))> ># Return searched value with specific key> >def> get_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key being searched> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key being searched,> ># Return the value found> ># Otherwise indicate there was no record found> >if> found_key:> >return> record_val> >else>:> >return> 'No record found'> ># Remove a value with specific key> >def> delete_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be deleted> >if> record_key>=>=> key:> >found_key>=> True> >break> >if> found_key:> >bucket.pop(index)> >return> ># To print the items of hash map> >def> __str__(>self>):> >return> ''.join(>str>(item)>for> item>in> self>.hash_table)> hash_table>=> HashTable(>50>)> # insert some values> hash_table.set_val(>'[email protected]'>,>'some value'>)> print>(hash_table)> print>()> hash_table.set_val(>'[email protected]'>,>'some other value'>)> print>(hash_table)> print>()> # search/access a record with key> print>(hash_table.get_val(>'[email protected]'>))> print>()> # delete or remove a value> hash_table.delete_val(>'[email protected]'>)> print>(hash_table)> |
>
>
wie man int in einen String Java umwandelt
Ausgabe:
Zeitkomplexität:
Der Zugriff auf den Speicherindex nimmt eine konstante Zeit in Anspruch, und das Hashing benötigt eine konstante Zeit. Daher ist die Suchkomplexität einer Hash-Map auch eine konstante Zeit, also O(1).
Vorteile von HashMaps
● Schneller zufälliger Speicherzugriff durch Hash-Funktionen
● Kann negative und nicht ganzzahlige Werte verwenden, um auf die Werte zuzugreifen.
● Schlüssel können in sortierter Reihenfolge gespeichert werden und können daher problemlos über die Karten iteriert werden.
Nachteile von HashMaps
● Kollisionen können hohe Strafen nach sich ziehen und die Zeitkomplexität auf lineare Werte steigern.
● Wenn die Anzahl der Schlüssel groß ist, führt eine einzelne Hash-Funktion häufig zu Kollisionen.
Anwendungen von HashMaps
● Diese haben Anwendungen in Cache-Implementierungen, bei denen Speicherorte kleinen Mengen zugeordnet werden.
● Sie werden zur Indizierung von Tupeln in Datenbankverwaltungssystemen verwendet.
● Sie werden auch in Algorithmen wie dem Mustervergleich von Rabin Karp verwendet