概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

ハッシュマップ

• ハッシュ値を添え字とした配列
• ハッシュの衝突処理
  • 開番地法
    • 衝突が生じた際に、ハッシュ関数とは別の関数を使って別の番地を求める方法。
  • 連鎖法
    • 衝突が生じても新しい番地を求めずに、衝突した番地に衝突したキー同士をポインタでつないだリンクリストを格納することで対応する方式。

計算時間

データへのアクセス

• O(1)
• 添字を使ってランダムアクセスが可能。

データの追加

• O(1)
• 配列の場合は、線形探索で追加箇所を探索する必要があるため、O(n)だが、ハッシュテーブルは、データの追加’箇所をハッシュによって求めるのでO(1)で済む。
• ハッシュが衝突した場合はこの限りではない。

実装

以下はハッシュ値の衝突を考慮していない粗雑なハッシュマップ。

package main

import "fmt"

// A HashMap is hash map.
type HashMap struct {
    data map[int]string
}

// hash is create a hash key.
func hash(key int) int {
    return key % 5
}

// put is add key to hash map.
func (h HashMap) put(key int, value string) {
    hash := hash(key)
    if h.data == nil {
        h.data = make(map[int]string)
    }
    h.data[hash] = value
}

// get is get a value from hash map.
func (h HashMap) get(key int) string {
    var hash int = hash(key)

    return h.data[hash]
}

func main() {
    h := &HashMap{
        data: make(map[int]string),
    }

    h.put(1, "foo")
    h.put(2, "bar")

    fmt.Printf("%#v\n", h.get(1))
    fmt.Printf("%#v\n", h.get(2))
}

• ハッシュ関数のアルゴリズムは色々ある。
  • cf. wikipedia - ハッシュ関数

参考

• Wikipedia - ハッシュテーブル
• github.com - flaviocopes/datastructures/blob/master/hashtable/hashtable.go