6.4   まとめ

1.   重要なポイント

• 入力keyが与えられると、ハッシュ表は\(O(1)\)の時間で対応するvalueを取得でき、非常に効率的です。
• 一般的なハッシュ表の操作には、クエリ、キー値ペアの追加、キー値ペアの削除、ハッシュ表の走査があります。
• ハッシュ関数はkeyを配列インデックスにマッピングし、対応するバケットにアクセスしてvalueを取得できるようにします。
• 2つの異なるキーがハッシュ化後に同じ配列インデックスになる場合があり、誤ったクエリ結果につながります。この現象はハッシュ衝突として知られています。
• ハッシュ表の容量が大きいほど、ハッシュ衝突の確率は低くなります。したがって、ハッシュ表のリサイズはハッシュ衝突を緩和できます。配列のリサイズと同様に、ハッシュ表のリサイズはコストが高いです。
• 要素数をバケット数で割った負荷率は、ハッシュ衝突の深刻度を反映し、しばしばハッシュ表リサイズのトリガー条件として使用されます。
• 連鎖法は各要素を連結リストに変換し、衝突するすべての要素を同じリストに格納することでハッシュ衝突に対処します。ただし、過度に長いリストはクエリ効率を低下させる可能性があり、リストを赤黒木に変換することで改善できます。
• オープンアドレス法は複数回のプローブを通してハッシュ衝突を処理します。線形プローブは固定ステップサイズを使用しますが、要素を削除できず、クラスタリングを起こしやすい傾向があります。多重ハッシュはプローブに複数のハッシュ関数を使用し、線形プローブと比較してクラスタリングを減らしますが、計算オーバーヘッドが増加します。
• 異なるプログラミング言語はさまざまなハッシュ表実装を採用しています。例えば、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\)が変化し、キーに対応するインデックスも変化する可能性があります。以前に同じバケットにマッピングされていたキーが、リサイズ後に複数のバケットに分散される可能性があり、それによってハッシュ衝突が緩和されます。