ハッシュテーブルの基本きほん

date2026-07-14document_iddoc_6e5b2ec4e3a69f6ebc84b37f111e6b97descriptionハッシュを、値そのものを探すのでなく置き場所を素早く決める仕組みとして整理し、平均的に高速な探索がなぜ可能かを説明します。prerequisites計算量の基本 / データ構造ポータル / 配列の基本操作type講義statusactive

algorithmdata-structuresundergraduatelecture

data/lecture/information/algorithm/data-structures/data-structures-portal.lecture.n.md

1導入どうにゅう

この講義こうぎでは、辞書じしょ ADT をハッシュテーブルで実装じっそうする方法ほうほうを説明せつめいする。衝突しょうとつを連鎖法れんさほうで処理しょりする場合ばあいについて、負荷率ふかりつと計算量けいさんりょうの関係かんけいを整理せいりする。

2辞書じしょ ADT

辞書じしょ ADTDictionary ADT は、キーの集合しゅうごうを管理かんりし、キーに対応たいおうする値あたいを記録きろくする抽象ちゅうしょうデータ型がたである。検索けんさくは、キーが存在そんざいすれば対応たいおうする値あたいを返かえし、存在そんざいしなければ「未登録みとうろく」を返かえす。挿入そうにゅうは、未登録みとうろくのキーと値あたいを追加ついかし、登録済とうろくずみのキーには対応値たいおうちを置換ちかんする。削除さくじょは、登録済とうろくずみのキーと対応値たいおうちを除去じょきょし、未登録みとうろくのキーには状態じょうたいを変更へんこうしない。キーの順序じゅんじょは仕様しように含ふくまれない。

3ハッシュ関数かんすうとバケット

キーの全体ぜんたいを $U$ 、バケット数すうを $m$ とする。ハッシュ関数かんすうHash function は

h : U \to {0, 1, \dots, m - 1}

によってキーを配列はいれつの添字そえじへ対応たいおうさせる関数かんすうである。バケットBucket は、同一どういつの添字そえじへ対応たいおうしたキーを格納かくのうする領域りょういきである。キー $k$ の操作そうさでは、まず $h (k)$ に対応たいおうするバケットを選択せんたくする。

衝突しょうとつCollision は、相異あいことなるキー $k_{1}, k_{2}$ に対たいして $h (k_{1}) = h (k_{2})$ が成立せいりつすることである。 $U$ の要素数ようそすうが $m$ より大おおきい場合ばあい、鳩はとの巣原理すげんりにより衝突しょうとつは不可避ふかひである。

4連鎖法れんさほう

連鎖法れんさほうSeparate chaining は、各かくバケットにキーと値あたいの列れつを保持ほじし、衝突しょうとつした要素ようそを同一どういつの列れつへ格納かくのうする方式ほうしきである。検索けんさくでは $h (k)$ のバケットだけを走査そうさする。挿入そうにゅうと削除さくじょでも、同おなじバケット内ないでキーを照合しょうごうする。連鎖れんさを連結れんけつリストで実装じっそうする場合ばあい、操作時間そうさじかんはバケット内ないの要素数ようそすうに依存いぞんする。

5負荷率ふかりつと期待計算量きたいけいさんりょう

格納かくのうされているキーの個数こすうを $n$ とする。負荷率ふかりつLoad factor は

α = \frac{n}{m}

である。入力にゅうりょくとなるキー列れつを固定こていし、ハッシュ関数族かんすうぞくから関数かんすうを無作為むさくいに選択せんたくしたとき、各かくキーが $m$ 個このバケットへ一様いちようかつ独立どくりつに対応たいおうするという単純一様たんじゅんいちようハッシュ仮定かていSimple uniform hashing assumptionを置おく。期待値きたいちはこの無作為選択むさくいせんたくについて取とる。この仮定かていの下もとでは、バケットの期待要素数きたいようそすうは $α$ である。したがって、連鎖法れんさほうによる検索けんさく・挿入そうにゅう・削除さくじょの期待時間きたいじかんは $O (1 + α)$ となる。 $α$ を定数ていすう以下いかに維持いじすれば、各操作かくそうさの期待時間きたいじかんは $O (1)$ である。

これは任意にんいのハッシュ関数かんすうに対たいする決定的けっていてきな保証ほしょうではない。すべてのキーが単一たんいつのバケットへ集中しゅうちゅうする場合ばあい、検索けんさく・挿入そうにゅう・削除さくじょの最悪時間さいあくじかんは $O (n)$ となる。

6リサイズ

リサイズResizing は、負荷率ふかりつが所定しょていの閾値しきいちを超過ちょうかしたときに、より大おおきいバケット配列はいれつを確保かくほし、すべてのキーを再配置さいはいちする操作そうさである。バケット数すうが変化へんかするとハッシュ値ちの範囲はんいも変化へんかするため、既存きそんの要素ようそをそのまま複製ふくせいするだけでは不十分ふじゅうぶんであり、各かくキーのバケットを再計算さいけいさんする必要ひつようがある。

1 回かいのリサイズには $O (n)$ 時間じかんを要ようする。ただし、バケット数すうを定数倍ていすうばいに拡大かくだいする方式ほうしきでは、多数たすうの挿入そうにゅうにリサイズ費用ひようを配分はいぶんできる。リサイズ後ごにも単純一様たんじゅんいちようハッシュ仮定かていを満みたす関数かんすうを選択せんたくし、 $α$ を定数ていすう以下いかに維持いじし、1 回かいのハッシュ計算けいさんを $O (1)$ とする。このとき、挿入そうにゅうの償却期待時間しょうきゃくきたいじかんは $O (1)$ となる。

7適用範囲てきようはんい

キーの完全一致かんぜんいっちによる検索けんさくにはハッシュテーブルが適てきする。
キーの大小順だいしょうじゅん、範囲検索はんいけんさく、最小値さいしょうちを直接ちょくせつ扱あつかう場合ばあいには、平衡探索木へいこうたんさくぎなどの順序じゅんじょを保持ほじするデータ構造こうぞうが適てきする。

8まとめ

ハッシュテーブルは、ハッシュ関数かんすうでバケットを選択せんたくし、連鎖法れんさほうで衝突しょうとつを処理しょりする。単純一様たんじゅんいちようハッシュ仮定かていと有界ゆうかいな負荷率ふかりつの下もとでは辞書操作じしょそうさを期待きたい $O (1)$ 時間じかんで実行じっこうできるが、最悪時間さいあくじかんは $O (n)$ である。