ここでちょっとした難問があります: CRC-64 のようなハッシュ アルゴリズムを使用する場合、適切なハッシュを計算するには、文字列内の何バイトを読み取る必要があるでしょうか? すべての文字列の長さが少なくとも 2 KB だとすると、文字列全体を使用してキャッシュを計算するのは無駄またはリソースのように見えますが、何文字あれば十分だと思いますか? 64ビットに等しいので、8つのASCII文字で十分でしょうか? ASCII 文字を 8 文字以上使用しても意味がありませんか? これについてあなたの考えを知りたいです。
更新: 「適切なハッシュ」とは、計算にさらに多くのバイトを使用してもハッシュ衝突の可能性が低くならないポイントを意味します。
8バイト以下でCRC-64を使用する場合、CRC-64を使用しても意味がありません。8バイトを「そのまま」使用するだけです。入力が意図した出力より長くない限り、CRCには付加価値がありません。
原則として、ハッシュ関数の出力がnビットの場合、約2 n / 2の文字列を蓄積すると、衝突が発生し始めます。つまり、64ビットを使用する場合、最初の20億の文字列で衝突が発生する可能性はほとんどありません。160ビット以上の出力を取得する場合、衝突は事実上実行不可能です（CPUが発火するなどのハードウェア障害よりもはるかに少ない衝突が発生します）。これは、ハッシュ関数が「完全」であることを前提としています。ハッシュ関数がいくつかのデータバイトを選択することから始まる場合、必然的に、あなたが選択しないバイトselectはハッシュ出力に影響を与えることができないため、「適切な」バイトを使用することをお勧めします。これは、ハッシュする文字列の種類に完全に依存します。ここには一般的な規則はありません。
私のアドバイスは、最初に文字列全体に対してジェネリックハッシュ関数を使用してみることです。私は通常MD4をお勧めします。MD4は暗号化ハッシュ関数であり、完全に壊れていますが、セキュリティが関係しない問題の場合でも、データ要素の混合に非常に優れています（暗号学的に言えば、CRCはMD4よりもはるかに壊れています）。一部のプラットフォームでは、MD4はCRC-32よりも実際に高速であると報告されているため、試してみることができます。基本的なPC（私の2.4 GHz Core2）では、MD4実装は約700 MBytes / sで動作するため、1秒あたり35000個のハッシュされた2kB文字列について話します。これは悪くありません。
2 つの異なる文字列の最初の 8 文字が同じである確率は? これらの文字列が何であるかによっては、非常に高くなる可能性があり、その場合、ハッシュの衝突が確実に発生します。
全体をハッシュします。数キロバイトは何でもありません。プログラムで実際にナノ秒を節約する必要がない限り、完全な文字列をハッシュしないことは時期尚早の最適化になります。