Hash Table

ハッシュテーブル（Hash Table）はハッシュ関数でキーをバケット配列に写し、平均 O(1) の検索・挿入・削除を提供する、最も使われるデータ構造の一つである。

目的

平均定数時間のキー値アクセスを提供し、辞書と集合を効率的に実装する。

メカニズム

hash(key) % capacity でバケットを特定する。衝突処理：連結リスト（バケットがリストを持つ）または開放アドレス法（次の空きスロットを探索）。負荷率 = 要素数／バケット数で、しきい値を超えるとリサイズと再ハッシュが行われる。良いハッシュ関数はキーを一様に分布させる。

ユースケース

辞書とマップの実装
データベースインデックス
キャッシュ（LRU）
重複排除（デデュープ）と集合

例

入力

{"name":"Ada"} → hash("name")=5

Output

Value stored in bucket 5

O(1) on average

よくあるエラー

A poorly distributed hash function causes collision pile-ups: Use a high-quality hash function and a suitable load factor

関連用語

ブルームフィルタは k 個のハッシュ関数とビット配列で集合の所属を近似し、偽陽性率と引き換えに容量効率を得る。

ビッグ O 記法は関数の漸近的上界を表し、定数と低次の項を無視してアルゴリズムの時間・空間計算量を分析するのに使われる。

関連ツール

DJB2 ハッシュ

Djb2 — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

SDBM ハッシュ

Sdbm — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

Zobrist ハッシュ

Zobrist — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

Pearson ハッシュ

Pearson — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

ELFHash ハッシュ

Elfhash — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

References