ハッシュテーブル

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

特徴

時間計算量
- 平均的には、検索、挿入、削除の操作を $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