How to implement hashmap in golang

The map structure that comes with the golang language is a very convenient data type, but for more efficient and flexible data operations, we can choose to use the hashmap implemented in golang. This article will introduce how golang implements hashmap.

1. Implementation Principle

The principle of Golang to implement hashmap is very simple, which is to map key-value pairs to an array through a certain algorithm, and use a linked list to resolve hash conflicts. Specifically, implementing hashmap requires the following steps:

1. Create an array with an array size of 2 to the nth power (n is adjustable).
2. Calculate the hash value of each key-value pair to be inserted, and then use the hash value to modulo the array size to obtain its position in the array.
3. If the position is empty, directly insert the key-value pair into the linked list at that position in the array.
4. If there is already a value at this position, traverse the linked list at this position to determine whether the same key exists. If it exists, update its corresponding value; if it does not exist, insert the node directly into the end of the linked list.
5. When searching for a key-value pair, first use the hash value to modulo the array size to obtain its position in the array, and then traverse the linked list at that position to find the value of the corresponding key.

2. Implementation code

The following is a simple golang code to implement 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. Usage examples

Usage examples are as follows ：

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. Summary

Implementing hashmap through golang can facilitate efficient and flexible data operations. The principle of implementing hashmap is very simple. It mainly maps key-value pairs to an array through a hash algorithm and uses a linked list to resolve hash conflicts. The code in the usage example can be used for your reference, and you can also optimize and improve it according to your own needs.

The above is the detailed content of How to implement hashmap in golang. For more information, please follow other related articles on the PHP Chinese website!