等しいかどうかを比較する必要がある非常に長い文字列があります。それらを文字ごとに比較するのは非常に時間がかかるため、文字列のハッシュを作成するのが好きです。
生成されたハッシュコードが一意であることが好きです（または、同じハッシュを持つ2つの文字列が生成される可能性が非常に小さい）。ハッシュとして文字列から int を作成することは、同じハッシュ コードを持つ 2 つの異なる文字列を排除するほど強力ではないと思うので、文字列ハッシュ コードを探しています。
上記の仮定は正しいですか？
明確にするために、たとえば 1K の長さの文字列があり、10 文字のハッシュ コードを作成すると仮定すると、比較ハッシュ コードは 100 倍高速になります。
私が持っている質問は、C++ でそのようなハッシュ コードを作成する方法ですか?
Visual Studio 2012 を使用して Windows で開発しています。
この場合に有用であるためには、ハッシュ コードは計算が迅速でなければなりません。ハードウェアでサポートされている最大のワード (通常は 64 ビット) よりも大きなものを使用すると、逆効果になる可能性があります。それでも、試してみることができます。以下がかなりうまく機能することがわかりました。
unsigned long long
hash( std::string const& s )
{
unsigned long long results = 12345; // anything but 0 is probably OK.
for ( auto current = s.begin(); current != s.end(); ++ current ) {
results = 127 * results + static_cast<unsigned char>( *current );
}
return results;
}
ただし、ほとんどの比較が等しくなく、長い共通の初期シーケンスを持つ文字列を使用しない限り、このようなハッシュを使用することはおそらく有利ではありません。ハッシュが等しい場合でも、文字列を比較する必要があり、その比較は等しくない最初の文字まで行う必要があることに注意してください。(実際、私が見た比較関数のほとんどは長さの比較から始まり、文字列の長さが等しい場合にのみ文字を比較します。)
さて、まずは弦の長さを比べてみます。それらが一致する場合は、ランダムな位置を使用して文字の同等性をテストするアルゴリズムを使用して比較を開始し、最初の違いで停止します。ランダムな位置は、0 から stringLength-1 の範囲のランダムな int で満たされた stringLength サイズのベクトルから取得されます。私はこの方法を測定していませんが、それは単なるアイデアです。ただし、これにより、比較時間を短縮しながら、ハッシュ衝突の懸念が解消されます。
それは本当にあなたの厳しい要件が何であるかに依存します. 「検索にそれほど時間がかからない」などの厳しい要件がある場合は、適用できるソリューションがない可能性があります。単純に多数の検索を高速化することが目的の場合は、単純で短いハッシュで十分です。
一般に、1000 文字の文字列を整数 (1 つの 32 ビットまたは 64 ビットの数値) にハッシュすると衝突が発生する可能性があり、最終的には衝突が発生することは事実ですが、これは心配する必要はありません。
10 文字のハッシュでも衝突が発生します。これは、1000 > 10 という事実の必然的な結果です。10 文字のハッシュごとに、100 個の 1000 文字の文字列1が存在します。
重要な問題は、実際に衝突が見られるかどうか、どのくらいの頻度で衝突が見られるか、そしてそれがまったく問題になるかどうかです。衝突が発生するかどうか (またはどの程度発生する可能性があるか)は、文字列の長さではなく、個別の文字列の数に依存します。
32 ビット ハッシュを使用して 77,100 個の文字列 (4 文字を超える) をハッシュすると、新しいハッシュごとに衝突が発生する可能性が 50% になります。25,000 文字列の場合、可能性はわずか 5 ～ 6% 程度です。1000 文字列では、可能性は約 0.1% です。
「77,100 弦で 50%」と言うとき、これはそうではないことに注意してください。実際に衝突に遭遇する可能性が非常に高いことを意味します。これは、同じハッシュ値を持つ 2 つの文字列が存在する可能性にすぎません。それが大部分の弦に当てはまらない限り、実際に弦を弾く可能性はさらに低くなります。
これは、ほとんどの使用例と同様に、それ以上でもそれ以下でもなく、単に問題ではないことを意味します。数十万の文字列をハッシュしたくない場合は、心配するのをやめて 32 ビット ハッシュを使用してください。
それ以外の場合は、何十億もの文字列をハッシュしたくない場合は、ここで心配するのをやめて 64 ビット ハッシュを使用してください。
つまり、2 つの文字列がある限り、衝突の可能性が完全にゼロになることはないため、どのような場合でも衝突を処理する準備をしておく必要があります。2 つまたは 3 つの 1000 文字の文字列を 500 バイトのハッシュにハッシュするだけでも、原則として衝突が発生する可能性があります (可能性は非常に低いですが可能性はあります)。
つまり、ハッシュの長さ (またはどれだけ良いか悪いか) に関係なく、ハッシュがどちらの場合にも一致する場合は、文字列比較を行う必要があります。
衝突が毎回発生しない場合、それらはまったく無関係です。テーブルに多くの衝突があり、たとえば 10,000 回の検索に 1 回 (これはかなりの割合です!) 衝突が発生したとしても、実際には何の影響もありません。はい、10,000 回のルックアップに 1 回は無駄な文字列比較を行う必要がありますが、残りの 9,999 回は単一の整数のみを比較することで機能します。厳しいリアルタイム要件がない限り、測定可能な影響はまったくゼロです。
5回の検索ごとに完全に失敗して衝突に遭遇したとしても（かなり悲惨なケースです。これは、約8億の文字列ペアが衝突することを意味します。これは、少なくとも16億の文字列でのみ可能です）、これはまだ5 回の検索のうち 4 回は競合にヒットしないため、比較を行わずに不一致の 80% を破棄します。
一方で、10 文字のハッシュを生成するのは面倒で時間がかかり、すぐに存在する 32 ビットまたは 64 ビットのハッシュよりも (設計が悪いため) 衝突が多いハッシュ関数を作成する可能性があります。
暗号ハッシュ関数は確かに優れていますが、非暗号ハッシュ関数よりも実行速度が遅く、16 バイトまたは 32 バイトのハッシュ値を格納するために必要なストレージもはるかに大きくなります (ほとんどの人にとって、事実上何のメリットもありません)。これは空間と時間のトレードオフです。
個人的には、3 行の C コードで実装でき、うまく機能し、非常に高速に動作する djb2 のようなものを使用します。もちろん、使用できるハッシュ関数は他にもたくさんありますが、私はその単純さから djb2 が好きです。
おかしなことに、James Kanze の回答を読んだ後、投稿されたコードは djb2 のバリエーションのように見えますが、シードと乗数が異なるだけです (それぞれ 5381 と 33)。
同じ回答で、文字列の長さを最初に比較することについての発言も良いヒントです。文字列の長さも「ハッシュ関数」の形式と見なすことができることは注目に値します (かなり弱いものですが、「無料で」提供されることがよくあります)。