ハッシュテーブルとは
はっしゅてーぶる
キーからハッシュ関数で格納する位置を計算し、平均 O(1) で探索・挿入・削除ができるデータ構造。異なるキーが同じ位置になる衝突を、チェイン法やオープンアドレス法で処理する。ハッシュ表ともいう。
「ハッシュテーブル」は、4分野の7問の練習問題に出てきます(データ構造とアルゴリズム, 確率・統計と待ち行列, メモリ階層と性能など)。
この用語の分野: データ構造とアルゴリズム
しくみと衝突の処理
ハッシュテーブルは、キーをハッシュ関数で整数に変え、表の大きさで割った余りなどを格納する位置にします。キーの種類は表の大きさよりはるかに多いので、異なるキーが同じ位置になる衝突は避けられません。チェイン法は、同じ位置の要素を連結リストなどでつなぎます。オープンアドレス法は、表の中の別の空いている位置を探し、隣を順に調べる線形探査や、別のハッシュ関数で間隔を決める二重ハッシュなどがあります。
負荷率とリハッシュ
格納した要素の数を表の大きさで割った値を負荷率といいます。チェイン法ではリストの平均の長さが負荷率に比例し、オープンアドレス法では負荷率が1に近づくと空きを探す回数が急に増えます。そのため、負荷率が決めた値を超えたら、表を2倍程度に大きくして全要素を入れ直します(リハッシュ)。1回のリハッシュは O(n) かかりますが、大きくする間隔が倍々に広がるので、追加1回あたりの手間は償却 O(1) に収まります。
性能と注意点
平均 O(1) は、ハッシュ関数がキーを表全体にばらつかせることが前提です。偏ったハッシュ関数や、意図的に衝突を起こす入力(ハッシュフラッディング攻撃)では、最悪 O(n) まで遅くなるので、Webサーバなどでは乱数の種を混ぜたハッシュ関数を使います。また、ハッシュテーブルは要素を順に並べて持たないので、範囲の検索や順番どおりの列挙には、二分探索木やB木の方が向いています。実際の速さはキャッシュの効き方にも左右され、線形探査のように隣を調べる方式は、ポインタをたどるチェイン法より速いことが多くなります。
ハッシュテーブルの練習問題に挑戦
10個のキーを、100個のバケットを持つハッシュ表に入れる。各キーは、それぞれ独立に、100個のバケットのどれかに等しい確率で割り当てられるとする。2つのキーの組のうち、同じバケットに割り当てられる組の数の期待値はどれか。
- A0.1
- B0.45
- C0.9
答えと解説を見る
正解：B. 0.45
10個のキーから2つを選ぶ組は 10C2 = 45組あり、それぞれの組が同じバケットに入る確率は1/100です。期待値の線形性(和の期待値は期待値の和)により、同じバケットに入る組の数の期待値は 45 × 1/100 = 0.45 です。期待値の線形性は組どうしが独立でなくても成り立つので、組ごとの確率を足すだけで求められます。
ハッシュテーブル(ハッシュ表)における衝突(コリジョン)の説明として正しいものはどれか。
- Aハッシュ値から元のキーが求められてしまうこと
- B異なるキーから同じハッシュ値(格納する位置)が求まること
- C同じキーから、実行するたびに違うハッシュ値が求まること
よくある質問
ハッシュテーブルとハッシュ関数の関係は何ですか?
ハッシュ関数は、キーから決まった範囲の値を計算する関数で、ハッシュテーブルはそれを格納する位置の計算に使うデータ構造です。ハッシュテーブル用のハッシュ関数は速さとばらつきの良さを重視し、暗号用のハッシュ関数のような一方向性までは求めないのが普通です。
ハッシュテーブルはどこで使われていますか?
プログラミング言語の辞書(連想配列)やセット、コンパイラの記号表、データベースのハッシュ結合やハッシュ索引、キャッシュの管理など、キーで値を素早く引く場面の多くで使われます。
解説の中の「ハッシュテーブル」
ハッシュテーブルは、キーからハッシュ関数で格納する位置を計算し、平均 O(1) で探索・挿入・削除ができるデータ構造です。
ハッシュテーブル(ハッシュ表)における衝突(コリジョン)の説明として正しいものはどれか。ランダムなキーでのハッシュ表の参照も、アドレスに規則性がないため効果は小さくなります。
ハードウェアのプリフェッチが特に効果を発揮しやすいアクセスはどれか。ハッシュ表のバケットごとにロックを分けるような細かい粒度にすれば、別の部分は同時に操作できます。
大きなデータ構造全体を1つのロックで守る「粗い粒度のロック」と、部分ごとに別のロックで守る「細かい粒度のロック」を比べ…
「ハッシュテーブル」が出てくる問題(7問)
- 10個のキーを、100個のバケットを持つハッシュ表に入れる。各キーは、それぞれ独立に、100個のバケットのどれかに等しい確率で割り当てられるとする。2つのキーの組のうち、同じバケットに割り当てられる組の数の期待値はどれか。
- ハッシュテーブル(ハッシュ表)における衝突(コリジョン)の説明として正しいものはどれか。
- 大きさ7のハッシュテーブル(位置0〜6)に、ハッシュ関数 h(k) = k mod 7 でキー10、17、24、3をこの順に格納する。衝突したときは、位置を1つずつ後ろへずらして(6の次は0)空いている位置を探す線形探査法を使う。キー3が格納される位置はどれか。
- ハッシュテーブルの衝突を処理する方法として、チェイン法(同じ位置の要素を連結リストでつなぐ)とオープンアドレス法(表の中の空いている別の位置を探す)を比べた説明として正しいものはどれか。負荷率は、格納した要素数を表の大きさで割った値とする。
- 要素数が多く、負荷率を0.5程度に保ったハッシュテーブルで、線形探査のオープンアドレス法が、チェイン法(連結リストでつなぐ方法)より速くなりやすい理由として最も適切なものはどれか。
- ハードウェアのプリフェッチが特に効果を発揮しやすいアクセスはどれか。
- 大きなデータ構造全体を1つのロックで守る「粗い粒度のロック」と、部分ごとに別のロックで守る「細かい粒度のロック」を比べた説明として正しいものはどれか。
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。