こんにちは。KOUKIです。
とあるWeb系企業でGoエンジニアをしています。
Golangでアルゴリズムの学習をしましょう!
今回は、ハッシュ関数を自作したいと思います。ハッシュを作成するためのパッケージは既にGoには存在するのですが、頭の体操になると思います^^
<目次>
課題
以下の文字列のハッシュ値を返すプログラムを実装しよう。
「Selfnote is the most wonderful blog in the world!」
回答
実装方法はいくつかあると思いますが、私は以下のように実装しました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package main import "fmt" type HashTable struct { data []int } func NewHashTable(size int) *HashTable { return &HashTable{ data: make([]int, size), } } func (h HashTable) _hash(key string) int { hash := 0 for i := 0; i < len(key); i++ { hash = (hash + int([]rune(string(key[i]))[0])) } return hash } func main() { myHashTable := NewHashTable(50) fmt.Println(myHashTable._hash("Selfnote is the most wonderful blog in the world!")) } |
単純な処理であるため解説は不要かと思うので、プログラムを実行してみましょう。
|
1 2 3 4 5 6 7 8 |
$ go run hash/main.go 4603 $ go run hash/main.go 4603 $ go run hash/main.go 4603 |
常に同じ値の返してますね。文字列を以下のように変更してみましょう。
「Selfnote is the most wonderful blog in the world! but, there are many blogs is more wonderfule thant selfnote after all!」
|
1 2 3 4 5 6 7 8 |
$ go run hash/main.go 11203 $ go run hash/main.go 11203 $ go run hash/main.go 11203 |
OKですね。現在は数値だけですが、文字や記号などを組み込むともっといい感じになると思います。
まとめ
今回のアルゴリズムの肝は、「同じ文字列を引数で渡した時、常に同じ結果を返すにはどうしたらいいのだろう」ということを考えることにあります。
このようなことを考えていてくとatomicなプログラムを書くときにも役立つ…かもしれません^^
それでは、また!
Go記事まとめ
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package main import "fmt" type HashTable struct { data []int } func NewHashTable(size int) *HashTable { return &HashTable{ data: make([]int, size), } } func (h HashTable) _hash(key string) int { hash := 0 for i := 0; i < len(key); i++ { hash = (hash + int([]rune(string(key[i]))[0])) } return hash } func main() { myHashTable := NewHashTable(50) fmt.Println(myHashTable._hash("Selfnote is the most wonderful blog in the world! but, there are many blogs is more wonderfule thant selfnote after all!")) } |
にほんブログ村
コメントを残す
コメントを投稿するにはログインしてください。