【Goで学ぶコンピューターサイエンス】ハッシュテーブル

ハッシュテーブル

データをキーと値のペアで管理し、高速なデータの格納・検索を可能にするデータ構造です。
内部では ハッシュ関数 を使用してキーを特定のインデックス（ハッシュ値）に変換し、そのインデックスを使ってデータを効率よく格納します。

特徴

• 時間計算量
  • 平均的には、検索、挿入、削除の操作を $O(1)$ で行えます。（ただし、最悪 $O(n)$ になることもあります）
• キーと値のペア
  • データは「キー」を使ってアクセスします
• ハッシュ関数
  • キーをインデックスに変換するための関数で、ハッシュテーブルの効率性に大きく影響します。

ハッシュテーブルの仕組み

• ハッシュ関数

  • キーを入力として受け取り、一定範囲の整数（ハッシュ値）を出力します

• バケット

  • ハッシュ値によってデータが格納される配列の各要素を指します
  • 配列のように直接インデックスにアクセスすることで、高速な検索が可能です

• 衝突

  • 異なるキーが同じハッシュ値になる場合です
  • 衝突を解決する方法として以下の手法があります
    • チェイニング
      • バケットにリストを格納して複数の値を保持
    • オープンアドレス法
      • 空いている別のバケットを探して格納

ハッシュテーブルの利点

• 高速なデータ操作
  • 配列と同様、インデックスで直接アクセスするため効率的
• 柔軟なキー管理
  • 数値や文字列など、さまざまなキーを使用可能
• 動的サイズ変更
  • ハッシュテーブルのサイズを動的に変更して効率性を維持できます

ハッシュテーブルの欠点

• メモリ使用量
  • バケットの数を多く用意する必要があるため、メモリ消費が多くなる場合があります
• データ順序非保持
  • データはハッシュ値の順序で格納されるため、挿入順序を保持しません

ハッシュテーブルのGoサンプルコード

package main

import "fmt"

type KeyValuePair struct {
	key   string
	value string
}

type HashTable struct {
	size    int
	buckets [][]KeyValuePair
}

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

func (ht *HashTable) Hash(key string) int {
	hash := 0
	for _, char := range key {
		hash += int(char)
	}
	return hash % ht.size
}

func (ht *HashTable) Insert(key, value string) {
	index := ht.Hash(key)
	ht.buckets[index] = append(ht.buckets[index], KeyValuePair{key: key, value: value})
}

func (ht *HashTable) Search(key string) (string, bool) {
	index := ht.Hash(key)
	for _, pair := range ht.buckets[index] {
		if pair.key == key {
			return pair.value, true
		}
	}
	return "", false
}

func (ht *HashTable) Delete(key string) {
	index := ht.Hash(key)
	for i, pair := range ht.buckets[index] {
		if pair.key == key {
			ht.buckets[index] = append(ht.buckets[index][:i], ht.buckets[index][i+1:]...)
			return
		}
	}
}

func main() {
	ht := NewHashTable(10)

	ht.Insert("apple", "red")
	ht.Insert("banana", "yellow")
	ht.Insert("grape", "purple")

	fmt.Printf("%+v\n", ht)

	value, found := ht.Search("apple")
	if found {
		fmt.Println("Found:", value)
	} else {
		fmt.Println("Not Found")
	}

	ht.Delete("banana")
	fmt.Printf("%+v\n", ht)

	value, found = ht.Search("banana")
	if found {
		fmt.Println("Found:", value)
	} else {
		fmt.Println("Not Found")
	}
}

&{size:10 buckets:[[{key:apple value:red}] [] [] [] [] [] [] [{key:grape value:purple}] [] [{key:banana value:yellow}]]}
Found: red
&{size:10 buckets:[[{key:apple value:red}] [] [] [] [] [] [] [{key:grape value:purple}] [] []]}
Not Found