科目B頻出のハッシュテーブル。挿入・検索・衝突処理 (チェイン法) を擬似言語で読みこなします。
日野 こむぎ
ハッシュテーブルって、擬似言語ではどう表現するの?
藤森 さやか 先生
配列とハッシュ関数を組み合わせるの。
簡単な例で見てみましょう。
青木 澪
ハッシュ関数は「キーを配列のインデックスに変換」する関数。
例えば整数キーなら、キー mod 配列サイズ で簡単な実装ができるわ。
/* ハッシュ関数: キー→インデックス */
○ 手続: hash(整数型: key, 整数型: size)
return key mod size + 1 /* 1始まりに調整 */
/* 単純な挿入 (衝突無視) */
○ 手続: insert(整数型の配列: table, 整数型: key, 整数型: size)
整数型: idx
idx ← hash(key, size)
table[idx] ← key
/* 検索 */
○ 手続: search(整数型の配列: table, 整数型: key, 整数型: size)
整数型: idx
idx ← hash(key, size)
if (table[idx] = key)
return idx
else
return -1
endif
桃井 すみれ
衝突 (collision) のときはどうするんですかぁ?
青木 澪
代表的な対策が「チェイン法」: 同じインデックスに複数の値が来たら、連結リストで繋ぐの。
/* チェイン法での挿入 (連結リストの先頭に追加) */
○ 手続: insertChain(リスト型の配列: table, 整数型: key, 整数型: size)
整数型: idx
idx ← hash(key, size)
/* table[idx] に key を含む新ノードを先頭追加 */
table[idx] ← addFirst(table[idx], key)
/* チェイン法での検索 */
○ 手続: searchChain(リスト型の配列: table, 整数型: key, 整数型: size)
整数型: idx
ノード型: cur
idx ← hash(key, size)
cur ← table[idx]
while (cur ≠ null)
if (cur.value = key)
return 真
endif
cur ← cur.next
endwhile
return 偽
日野 こむぎ
衝突がなければ O(1)、衝突があると最悪 O(n) ってやつだね!
藤森 さやか 先生
そうなのよ。
試験では「ハッシュ関数 hash(k) = k mod 7、配列サイズ7、キー 14, 21, 8 を順に挿入したときの状態は?」みたいな問題が定番ね。
青木 澪
計算してみると、14 mod 7 = 0、21 mod 7 = 0 (衝突!)、8 mod 7 = 1。
チェイン法ならインデックス0に [21,14] (先頭追加方式)、インデックス1に [8] が入るわ。
確認クイズ
ハッシュテーブルでキーが衝突したとき、同じインデックスに連結リストで繋いで管理する手法はどれか。
- チェイン法
- オープンアドレス法
- リハッシュ法
- 二重ハッシュ法
こたえを見る
正解: 1. チェイン法
チェイン法 (Chaining) は同じハッシュ値の要素を連結リストで管理する衝突対策。実装が単純で、削除も簡単という利点があります。
