Comment implémenter hashmap dans Golang

La structure cartographique fournie avec le langage golang est un type de données très pratique, mais pour les opérations de données qui nécessitent plus d'efficacité et de flexibilité, nous pouvons choisir d'utiliser le hashmap implémenté par golang. Cet article présentera comment Golang implémente hashmap.

1. Principe de mise en œuvre

Le principe de l'implémentation de hashmap par Golang est très simple, qui consiste à mapper des paires clé-valeur à un tableau via un certain algorithme et à utiliser une liste chaînée pour résoudre les conflits de hachage. Plus précisément, l'implémentation de hashmap nécessite les étapes suivantes :

1. Créez un tableau avec une taille de tableau de 2 à la puissance n (n est réglable).
2. Calculez la valeur de hachage de chaque paire clé-valeur à insérer, puis utilisez la valeur de hachage pour modulo la taille du tableau afin d'obtenir sa position dans le tableau.
3. Si la position est vide, insérez directement la paire clé-valeur dans la liste chaînée à cette position dans le tableau.
4. S'il y a déjà une valeur à cette position, parcourez la liste chaînée à cette position pour déterminer si la même clé existe. Si elle existe, mettez à jour sa valeur correspondante si elle n'existe pas, insérez le nœud directement à la fin de ; la liste chaînée.
5. Lors de la recherche d'une paire clé-valeur, utilisez d'abord la valeur de hachage pour modulo la taille du tableau afin d'obtenir sa position dans le tableau, puis parcourez la liste chaînée à cette position pour trouver la valeur de la clé correspondante.

2. Code d'implémentation

Ce qui suit est un code Golang simple pour implémenter 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. Exemples d'utilisation

Les exemples d'utilisation sont les suivants :

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. Résumé

L'implémentation de hashmap via golang peut être pratique et des opérations de données efficaces et flexibles. Le principe d'implémentation de hashmap est très simple. Il mappe principalement les paires clé-valeur à un tableau via un algorithme de hachage et utilise une liste chaînée pour résoudre les conflits de hachage. Le code de l'exemple d'utilisation peut être utilisé pour votre référence, et vous pouvez également l'optimiser et l'améliorer en fonction de vos propres besoins.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!