4

SHA256 よりも速い可能性のあるものを見つけようとしています。ハッシュして一意かどうかを検証する必要がある 10 億を超えるレコードがあります。私は現在、衝突を避けるためにsha256を介してかなり高速に見えるMD5を介して実行しています。それらをこの順序で実行すると、パフォーマンスが少し向上するようですが、それでももっと速くする必要があります。C# で作成したハッシュの名前や例、または C# で再作成できる疑似コードを探しています。

4

6 に答える 6

5

ここでの回答には、疑わしい情報がたくさんあります。質問にタグを付け、cryptography暗号化ハッシュ関数についてのみ言及しましたが、特に次のように言うため、暗号化セキュリティは本当に必要ないように思えます:

ハッシュして一意かどうかを検証する必要がある 10 億を超えるレコードがあります。

暗号化ハッシュ関数には 4 つのプロパティがあります。

  • 任意のメッセージのハッシュ値を簡単に計算できます
  • 指定されたハッシュを持つメッセージを生成することは実行不可能です
  • ハッシュを変更せずにメッセージを変更することは不可能です
  • 同じハッシュを持つ 2 つの異なるメッセージを見つけることは不可能です。

実際には最初の品質のみに関心があり、一意性は、暗号化セキュリティの他の 3 つのプロパティに部分的にのみ関連する小規模な要件です。

なんで気にするの？

暗号化セキュリティにはオーバーヘッドがあります。あなたはそれを必要とせず、速度に興味があるので、スキップしてみませんか? MD5 と SHA ファミリのハッシュ幅は、明らかに目的に十分な大きさです。

ウィキペディアのハッシュ関数のリストを確認するか、通常のハッシュ関数に関する記事を確認してください。さらに言えば、組み込みの .NET ハッシュ関数の何が問題なのですか? メソッドを延期しようとしましたObject.GetHashCode()か？その MSDN リファレンスには、ハッシュ関数の使用について多くのことが書かれています。ハッシュしているデータについてはあまり語らないため、出力がオブジェクト間で一意になるかどうかを判断するのは困難です。オブジェクトを MD5 ハッシャーにどのようにフィードしていますか? あなたはそれのバイナリ表現を取っていると思います。同様のアプローチを使用して、組み込みの非暗号化ハッシュ関数を使用できます。

組み込みのハッシュ関数の一意性が気になるかもしれません。通常の int のみを返します。これは 2^32 であり、使用しているデータ セットの約 4 倍しかありません。ただし、ハッシュ関数のバックアップ計画は常に必要です。衝突は不可能ではありません。標準的なフォールバックは、よりコストのかかる比較を実行することです。通常は、参照比較とフィールド単位の値比較です。

ハッシュ出力を正確に比較する準備ができていない場合は、基本的に、誤検知が発生するまでカウントダウンを行っていることになります。それはあなたにとって大したことではないかもしれません.何がマイナス面であるかを判断できるのはあなただけです.

さらに、別のハッシュ関数計算を実行しても、おそらく直接比較よりもはるかに高速ではありません。すべての点で、確実なことを行って、長い直接比較を実行する方が良いでしょう.

もう 1 つの一般的な衝突防止手法は、複数のキーを使用することです。したがって、データ ポイントに複数の大きなサブコンポーネントがある場合は、個別にハッシュして比較します。大きなコンポーネントと小さなコンポーネント (いくつかの単純な数値型など) がある場合、大きなコンポーネントをハッシュし、小さなコンポーネントを直接比較します。序数を簡単に取得できるデータ (文字列の長さや一部のコンテナーのサイズなど) がある場合は、それらのビットを直接比較できます。

それがうまくいかない場合は、ウィキにリストされている他のハッシュ関数の実装を見てください。これは、32 ビットまたは 128 ビットのハッシュ値を計算できるMurmerHash3のかなり良いリファレンスです。リストには、ハッシュ幅が長く、C# ライブラリが利用可能な他のハッシュ関数もあります。しかし、その参照が指摘しているように、Murmurhash は MD5 および SHA 関数よりもはるかに高速ですが、上記の Object.GetHashCode メソッドと直接比較することはできません。

于 2013-07-31T07:10:45.300 に答える
3

何か違うことをしてみませんか？

レコードをハッシュ テーブルに挿入するときに使用するような単純なハッシュ関数を各レコードで使用し、おそらく各レコードを 32 ビット INT にマッピングします。次に、ハッシュの衝突があった場合は、衝突したレコードの一意性を比較します。

于 2013-06-28T12:34:15.940 に答える
1

MD5 を使用すると、競合するレコードに遭遇した場合に、SHA256 または SHA128 でそれらをチェックできます。

于 2013-06-28T12:39:41.960 に答える