algorithm - パーフェクトハッシュビルディング

Question

ハッシュにSHA-1、md5Sum、その他の標準的な暗号化ハッシュを使用してみませんか。それらは衝突を回避するのに十分賢く、また元に戻すことはできません。したがって、衝突が発生する可能性のある新しいハッシュ関数のセットを考え出すのではなく、それらを使用してみませんか。私が考えることができる唯一の理由は、32ビットなどの大きなキーが必要なことですが、それでも衝突を回避するため、ルックアップは間違いなくO（1）になります。

Answer 1

1. それらは非常に遅いため、2つの理由があります。
   1. それらは、一般的に衝突耐性があるだけでなく、暗号的に安全であることを目指しています
   2. それらは、ハッシュテーブルで実際に必要なものよりもはるかに大きなハッシュ値を生成します
2. 非構造化データ（オクテット/バイトストリーム）を処理しますが、ハッシュする必要のあるオブジェクトは構造化されていることが多く、最初に線形化が必要になるためです。

Answer 2

SHA-1、md5Sum、およびその他の標準的な暗号化ハッシュをハッシュに使用しないのはなぜですか。彼らは衝突を避けるのに十分賢いです...

間違っている理由:

• 2 つの入力は、たまたま同じハッシュ値を持つことがあります。ハッシュ値が 32 ビットだとすると、優れた汎用ハッシュ ルーチン (つまり、実際のキーのセットへの洞察を利用しないもの) は、任意の 2 に対して同じハッシュ値を返す可能性が少なくとも 1/2^32 あります。キーの場合、3 番目のキーがハッシュされると 2/2^32 の確率でそれらのいずれかと衝突し、4 番目のキーは 3/2^32 になります。
• 個別のハッシュ値を持つことは、ハッシュ値がハッシュ テーブル内の個別のハッシュ バケットにマップされることとはまったく異なります。ハッシュ値は通常、バケットを選択するためにテーブル サイズに変更されます。そのため、ハッシュ テーブルに要素を追加するときに競合が発生する可能性は、せいぜい (これも汎用ハッシュの場合) #preexisting-elements / table-size です。

したがって、衝突が発生する可能性のある一連の新しいハッシュ関数を考え出すのではなく、それらを使用しないでください。

バイナリ ツリーではなくハッシュ テーブルを使用することを選択する場合、多くの場合、速度がプログラマの目標となるためです。ハッシュ値の計算が数学的に複雑な場合は、競合が発生しやすいが計算が高速なハッシュ関数を使用するよりも、はるかに長い時間がかかる場合があります。とは言うものの、ハッシュ処理の労力を増やせば報われる場合もあります。たとえば、ハッシュ テーブルが磁気ディスク上に存在し、レコードのシークと読み取りの I/O コストがハッシュ計算の労力を圧倒する場合などです。

antti はデータについても興味深い指摘をしています...汎用ハッシュルーチンは、特定の開始アドレスとバイト数を持つバイナリデータのブロックで動作することがよくあります (バイト数が 2 または 4 の倍数である必要がある場合もあります)。 . 多くのアプリケーションでは、ハッシュする必要があるデータは、ハッシュに含めてはならないデータ (キャッシュされた値、ファイル ハンドル、他のデータへのポインター/参照、仮想ディスパッチ テーブルなど) と混在します。一般的な解決策は次のとおりです。必要なフィールドを個別にハッシュし、ハッシュ キーを結合します (おそらく排他的論理和を使用します)。ハッシュされるべきではない他のデータと同じメモリ バイトでハッシュされるべきビット フィールドが存在する可能性があるため、それらの値を抽出するカスタム コードが必要になる場合があります。それでも、事前にコピーとパディングが必要だったとしても、

私が考えることができる唯一の理由は、32ビットと言う大きなキーが必要だということです。

他のすべての条件が同じであれば、キーが大きいほど優れていますが、ハッシュ関数が数学的に理想的である場合、そのビットの任意の N (2^N >= # ハッシュ バケット) で衝突が最小限に抑えられます。

ただし、衝突を回避しているため、ルックアップは間違いなく O(1) になります。

繰り返しますが、上記のように間違っています。

（ところで...上記のいくつかの場所で汎用性を強調しています。これは、ハッシュする必要があるキーについて洞察を得ることができる些細なケースがあり、利用可能なハッシュバケット内にそれらを完全に配置できるからです。たとえば、キーが 1000、2000、3000 などの 100000 までの数字であり、少なくとも 100 個のハッシュ バケットがあることがわかっている場合、ハッシュ関数を x/1000 として自明に定義でき、完全なハッシュ sans 衝突.すべてのキーが個別のハッシュ テーブル バケットにマップされていることを知っているこの状況は、「完全なハッシュ」と呼ばれます-質問のタイトルによると-md5 のような優れた汎用ハッシュは完全なハッシュではなく、実際にそれは可能なキーの完全なセットを知らずに完全ハッシュについて話す意味はありません)。