golangでハッシュマップを実装する方法

golang 言語に付属のマップ構造は非常に便利なデータ型ですが、より効率的かつ柔軟なデータ操作のために、golang に実装されたハッシュマップの使用を選択できます。この記事では、golang がハッシュマップを実装する方法を紹介します。

1. 実装原理

Golang のハッシュマップ実装原理は非常に単純で、特定のアルゴリズムを通じてキーと値のペアを配列にマッピングし、リンク リストを使用して解決することです。ハッシュの競合。具体的には、ハッシュマップの実装には次の手順が必要です。

1. 配列サイズが 2 の n 乗 (n は調整可能) の配列を作成します。
2. 挿入する各キーと値のペアのハッシュ値を計算し、そのハッシュ値を使用して配列サイズを剰余し、配列内での位置を取得します。
3. その位置が空の場合は、配列内のその位置にあるリンク リストにキーと値のペアを直接挿入します。
4. この位置にすでに値がある場合は、この位置のリンク リストを走査して、同じキーが存在するかどうかを確認します。存在する場合は、対応する値を更新します。存在しない場合は、ノードを直接挿入します。リンクされたリストの最後に追加します。
5. キーと値のペアを検索する場合は、まずハッシュ値を使用して配列サイズを剰余して配列内の位置を取得し、次にその位置でリンクされたリストを走査して、対応するキーの値を見つけます。 。

2. 実装コード

次は、ハッシュマップを実装するための簡単な golang コードです:

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. 使用例

使用例は次のとおりです。以下の通り ：

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. まとめ

golang を介してハッシュマップを実装すると、効率的かつ柔軟なデータ操作が容易になります。ハッシュマップの実装原理は非常に単純で、主にハッシュ アルゴリズムを通じてキーと値のペアを配列にマッピングし、リンク リストを使用してハッシュの競合を解決します。使用例のコードは参考として使用することができ、必要に応じて最適化および改善することもできます。

以上がgolangでハッシュマップを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。