Zenn
🐰

ハッシュ関数ってなんぞや

2024/05/18に公開
Go
ハッシュ関数
tech

ハッシュ関数は、入力（キー）を固定サイズの値（ハッシュ値）に変換する関数です。ハッシュ関数の主な目的は、異なるキーを可能な限り異なるインデックスにマッピングすることです。これにより、ハッシュテーブルのバケットへのアクセスが効率的になります。

ハッシュ関数の基本的な特性

  1. 決定性: 同じ入力に対して常に同じハッシュ値を返します。
  2. 高速計算: 入力サイズに対して効率的に計算されます。
  3. 均等分布: 入力が均等にバケットに分布するように設計されています。

ハッシュ関数の一般的な構造

ハッシュ関数の設計には多くの方法がありますが、ここでは単純な例をいくつか紹介します。

例1: 簡単な整数ハッシュ関数

整数をハッシュする単純な方法は、整数値をテーブルのサイズで割った余りを返すことです。

func simpleHash(key int, tableSize int) int {
    return key % tableSize
}

例2: 文字列のハッシュ関数

文字列のハッシュには、各文字の値を使ってハッシュ値を計算する方法があります。以下は簡単な例です。

func stringHash(s string, tableSize int) int {
    hash := 0
    for i := 0; i < len(s); i++ {
        hash = (31*hash + int(s[i])) % tableSize
    }
    return hash
}

このハッシュ関数は、文字列の各文字のASCII値を使ってハッシュ値を計算します。31は一般的に使われる素数で、ハッシュ値の分布を均等にするのに役立ちます。

Go言語におけるハッシュ関数

Go言語の map は内部で複雑なハッシュ関数を使用しています。標準ライブラリ内で直接ハッシュ関数を確認することはできませんが、Goの内部では、効率的で分布の良いハッシュ関数が使われています。

ハッシュ関数の例と衝突解決

ハッシュ関数の例（整数ハッシュ）

以下は、整数をキーとする簡単なハッシュ関数の例です。

package main

import (
    "fmt"
)

const tableSize = 10

func hashFunction(key int) int {
    return key % tableSize
}

func main() {
    keys := []int{1, 2, 3, 11, 12, 13}
    for _, key := range keys {
        fmt.Printf("Key: %d, Hash: %d\n", key, hashFunction(key))
    }
}

このコードでは、キー 1, 2, 3, 11, 12, 13 をハッシュテーブルサイズ 10 で割った余りを計算し、ハッシュ値を出力します。

衝突解決方法

  1. チェイン法 (Separate Chaining):
    • 各バケットがリストを保持し、衝突が発生した場合にリストに追加します。
    • 以下はGoでの擬似的なチェイン法の例です。
type Entry struct {
    key   string
    value int
}

type HashTable struct {
    table map[int][]Entry
}

func NewHashTable(size int) *HashTable {
    return &HashTable{table: make(map[int][]Entry, size)}
}

func (ht *HashTable) Put(key string, value int) {
    index := hashFunction(key)
    ht.table[index] = append(ht.table[index], Entry{key, value})
}

func hashFunction(key string) int {
    hash := 0
    for i := 0; i < len(key); i++ {
        hash = (31*hash + int(key[i])) % tableSize
    }
    return hash
}

func main() {
    ht := NewHashTable(tableSize)
    ht.Put("cat", 1)
    ht.Put("dog", 2)
    ht.Put("bat", 3)

    fmt.Println(ht.table)
}
  1. オープンアドレス法 (Open Addressing):
    • 衝突が発生した場合に他の空いているバケットを探します。
    • 以下はGoでの擬似的なオープンアドレス法の例です。
type HashTable struct {
    table []Entry
}

type Entry struct {
    key   string
    value int
}

func NewHashTable(size int) *HashTable {
    return &HashTable{table: make([]Entry, size)}
}

func (ht *HashTable) Put(key string, value int) {
    index := hashFunction(key)
    for ht.table[index].key != "" {
        index = (index + 1) % tableSize
    }
    ht.table[index] = Entry{key, value}
}

func hashFunction(key string) int {
    hash := 0
    for i := 0; i < len(key); i++ {
        hash = (31*hash + int(key[i])) % tableSize
    }
    return hash
}

func main() {
    ht := NewHashTable(tableSize)
    ht.Put("cat", 1)
    ht.Put("dog", 2)
    ht.Put("bat", 3)

    fmt.Println(ht.table)
}

このように、ハッシュ関数と衝突解決方法を組み合わせることで、ハッシュマップの効率的な動作が保証されます。

Discussion