6.4 まとめ¶
1. 重要ポイントの振り返り¶
keyを入力すると、ハッシュテーブルは \(O(1)\) 時間でvalueを検索でき、非常に高効率である。- 一般的なハッシュテーブルの操作には、検索、キーと値のペアの追加、キーと値のペアの削除、ハッシュテーブルの走査などがある。
- ハッシュ関数は
keyを配列インデックスに写像し、それによって対応するバケットにアクセスしてvalueを取得する。 - 異なる 2 つの
keyが、ハッシュ関数を通した後に同じ配列インデックスになることがあり、検索結果の誤りを引き起こす。この現象をハッシュ衝突と呼ぶ。 - ハッシュテーブルの容量が大きいほど、ハッシュ衝突の確率は低くなる。そのため、ハッシュテーブルを拡張することでハッシュ衝突を緩和できる。配列の拡張と同様に、ハッシュテーブルの拡張操作のコストは大きい。
- 負荷率は、ハッシュテーブル内の要素数をバケット数で割ったものと定義され、ハッシュ衝突の深刻さを反映する。ハッシュテーブル拡張を発動する条件としてよく用いられる。
- 連鎖方式では、単一要素を連結リストに変換し、衝突したすべての要素を同じ連結リストに格納する。しかし、連結リストが長すぎると検索効率が低下するため、さらに連結リストを赤黒木に変換して効率を高めることができる。
- オープンアドレス法は複数回の探索によってハッシュ衝突を処理する。線形探索は固定のステップ幅を用いるが、要素を削除できず、クラスタリングが発生しやすいという欠点がある。二重ハッシュは複数のハッシュ関数を用いて探索するため、線形探索に比べてクラスタリングが起きにくいが、複数のハッシュ関数によって計算量が増える。
- プログラミング言語ごとに、異なるハッシュテーブル実装が採用されている。たとえば、Java の
HashMapは連鎖方式を使用し、Python のDictはオープンアドレス法を採用している。 - ハッシュテーブルでは、ハッシュアルゴリズムに決定性、高効率、均一分布という特徴が求められる。暗号学では、ハッシュアルゴリズムはさらに耐衝突性とアバランシェ効果も備えるべきである。
- ハッシュアルゴリズムは通常、大きな素数を法として用い、ハッシュ値の均一分布を最大限に保証してハッシュ衝突を減らす。
- 一般的なハッシュアルゴリズムには MD5、SHA-1、SHA-2、SHA-3 などがある。MD5 はファイル完全性の検証によく用いられ、SHA-2 はセキュリティ用途やプロトコルでよく用いられる。
- プログラミング言語は通常、データ型に対して組み込みのハッシュアルゴリズムを提供し、ハッシュテーブル内のバケットインデックスの計算に用いる。通常、ハッシュ可能なのは不変オブジェクトだけである。
2. Q & A¶
Q：ハッシュテーブルの時間計算量が \(O(n)\) になるのはどのような場合ですか？
ハッシュ衝突が深刻な場合、ハッシュテーブルの時間計算量は \(O(n)\) に劣化する。ハッシュ関数の設計が適切で、容量設定が合理的で、衝突が比較的均等な場合、時間計算量は \(O(1)\) である。プログラミング言語組み込みのハッシュテーブルを使うとき、通常は時間計算量を \(O(1)\) とみなす。
Q：なぜハッシュ関数 \(f(x) = x\) を使わないのですか？ そうすれば衝突は起きません。
\(f(x) = x\) というハッシュ関数では、各要素は一意のバケットインデックスに対応し、これは配列と等価である。しかし、入力空間は通常、出力空間（配列長）よりはるかに大きいため、ハッシュ関数の最後のステップはたいてい配列長での剰余になる。言い換えると、ハッシュテーブルの目的は、大きな状態空間をより小さな空間に写像し、\(O(1)\) の検索効率を提供することである。
Q：ハッシュテーブルの基礎実装は配列、連結リスト、二分木なのに、なぜそれらより高効率になり得るのですか？
まず、ハッシュテーブルは時間効率が高くなる一方で、空間効率は低くなる。ハッシュテーブルには、かなりの部分で未使用のメモリが存在する。
次に、時間効率が高くなるのは特定の利用場面に限られる。ある機能が同じ時間計算量で配列や連結リストによって実装できるなら、通常はハッシュテーブルより速い。これは、ハッシュ関数の計算にコストがかかり、時間計算量の定数項がより大きいからである。
最後に、ハッシュテーブルの時間計算量は劣化する可能性がある。たとえば連鎖方式では、連結リストや赤黒木で検索操作を行うため、なお \(O(n)\) 時間に劣化するリスクがある。
Q：二重ハッシュにも要素を直接削除できない欠点がありますか？ 削除済みとマークした領域は再利用できますか？
二重ハッシュはオープンアドレス法の一種であり、オープンアドレス法はいずれも要素を直接削除できないという欠点があるため、削除のマーク付けが必要になる。削除済みとマークされた領域は再利用できる。新しい要素をハッシュテーブルに挿入し、ハッシュ関数によって削除済みとマークされた位置を見つけた場合、その位置は新しい要素に使用できる。こうすることで、ハッシュテーブルの探索系列を変えずに保ちつつ、空間利用率も確保できる。
Q：なぜ線形探索では、要素を探すときにハッシュ衝突が発生するのですか？
探索時には、ハッシュ関数で対応するバケットとキーと値のペアを見つけ、key が一致しないことが分かると、それはハッシュ衝突を意味する。そのため、線形探索法では事前に設定したステップ幅に従って順に探索し、正しいキーと値のペアを見つけるか、見つからずに終了するまで続ける。
Q：なぜハッシュテーブルの拡張でハッシュ衝突を緩和できるのですか？
ハッシュ関数の最後のステップは、たいてい配列長 \(n\) での剰余を取り、出力値を配列インデックスの範囲内に収めることである。拡張後は配列長 \(n\) が変化し、key に対応するインデックスも変化する可能性がある。もともと同じバケットに入っていた複数の key は、拡張後には複数のバケットに割り当てられる可能性があり、それによってハッシュ衝突が緩和される。
Q：高効率な読み書きのためなら、配列を直接使えばよいのではないですか？
データの key が連続した小範囲の整数であれば、配列を直接使えばよく、単純で高効率である。しかし key が別の型（たとえば文字列）の場合は、ハッシュ関数を用いて key を配列インデックスに写像し、さらにバケット配列を通じて要素を格納する必要がある。このような構造がハッシュテーブルである。