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

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)$ である。

Hash Table Basics

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

1Introduction

This lecture explains how a hash table implements the dictionary ADT. For separate chaining, it relates the load factor to operation complexity.

2Dictionary ADT

The dictionary ADTDictionary ADT is an abstract data type that maintains a set of keys and records a value associated with each key. Lookup returns the associated value for a present key and an “absent” result otherwise. Insertion adds an absent key-value pair and replaces the associated value of a present key. Deletion removes a present key and its value and leaves the state unchanged for an absent key. The specification does not require an ordering of the keys.

3Hash Functions and Buckets

Let $U$ be the universe of keys and let $m$ be the number of buckets. A hash functionHash function is a function

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

that maps a key to an array index. A bucketBucket is the storage region for keys mapped to the same index. An operation on key $k$ first selects the bucket indexed by $h (k)$ .

A collisionCollision occurs when $h (k_{1}) = h (k_{2})$ for two distinct keys $k_{1}$ and $k_{2}$ . If the cardinality of $U$ exceeds $m$ , the pigeonhole principle makes collisions unavoidable.

4Separate Chaining

Separate chainingSeparate chaining stores a sequence of key-value pairs in every bucket and places colliding entries in the same sequence. Lookup scans only the bucket selected by $h (k)$ . Insertion and deletion likewise compare keys within that bucket. When each chain is implemented as a linked list, an operation's running time depends on the number of entries in its bucket.

5Load Factor and Expected Complexity

Let $n$ be the number of stored keys. The load factorLoad factor is

α = \frac{n}{m} .

Fix the input sequence of keys and choose a function randomly from a hash-function family. Assume simple uniform hashingSimple uniform hashing assumption: each key maps independently and uniformly to one of the $m$ buckets. The expectation is over this random choice. Under the assumption, the expected number of entries in a bucket is $α$ . Lookup, insertion, and deletion with separate chaining therefore take expected time $O (1 + α)$ . If $α$ is kept below a constant, each operation takes expected time $O (1)$ .

This conclusion is not a deterministic guarantee for every hash function. If all keys map to one bucket, lookup, insertion, and deletion take $O (n)$ time in the worst case.

6Resizing

ResizingResizing allocates a larger bucket array and redistributes all keys when the load factor exceeds a prescribed threshold. Because changing the bucket count changes the range of hash values, merely copying the existing entries is insufficient: the bucket of every key must be recomputed.

A single resize takes $O (n)$ time. If the bucket count grows by a constant factor, however, its cost can be distributed over many insertions. Assume that after resizing a function satisfying simple uniform hashing is selected, that $α$ remains bounded by a constant, and that one hash computation takes $O (1)$ time. Insertion then takes $O (1)$ amortized expected time.

7Scope of Application

Hash tables are appropriate for exact-key lookup.
When an application directly requires sorted keys, range queries, or a minimum key, an order-preserving data structure such as a balanced search tree is more appropriate.

8Summary

A hash table selects a bucket with a hash function and resolves collisions by separate chaining. Under simple uniform hashing and a bounded load factor, dictionary operations take expected $O (1)$ time, whereas their worst-case time is $O (n)$ .