SSE 4.2（Intel Core i7およびi5パーツ）にCRC32命令が含まれていることを考えると、より高速な汎用ハッシュ関数を構築できるかどうかを調査することは合理的と思われます。これによると、CRC32の16ビットのみが均等に分散されます。では、それを克服するために他にどのような変革を適用するでしょうか？
更新 これはどうですか？ハッシュ値には16ビットのみが適しています。罰金。テーブルが65535以下の場合は、すばらしいです。そうでない場合は、Nehalem POPCNT（ポピュレーションカウント）命令を介してCRC値を実行し、設定されているビット数を取得します。次に、それをテーブルの配列へのインデックスとして使用します。これは、テーブルが1mmエントリの南にある場合に機能します。最高のパフォーマンスのハッシュ関数よりも安くて速いと思います。GCC 4.5にはCRC32が組み込まれているので、テストは簡単です...私がそれに取り組むための十分な時間がある場合に限ります。
デビッド
再訪、2014 年 8 月最近のコメントでArnaud Bouchez
によって促され、他の回答やコメントを考慮して、元の回答を変更する必要があること、または最も限定的なものであることを認めます。参考までに原文を最後にそのまま残しておきます。
まず、おそらく最も重要なことですが、質問に対する公正な答えは、ハッシュ コードの使用目的によって異なります。「良い」[ハッシュ関数...] とはどういう意味ですか? ハッシュはどこで/どのように使用されますか? (例えば、比較的短い入力キーをハッシュするためですか? インデックス作成/検索目的、メッセージ ダイジェストを生成するため、またはその他の用途のためですか? 目的のハッシュ コード自体、[CRC32 またはその派生物の] すべての 32 ビットの長さ、詳細ビット、より少ない...など?
OPの質問は、「より高速 な汎用ハッシュ関数"、したがって、焦点は SPEED (CPU の負荷が少ないもの、および/またはさまざまな性質の並列処理を利用できるもの) です。ここで、ハッシュ コード自体の計算時間は、多くの場合、問題の一部にすぎないことに注意してください。ハッシュの適用 (たとえば、ハッシュ コードのサイズまたはその固有の特性により、余分なサイクルを処理する必要がある多くの衝突が発生する場合) また、「汎用」の要件により、可能な用途について多くの疑問が残ります。
これを念頭に置いて、短くてより良い答えはおそらく次のとおりです。
はい、新しい Intel プロセッサでの CRC32C のハードウェア実装を使用して、より高速なハッシュ コードを構築できます。ただし、ハッシュの特定の実装とそのアプリケーションによっては、衝突の頻度やより長いコードを使用する必要があるため、全体的な結果が最適ではない可能性があることに注意してください。また、CRC32 アルゴリズム自体はこの点で非常に弱いため、ハッシュの暗号化の使用は慎重に検討する必要があります。
元の回答は、Bret Mulvey による Evaluating Hash functions に関する記事を引用しており、Mdlg の回答で指摘されているように、この記事の結論は、CRC32の実装にバグがあり/欠陥があったため、CRC32 に関して誤りです。CRC32 に関するこの重大なエラーにもかかわらず、この記事は一般的なハッシュ アルゴリズムのプロパティに関する有用なガイダンスを提供します。この記事への URL は現在無効になっています。archive.todayで見つけましたが、作者が別の場所に持っているかどうか、また更新したかどうかはわかりません。
ここでの他の回答は、CRC32Cを使用するハッシュライブラリの例としてCityHash 1.0を引用しています。明らかに、これはいくつかの長い (32 ビットよりも長い) ハッシュ コードのコンテキストで使用されますが、CityHash32() 関数自体には使用されません。また、シティ ハッシュ関数による CRC32 の使用は、ハッシュ コードを生成するために実行されるすべてのシフト、シャッフル、およびその他の操作と比較して、比較的少ないものです。(これは私が実地経験のない CityHash に対する批判ではありません。CityHash 関数が生成するソース コードのざっとしたレビューから、CityHash 関数は適切な分散コードなどを生成しますが、それほど高速ではありません。他のさまざまなハッシュ関数よりも。)
最後に、 SO の疑似重複質問でこの問題に関する洞察を見つけることもできます。
元の回答と編集 (2010 年 4 月)
アプリオリに、これは悪い考えのように聞こえます! .
CRC32 はハッシュ目的で設計されておらず、その分布は均一ではない可能性が高いため、比較的貧弱なハッシュ コードになっています。さらに、その「スクランブリング」能力は比較的弱く、暗号化アプリケーションで使用されるような非常に貧弱な一方向ハッシュになります。
[BRB: その効果に関するオンライン リファレンスを探しています...]
Google の最初の [キーワード = CRC32 分布] ヒットは、これを確認しているようです:
Evaluating CRC32 for hash tables
編集：上記のページ、および実際には完全な記事は、ハッシュ関数で何を探すべきかの良い基礎を提供します。この記事を[すばやく]読んで、一般的にCRC32をハッシュとして使用すべきではない
という包括的な声明を確認しましたが、ハッシュの特定の目的によっては、少なくとも部分的にCRC32をハッシュコード。
たとえば、CRC32 コードの下位 (または実装によっては上位) の 16 ビットは、比較的均等に分布しており、ハッシュ コードの暗号化特性 (つまり、類似のキーが非常によく似たコードを生成する)、たとえば、元のキーの 2 つの半分 (または任意の分割) で生成された 2 つの CRC32 コードの下位 [または上位] 16 ビットの連結を使用するハッシュ コードを構築できる場合があります。
組み込みの CRC32 命令の効率が、代替ハッシュ関数と比較して、命令を 2 回呼び出してコードをつなぎ合わせるなどのオーバーヘッドが発生しないようなものであるかどうかを確認するために、テストを実行する必要があります。全体的に遅い機能。
他の回答で参照されている記事は、バグのあるcrc32コードに基づいて誤った結論を導き出しています。Google のランキング アルゴリズムは、まだ科学的精度に基づいてランク付けを行っていません。
参照された記事「ハッシュ テーブルの CRC32 の評価」の結論に反して、CRC32 と CRC32C はハッシュ テーブルの使用に受け入れられます。著者のサンプルコードには、crc32 テーブルの生成にバグがあります。crc32 テーブルを修正すると、同じ方法で満足のいく結果が得られます。また、CRC32 命令の速度は、多くの状況で最良の選択となります。CRC32 命令を使用するコードは、最適なソフトウェア実装よりもピーク時に 16 倍高速です。(CRC32 は intel 命令が実装する CRC32C とまったく同じではないことに注意してください。)
CRC32 は明らかに暗号化の使用には適していません。(32 ビットは力ずくのジョークです)。
はい。 CityHash 1.0.1には、CRC32 命令を使用するいくつかの新しい「優れたハッシュ関数」が含まれています。
For cryptographic purposes, CRC32 is a bad fundation because it is linear (over the vector space GF(2)^32) and that is hard to correct. It may work for non-cryptographic purposes.
However, recent Intel cores have the AES-NI instructions, which basically perform 1/10th of an AES block encryption in two clock cycles. They are available on the most recent i5 and i7 processors (see the Wikipedia page for some details). This looks like a good start for building a cryptographic hash function (and a hash function which is good for cryptography will also be good for about anything else).
Indeed, at least one of the SHA-3 "round 2" candidates (the ECHO hash function) is built around the AES elements so that the AES-NI opcodes provide a very substantial performance boost. (Unfortunately, in the absence of AES-NI instruction, ECHO performance somewhat sucks.)
暗号ハッシュを使用していない限り、機能する可能性があります。