ハッシュテーブル

2024年8月9日 #Hashtable #Hashing

概要

ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。これは \(x \mapsto y\) という射を表しているため写像 (map) の具体的な表現の一つという見方もある。

ハッシュテーブルが探索木と異なるのは、検索の典型的な期待実行時間が定数時間 \(O(1)\) となることである。

ハッシュテーブルには静的と動的の 2 種類がある。静的 (static) ハッシュテーブルは内容が変化しないことを前提としており、高速な検索操作のみをサポートする。動的 (dynamic) ハッシュテーブルは検索に加えて挿入と時に削除をサポートし、それぞれの操作はそれなりの性能で動作することが求められる。

概要
基本的な構造
チェーン法
線形プローブ法
カッコウハッシュ法
Hopscotch ハッシュ法
参考文献

基本的な構造

ハッシュテーブルの基本的なアイディアは、あるハッシュ関数によって得られたハッシュ値に基づくインデックスのエントリ (entry) に要素 (Key-Value ペア) を配置することである。エントリは 1 次元の配列であることから、理想的なハッシュテーブルは \(O(1)\) で要素にアクセスできる。

異なる要素に対して同じハッシュ値が生成されることを衝突 (collision) と呼ぶ。衝突はハッシュ関数の値域 (出力範囲) が有限であるため正確には全単射ではなく全射であることから生じる。値 \(A\) と \(B\) のハッシュ値が衝突する場合、\(B\) は \(A\) の、または \(A\) は \(B\) の競合やシノニム (synonym) であると言う。

ハッシュテーブルで衝突が発生すると複数の要素が同じテーブルエントリに割り当てられることになる。このような状況でどのように競合を解決し、すべての要素を保持するかがハッシュテーブルアルゴリズムの主な違いである。

ハッシュ関数が一様にランダムな理想的なハッシュ値を生成するならば、\(n\) 個の要素を \(n\) 個のエントリに入れるとき、少なくとも \(1-\frac{1}{n}\) の確率でもっとも要素の入るエントリは \(O(\frac{\log n}{\log \log n})\) 個の要素が割り当てられる [1, 4]。ハッシュテーブル内での衝突の数がこのような対数的なサイズの上限を超えることはほぼ確実にない [2]。

ハッシュテーブルが構成するエントリの個数 (テーブルサイズ) を \(m\)、テーブルに格納されている要素数を \(n\) としたとき、負荷係数 (load factor) を \(\alpha=\frac{n}{m}\) と表す。一般に、ハッシュテーブルの負荷係数が特定のしきい値を超えたとき、テーブルサイズを拡大するようなリハッシュ (再ハッシュ、再配置) が行われる。ハッシュテーブルのリハッシュは \(O(n)\) のようなコストがかかるが、通常の 1 回の挿入操作に十分分散できることからその計算コストは償却され (amortized; ならされ) 無視できると見なされている。

各テーブルエントリが 1 つの要素を保存する手法をオープンアドレス法 (open addressing) と呼ぶ。一般にオープンアドレス法ではハッシュ値によって示された特定のエントリを起点に空いているエントリを探索して要素を配置するアルゴリズムである。これに対して各テーブルエントリが複数の要素を保存する (いわゆるバケット (bucket) になっている) 手法をクローズアドレス法 (closed addressing) と呼ぶ [6]。

チェーン法

ハッシュ値の衝突に対処する方法の一つにチェーン法 (separate chaining, chained hashing) がある。これはテーブルエントリにリンクリストや平衡二分木のようなバケット構造を持たせ、衝突したすべての要素をそれに格納するクローズアドレス法である。したがって衝突が起きたときの挿入 (置換)、検索、削除の操作はそのデータ構造の操作と等価である。

チェーン法の期待計算量は \(O(1+\alpha)\)、最悪計算量は \(O(n)\) で表される。また負荷係数 \(\alpha\) があるしきい値 (例えば 0.75) を超えたときにバケットサイズを拡張するリハッシュを行うように実装する。いくつかの論文の性能比較を参照すると、チェーン法はハッシュテーブルの中で最速ではないものの contains(), add(), remove() の基本的な操作で安定した性能を持ってる。

チェーン法を使用した実装例としては Java の Hashtableや HashMapがある。これらはリンクリストに基づいたバケットを実装している。

線形プローブ法

線形プローブ法または線形探索法 (linear probing) は各エントリが特定のデータ構造を持たず 1 つの要素のみを格納できるオープンアドレス法の一種である。配列として並んでいるエントリから対象の要素、または空きエントリを線形探索することで行われる (エントリの末尾に到達した場合は先頭から再開する)。

各操作の挙動は次のようになる。

挿入: 探索中に空きエントリを検出した場合、単純にその空きエントリに要素を格納する。同じ要素を見つけた場合は既に同じ要素が登録されていることを意味するため、その要素を置き換える。探索開始位置に戻った場合はハッシュテーブルがいっぱいになっていることを意味しているため、エントリサイズを拡張するリハッシュを行うか挿入を拒否する必要がある。
検索: 空きエントリを検出するまで検索対象の要素を探索する。空きエントリを検出したり探索開始位置に戻った場合、その要素はハッシュテーブルに存在しないことを意味する。
削除: 空きエントリを検出するまで削除対象の要素を探索する。削除対象の要素を見つけたら、そのエントリに削除マークを付ける (エントリを空にすると他の要素の探索に不整合が発生する点に注意)。探索中に空きエントリを検出したり探索開始位置に戻った場合、削除対象の要素はハッシュテーブルに存在しないことを意味する。

線形プローブ法はチェーン法より単純な構造を持つが、各操作の期待計算量は \(O(\log n)\)、最悪計算量は \(O(n)\) になる。ここで \(n\) はハッシュテーブルに格納されている全要素数である。ただし、エントリがメモリ上に連続して配置されているため高速なキャッシュアクセスの恩恵を受けることができる。線形プローブ法の効率を改善するために二次プローブ、二重ハッシュ法 (double hashing) などのオープンアドレス法の変種が存在する。

カッコウハッシュ法

カッコウハッシュ法 (Cuckoo hashing) [3, 6] はオープンアドレス法の一種で、2 つ以上のハッシュ関数とテーブルを使用して要素を格納する。衝突が発生した場合、もともとあった要素を再帰的に別のテーブルに「追い出し」て要素を格納することで衝突を解消する (この動作がカッコウの托卵に似ていることからカッコウハッシュ法と呼ばれる)。

カッコウハッシュ法の検索は必ず \(O(1)\) となるが、挿入時には多数の再配置が発生することによるパフォーマンスの低下や、無限ループを解消するためのリハッシュが必要になることがある。

挿入: 要素 \(A\) を挿入するとき、\(T_1[h_1(A)]\) または \(T_2[h_2(A)]\) の空いているエントリがあればそこに格納する。両方のエントリともすでに別の要素が格納されている場合、\(T_1[h_1(A)]\) のエントリに格納する。\(T_1[h_1(A)]\) に元々あった要素 \(B\) は \(T_2[h_2(B)]\) に移動する。\(T_2[h_2(B)]\) に元々あった要素 \(C\) は\(T_1[h_1(C)]\) に移動する。これを要素の移動先が空のエントリになるまで再帰的に繰り返す。

Fig 4 はこの操作を示した図である。

\(T_1[h_1(A)]\) が空いていれば \(T_1[h_1(A)]\) のエントリに格納する。

\(T_1[h_1(A)]\) に別の要素が格納されており、かつ、\(T_2[h_2(A)]\) が空いていれば \(T_2[h_2(A)]\) のエントリに格納する。

\(T_1[h_1(A)]\) と \(T_2[h_2(A)]\) の両方に別の要素が格納されていた場合、空のエントリに要素を移動するまで再帰的に処理する。

Fig 4. カッコウハッシュ法における要素の挿入操作。

このような衝突時の再帰的な再配置はやや複雑だが、結局のところ Fig 5 のように特定の要素 \(x\) は \(T_1[h_1(x)]\), \(T_2[h_2(x)]\) 間でしか移動しない点に注意。

Fig 5. 要素 \(x\) は \(T_1[h_1(x)]\) または \(T_2[h_2(x)]\) のいずれかに存在する。

Fig 6. 衝突の追い出しが無限ループになるケース。

ハッシュテーブルの負荷係数が高くなると、一度の挿入でこのような要素の再配置が多数行われるようになり挿入パフォーマンスが低下する可能性がある。また Fig 6 のように再配置の無限ループが形成されてしまうことがある。カッコウハッシュ法では、負荷係数 \(a\) が一定のしきい値を超えた場合や、再配置の無限ループを検出した場合に、エントリサイズを拡張しハッシュ関数を変更するリハッシュを行う。

ハッシュテーブルの負荷係数が 0.5 以下の状況では、挿入操作の期待計算量は \(O(1)\) である。
検索: 要素 \(x\) の検索は、最大でも 2 つのエントリ \(T_1[h_1(x)]\), \(T_2[h_2(x)]\) を検査すれば良い。したがって検索の最悪計算量は \(O(1)\) である。
削除: 検索と同様に最大でも 2 つのエントリ \(T_1[h_1(x)]\), \(T_2[h_2(x)]\) を検査し、一致する要素のエントリを空にする。したがって削除の最悪計算量は \(O(1)\) である。

カッコウハッシュ法は離れた 2 つのメモリにアクセスする必要があることから多くの場合に 2 回のキャッシュミスが発生する。このため線形プローブ法と比較すると実際に 20%～30% の遅さが見られる [4]。ただし、計算量が定数時間 \(O(1)\) であることは分散システムのようなキャッシュの効果を期待しないシステム設計に適用するときに有利である。

Hopscotch ハッシュ法

Hopscotch ハッシュ法 (hopscotch hashing) [7] はオープンアドレス方式の一種で、線形プローブ法と似ているが、要素を正規スロットの近くに集めて配置する特徴がある。これにより要素の局所性が高まりキャッシュラインを効率的に機能させることができる。実際、Hopscotch ハッシュ実装は負荷係数が高い状況でも他のアルゴリズムと比べてスループットの低下が少ない。

Hopscotch ハッシュのエントリは 1 つの要素を格納するバケットの他に \(H\) ビットのホップ情報を持つ ([7] では \(H=32\) を適用している)。ホップ情報は「このエントリを正規スロットとする要素が、このエントリの後ろの何番目に格納されているか」をビットマップで表している。つまり衝突した要素はすべて正規スロット \(i\) から \(i+H-1\) の範囲に存在することを保証する。

挿入: 挿入する要素 \(x\) をハッシュ化してテーブルエントリのインデックス \(h(x)=i\) を取得する。エントリ \(i\) が空いていればそのエントリに要素を格納しホップ情報の最右ビットを 1 にする。エントリ \(i\) が空いていなければ、線形プローブ法と同様の方法で最も近い空きエントリを探索し、既存の要素を置き換えて空きエントリが \([i,i+H-1]\) の範囲になるように移動し、要素を格納する。

Fig 7 は \(H=4\) の設定で正規エントリに既に要素が格納されているケースでの例である。エントリ \(i\) には既に別の要素が格納されており、その後ろで最も近い空きエントリは \(i+7\) である。

Fig 7. 線形プローブ法と同様に \(i\) より後ろで最も近い空きエントリを探索する。

エントリ \(i+7\) は \([i,i+H-1]\) の範囲にないため、この空きをもっと近づける必要がある。エントリ \(i+7\) から \(H-1\) 個前のエントリ \(i+4\) のホップ情報を参照すると、\(i+5\) の要素を \(i+7\) に移動できることが分かる。このため \(x_4\) をエントリ \(i+7\) に移動して \(i+4\) のホップ情報を更新する。しかし新しく空きとなったエントリ \(i+5\) もまだ範囲内ではないため、\(i+2\) のホップ情報から移動可能なエントリを探して移動する。このような操作を繰り返して \([i,i+H-1]\) 範囲までエントリの空きを移動させる。

Fig 8. エントリの空きを \(i\) に近づくように移動させる。

空きエントリが \(i+3\) の位置まで来たため、挿入しようとしていた要素をエントリ \(i+3\) に格納し、\(i\) のホップ情報の 3 ホップ目のビットマップを 1 に設定する。

Fig 9. 移動したエントリの空きに要素を格納する。

Hopscotch ハッシュは空きが見つかるまで要素を追い出すカッコウハッシュ法とは逆に空きを移動させている。この空きエントリの移動が「けんけんぱ」に似ていることから Hopscotch と呼ばれている。
検索: 要素の正規スロットのホップ情報を参照すると、そのエントリからの相対位置で衝突している要素の格納されている位置が分かる。それらを逐次参照して検索対象の要素と比較する。
削除: 削除対象の要素が格納されているエントリを見つけ、正規スロットのホップ情報でそのエントリのビットを 0 に設定する。Hopscotch ハッシュ法は墓石を使用しないため削除が多くなったときの墓石汚染が発生しない。

エントリの空きを移動できなくなった場合、Hopscotch ハッシュテーブルのサイズを拡張してリハッシュする必要がある。

参考文献

Jeff Erickson. Algorithms, More Algorithms Lecture Notes, Lecture 5: Hash Tables [Sp’17]
Dzejla Medjedovic, Emin Tahirovic, Ines Dedovic. 大規模データセットのためのアルゴリズムとデータ構造. マイナビ出版 (2024)
PAGH, Rasmus; RODLER, Flemming Friche. Cuckoo hashing. Journal of Algorithms, 2004, 51.2: 122-144.
Anshumali Shrivastava. Probabilistic Algorithms and Data Structure. Lecture 4, Jan 17, 2018
Avrim Blum, Manuel Blum. Universal and Perfect Hashing, CMU 15-451 Algorithms Lecture 10, 2011 Fall.
Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming 並行プログラミングの原理から実践まで. アスキー・メディアワークス, 2009
HERLIHY, Maurice; SHAVIT, Nir; TZAFRIR, Moran. Hopscotch hashing. In: Distributed Computing: 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings 22. Springer Berlin Heidelberg, 2008. p. 350-364.