string - ハッシュによる長い文字列の比較

Question

文字列を比較する関数のパフォーマンスを改善しようとして、ハッシュを比較して比較することにしました。2つの非常に長い文字列のハッシュが互いに等しい場合、文字列も互いに等しいという保証はありますか?

Answer 1

2 つの同一の文字列が等しいハッシュを与えることが保証されていますが、その逆は当てはまりません: 特定のハッシュに対して、同じハッシュを生成する可能性のある文字列が常に複数存在します。これは、PigeonHole の原理によるものです。

そうは言っても、2 つの異なる文字列が同じハッシュを生成する可能性は、null と同等と見なされるまで、ごくわずかにすることができます。

このようなハッシュのかなり古典的な例はMD5で、これはほぼ完全な 128 ビットの分布を持っています。つまり、2^128 で 2 つの異なる文字列が同じハッシュを生成する可能性が 1 つあります。まあ、基本的にはほぼ不可能と同じです。

Answer 2

2 つの長い文字列が同一かどうかを判断するために比較される単純な一般的なケースでは、2 つの理由から、単純な比較がハッシュよりもはるかに優先されます。まず、@wildplasser が指摘したように、ハッシュでは、2 つのハッシュ値を計算するために両方の文字列のすべてのバイトをトラバースする必要がありますが、単純な比較は高速であり、最初の違いが見つかるまでバイトをトラバースするだけで済みます。これは、文字列全体の長さよりもはるかに短い場合があります。次に、@AdamLiss と @Cyan で指摘されているように、単純な比較では違いを検出することが保証されていますが、ハッシュはそれらが同一である可能性が高いだけです。

ただし、ハッシュ比較を使用して大きな利点を得ることができる興味深いケースがいくつかあります。@Cyan が述べたように、比較を複数回行う場合、または後で使用するために保存する必要がある場合は、ハッシュの方が高速になる可能性があります。他の人が言及していないケースは、文字列がローカルネットワークまたはインターネット経由で接続された異なるマシン上にある場合です。2 台のマシン間で少量のデータを渡すと、通常ははるかに高速になります。最も簡単な最初のチェックは、2 つのサイズを比較することです。異なる場合は完了です。それ以外の場合は、それぞれ独自のマシンでハッシュを計算し (リモート マシンでプロセスを作成できると仮定します)、異なる場合は再度計算します。ハッシュ値が同じで、絶対的な確実性が必要な場合、その確実性への近道はありません。両端で可逆圧縮を使用すると、比較のために転送されるデータが少なくなります。そして最後に、@Cyan でほのめかされているように、2 つの文字列が時間で区切られている場合、ファイルが昨日から変更されたかどうかを知りたい場合、および昨日のバージョンのハッシュを保存した場合は、今日のハッシュとそれを比較できます。 .

これが誰かの「箱から出してすぐに使える」アイデアを刺激するのに役立つことを願っています.

Answer 3

パフォーマンスが向上するかどうかはわかりません。両方: ハッシュの構築 + 整数の比較と等号を使用した単純な文字列の比較は同じ複雑さを持ち、O(n) になります。ここで、n は文字数です。