So implementieren Sie eine Hashmap in Golang

Die mit der Golang-Sprache gelieferte Kartenstruktur ist ein sehr praktischer Datentyp. Für Datenoperationen, die mehr Effizienz und Flexibilität erfordern, können wir jedoch die von Golang implementierte Hashmap verwenden. In diesem Artikel wird vorgestellt, wie Golang Hashmap implementiert.

1. Implementierungsprinzip

Das Prinzip der Golang-Implementierung von Hashmaps ist sehr einfach: Schlüssel-Wert-Paare werden über einen bestimmten Algorithmus einem Array zugeordnet und eine verknüpfte Liste verwendet, um Hash-Konflikte zu lösen. Konkret erfordert die Implementierung von Hashmap die folgenden Schritte:

1. Erstellen Sie ein Array mit einer Array-Größe von 2 hoch n-tel (n ist einstellbar).
2. Berechnen Sie den Hash-Wert jedes einzufügenden Schlüssel-Wert-Paares und modulieren Sie dann mithilfe des Hash-Werts die Array-Größe, um deren Position im Array zu ermitteln.
3. Wenn die Position leer ist, fügen Sie das Schlüssel-Wert-Paar direkt an dieser Position im Array in die verknüpfte Liste ein.
4. Wenn an dieser Position bereits ein Wert vorhanden ist, durchlaufen Sie die verknüpfte Liste an dieser Position, um festzustellen, ob derselbe Schlüssel vorhanden ist. Wenn er nicht vorhanden ist, fügen Sie den Knoten direkt am Ende ein die verknüpfte Liste.
5. Wenn Sie nach einem Schlüssel-Wert-Paar suchen, verwenden Sie zunächst den Hash-Wert, um die Array-Größe zu modulieren, um seine Position im Array zu ermitteln, und durchlaufen Sie dann die verknüpfte Liste an dieser Position, um den Wert des entsprechenden Schlüssels zu finden.

2. Implementierungscode

Das Folgende ist ein einfacher Golang-Code zum Implementieren von Hashmap:

package hashmap

import "sync"

type Node struct {
    key   string
    value interface{}
    next  *Node
}

type HashMap struct {
    size  int
    nodes []*Node
    mutex sync.Mutex
}

func NewHashMap(size int) *HashMap {
    return &HashMap{size, make([]*Node, size), sync.Mutex{}}
}

func (hm *HashMap) hash(key string) int {
    h := 0
    for i := 0; i < len(key); i++ {
        h = (h << 5) + h + int(key[i])
    }
    return h % hm.size
}

func (hm *HashMap) Set(key string, value interface{}) {
    hm.mutex.Lock()
    defer hm.mutex.Unlock()
    i := hm.hash(key)
    if hm.nodes[i] == nil {
        hm.nodes[i] = &Node{key, value, nil}
    } else {
        for n := hm.nodes[i]; n != nil; n = n.next {
            if n.key == key {
                n.value = value
                return
            }
            if n.next == nil {
                n.next = &Node{key, value, nil}
                break
            }
        }
    }
}

func (hm *HashMap) Get(key string) interface{} {
    hm.mutex.Lock()
    defer hm.mutex.Unlock()
    i := hm.hash(key)
    for n := hm.nodes[i]; n != nil; n = n.next {
        if n.key == key {
            return n.value
        }
    }
    return nil
}

func (hm *HashMap) Delete(key string) {
    hm.mutex.Lock()
    defer hm.mutex.Unlock()
    i := hm.hash(key)
    if hm.nodes[i] != nil {
        if hm.nodes[i].key == key {
            hm.nodes[i] = hm.nodes[i].next
            return
        }
        for n := hm.nodes[i]; n.next != nil; n = n.next {
            if n.next.key == key {
                n.next = n.next.next
                return
            }
        }
    }
}

3. Anwendungsbeispiele

Anwendungsbeispiele sind wie folgt:

package main

import (
    "fmt"
    "hashmap"
)

func main() {
    m := hashmap.NewHashMap(16)
    m.Set("apple", 1)
    m.Set("banana", 2)
    m.Set("cat", 3)
    fmt.Println(m.Get("apple"))   // Output: 1
    fmt.Println(m.Get("carrot")) // Output: <nil>
    m.Delete("banana")
    fmt.Println(m.Get("banana")) // Output: <nil>
}

4. Zusammenfassung

Die Implementierung von Hashmap über Golang kann praktisch sein und effiziente, flexible Datenoperationen. Das Prinzip der Implementierung von Hashmap ist sehr einfach. Es ordnet Schlüssel-Wert-Paare hauptsächlich einem Array über einen Hash-Algorithmus zu und verwendet eine verknüpfte Liste, um Hash-Konflikte zu lösen. Der Code im Anwendungsbeispiel kann als Referenz verwendet werden und Sie können ihn auch entsprechend Ihren eigenen Anforderungen optimieren und verbessern.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine Hashmap in Golang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!