Die einfachste Implementierung von HashMap in Go / Sudo Null IT News

Schönen Tag. Für einen unerfahrenen Programmierer (der ich bin) ist die Implementierung grundlegender Datenstrukturen wie Binärbäume und verknüpfte Listen ziemlich einfach. Was kann man über Hashkarten nicht sagen. In diesem Artikel werden wir ein Beispiel für seine Implementierung analysieren.

Über das Hash-Kartengerät

In diesem Beispiel betrachten wir eine Hash-Map basierend auf der Funktion Pearson-Hashing. Diese Funktion gibt eine Zahl vom Typ uint8 aus, als Ergebnis können wir 256 Speicherzellen verwenden, um das Ergebnis basierend auf dem Schlüssel zu speichern. Es gibt jedoch einen solchen Nachteil von Hash-Funktionen wie Kollisionen. Hier kommen verknüpfte Listen ins Spiel. Lassen Sie uns vereinbaren, dass unsere Hash-Map-Struktur ein Array der Länge 256 haben wird und jedes der Elemente eine verknüpfte Liste sein wird.

Schauen wir uns ein Beispiel an

Beginnen wir mit der Hash-Funktion.
Kurz gesagt, diese Funktion erhält eine beliebige Anzahl von Bytes als Eingabe und gibt 1 Byte zurück. Seine Implementierung basiert auf einer Reihe von Anweisungen (in diesem Fall das Verschieben eines Elements um eine Zeichennummer in der ASCII-Tabelle) sowie auf einer 256-Byte-Nachschlagetabelle, die eine Permutation von Werten von 0 bis 255 enthält.

var-Tabelle[256]int = func()[256]int {var-Daten [256]int rand.Seed(time.Now().Unix()) für index, _ := range(data) { data[index] = index } für index, _ := range(data) { rv := rand.Intn(256) data[index]Daten[rv] = Daten[rv]Daten[index]
} Daten zurückgeben }()

Zuerst erstellen wir ein Array aus 256 Elementen, von denen jedes einen Wert hat, der seinem Index entspricht, und mischen diese Elemente dann in zufälliger Reihenfolge.

func hash8(message string) int { // globale Tabelle verwenden var hash int = len(message)%256 for _, value := range(message) { hash = table[(hash + int(value))%256]
} Hash zurückgeben }

Und hier ist die Implementierung des Algorithmus 🙂
Betrachten wir es genauer. Wenn wir einen String als Eingabe erhalten, deklarieren wir eine Hash-Variable gleich (String-Länge) mod 256, die auch als Ergebnis der Hash-Funktion dient. Während wir über die Zeichenfolge iterieren, weisen wir dann den Hash-Wert zu, der gleich dem Wert des Nachschlagetabellenelements nach Index (Hash + ASCII-Nummer) mod 256 ist.

Nachdem wir uns mit der Hash-Funktion befasst haben, betrachten wir die Implementierung der Hash-Map selbst.

type Node struct { key string value string next *Node } type List struct { head *Node } type Map struct { map_list [256]*Len int64 auflisten }

Wie oben geschrieben, basiert die Hash-Map auf einem Array mit einer Länge von 256 Elementen. Jedes Element ist der Anfang/Kopf einer verketteten Liste Liste, bestehend aus Node-Knoten, die wiederum Schlüssel- und Wertvariablen haben. Außerdem hat Map eine len-Variable, die benötigt wird, um die Länge der Karte zu berechnen.

Kommen wir nun zu den Methoden. Zuerst müssen Sie die Linked-List-Methode implementieren:
1. Element einfügen
2. Löschen eines Elements
3. Ausgabe von Elementen (insbesondere Schlüssel)

Spoiler

Im Folgenden werden wir die Implementierung der Methoden der verknüpften Liste nicht im Detail betrachten …
Irgendwann wird es dazu einen Post geben.

func (l *List) add(key, val string, m *Map) { new_data := &Node{value: val, key: key} if l.head == nil { l.head = new_data m.len++ } else { current := l.head for current.next != nil { if key == current.key { current.value = val return } current = current.next } if key == current.key { current.value = val return } current.next = neue_daten m.len++ } }

Um ein Element einzufügen, gehen wir die verknüpfte Liste durch, wenn wir den gleichen Schlüssel wie die Eingabe finden, ändern wir den Wert, ansonsten fügen wir ein neues Element ans Ende und erhöhen den Längenzähler um 1.

func (l *List) delete(key string, m *Map) { current := l.head if current.key == key { l.head = l.head.next m.len– return } for current.next != nil { if current.next.key == key { current.next = current.next.next m.len– return } current = current.next } panic(“Key is missing!!”) }

Um dort ein Element zu löschen, müssen Sie die Liste durchgehen und den gewünschten Schlüssel finden und dieses Element löschen (durch das nächste ersetzen) und gleichzeitig den Längenzähler verringern. Wenn der Schlüssel fehlt, geben wir einen Fehler zurück.

func (l *Liste) print() []string { varresult []string current := l.head if current != nil { result = append(result, current.key) } for current.next != nil { result = append(result, current.next.key) current = current.next } Ergebnis zurückgeben }

Um die Schlüssel der Liste zu erhalten, iterieren wir darüber und sammeln alle Schlüssel im Ergebnisarray und geben es dann zurück.

Der nächste Schritt besteht darin, die Methoden der Map-Struktur selbst zu implementieren.:
1. Einfügen
2. Entfernung
3. Wert nach Schlüssel abrufen
4. Alle Schlüssel bekommen

func (m *Map) insert(key, val string) { if m.map_list[hash8(key)] == nil { m.map_list[hash8(key)] = &Liste{} } m.map_list[hash8(key)].add(Schlüssel, Wert, m) }

Um ein Element einzufügen, überprüfen wir das Vorhandensein von Daten im Array anhand des Index des Ergebnisses der Hash-Funktion. Wenn es nicht vorhanden ist, erstellen wir eine Instanz der Listenstruktur. Sonst haben wir eine Kollision. Dazu greifen wir auf das Element zu (das eine Instanz der List-Struktur ist) und rufen darauf die zuvor beschriebene add-Methode auf.

func (m *Map) delete(key string) { elem := m.map_list[hash8(key)]
if elem == nil { panic(“Map is nil!!”) } if elem.head.key == key && elem.head.next == nil { m.map_list[hash8(key)] = nil m.len– fmt.Println(“+”) } else if elem.head.next != nil { elem.delete(key, m) } else { panic(“Key is missing!!”) } }

Um das Entfernen eines Elements zu implementieren, überprüfen wir das Vorhandensein eines Elements im Array anhand des Index des Ergebnisses der Hash-Funktion:

  • Wenn das Element leer ist, geben wir einen Fehler zurück.

  • Wenn es ein Element gibt, aber kein nächstes, dann weisen wir dem Element des Arrays nil zu.

  • Wenn es ein Element und einen Nachfolger gibt, rufen wir die delete-Methode für das Array-Element (das den Typ *List hat) auf.

  • Andernfalls geben wir einen Fehler zurück, der besagt, dass der Schlüssel fehlt.

func (m *Map) get_value(key string) string { if m.map_list[hash8(key)] == nil { panic(“Map is nil!!”) } current := m.map_list[hash8(key)].head if current != nil && current.key == key { return current.value } for current.next != nil { if current.next.key == key { return current.next.value } current = current.next } panic(“Schlüssel fehlt!”) }

Um einen Wert nach Schlüssel zu erhalten, müssen Sie eine verknüpfte Liste aus einem Array basierend auf dem Ergebnis einer Hash-Funktion abrufen. Als nächstes iterieren Sie durch die verknüpfte Liste und vergleichen die Eingabe und die aktuellen Schlüssel.

func (m *Map) Tasten() []string { var antwort [] string for _, data := range(m.map_list) { if data != nil { answer = append(answer, data.print()…)} } return answer }

Um alle Schlüssel zu entladen, gehen wir durch das gesamte Array. Wenn das Element Daten enthält, ergänzen wir den Antwort-Slice mit dem resultierenden Slice der Druckfunktion der Listenstruktur.

Ergebnisse

Wir haben herausgefunden, wie man eine einfache Hash-Map basierend auf 8-Bit implementiert Pearson-Hash-Funktionen mit der Go-Sprache. Wir haben die Grenzfälle aller beschriebenen Verfahren sowie das Auftreten einer Kollision betrachtet. Die Komplexität dieser Struktur (sowohl für das Lesen als auch für das Schreiben) würde ich im besten Fall mit O (1) einschätzen, im schlimmsten Fall erreicht sie O (n), im Falle einer Kollision und der Bildung einer verketteten Liste Länge > 1.

Quelle

Similar Posts

Leave a Reply

Your email address will not be published.