Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。
前回: Goでのアルゴリズムクイックリファレンス第2版(二分探索)
今回はハッシュ関数
ハッシュ関数 (ハッシュかんすう、hash function) あるいは要約関数とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことを要約値やハッシュ値または単にハッシュという。
計算量は、最良と平均はO(1)で最悪がO(n)となる。
高速でデータを取り出したい場合によく使われる
package main
import "fmt"
var table [][]int
func loadTable(a *[]int) {
table = make([][]int, len(*a))
for _, e := range *a {
h := hash(e, len(*a))
if table[h] == nil {
table[h] = make([]int, 0)
}
table[h] = append(table[h], e)
}
}
func hash(key int, size int) int {
var h int
for i := 0; i < key+1; i++ {
h = (h*137 + i) % size
}
return h
}
func search(a *[]int, t int) bool {
h := hash(t, len(*a))
list := table[h]
if list == nil {
return false
}
for _, v := range list {
if v == t {
return true
}
}
return false
}
func main() {
a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
loadTable(&a)
fmt.Println(a)
fmt.Printf("0:%t\n", search(&a, 0))
fmt.Println(a)
fmt.Printf("2:%t\n", search(&a, 2))
fmt.Println(a)
fmt.Printf("12:%t\n", search(&a, 12))
}
今回はhash関数を作成するところで以下のサイトを参考にさせていただきました。
次回はブルームフィルタの予定です。