問題タブ [hash-collision]

私は、システムから外部システムにデータを同期する必要があるプロジェクトに取り組んでいます。私が達成したいのは、カスタムクエリから変更されたアイテム (行) のみを定期的に送信することです。このクエリは次のようになります (ただし、さらに多くの列があります)。

同期間ですべてのフィールドを 1 対 1 で比較する必要はありません。クエリからすべての行のハッシュを生成し、これを以前の同期からのハッシュと比較すると、変更された行のみが返されるという考えに至りました。私はCHECKSUM関数を認識していますが、衝突が非常に発生しやすく、時々変更を見逃す可能性があります。ただし、一時テーブルを作成して使用できる方法が気に入っていますCHECKSUM(*)。これにより、メンテナンスが簡単になります（クエリとチェックサムにフィールドを追加する必要はありません）。

HASHBYTES関数 (衝突しにくい sha1、md5 をサポート) は知っていますが、列のリストや CHECKSUM のように * ではなく、varchar または varbinary のみを受け入れます。クエリからすべての列をキャスト/変換する必要があるのは面倒です...そしてエラーへの扉を開きます（たとえば、新しいフィールドを含めるのを忘れます）

また、SQL Server の変更データ キャプチャ機能と変更追跡機能にも気付きましたが、それらはすべて複雑で、私がやっていることにはやり過ぎのように思えます。

だから私の質問:私の基準を満たすクエリまたは一時テーブルからハッシュを生成する他の方法はありますか?

そうでない場合、この種の作業を達成する別の方法はありますか (クエリとの違いを同期するため)

多数のオブジェクト (オブジェクトのバイト配列に格納された値の一意の組み合わせ) をハッシュマップ (約 280 万オブジェクト) に格納しています。また、ハッシュ コード (32 ビット ハッシュ)、統計的には、少なくとも 1 つの衝突が発生する可能性がほぼ 100% あるのに、まったくないことに非常に驚いています ( http://preshing.com/20110504/hash-collision-probabilities/を参照)。

したがって、衝突を検出するための私のアプローチにバグがあるのか​​ 、それとも非常に幸運なのか疑問に思っています...

マップに格納されている 280 万の値から衝突を検出する方法を次に示します。

そして、ハッシュ値を作成するためのオブジェクトのアプローチは次のとおりです。

私が間違っていることについてのアイデア/ヒントは大歓迎です!

ありがとう、トーマス

これが重複した質問である場合はお詫びします。私が見つけたもののほとんどは私の頭の中にあるので、答えを見落としている可能性があります。

特定のハッシュ、例えば MD5 (128 ビット) の場合、10^12 個のハッシュが衝突する可能性はどれくらいですか?

私の数学は得意ではありません。この方程式を思いつきました (正しいと思います) が、それを解く方法がわかりません:

衝突確率 = 1 - (1 - (1 / 2^128) ) ^ (10^12)

10^-26くらいだと思いますが、これでいいでしょうか？

ありがとう

編集：私の見積もりは非常に間違っていると思います。誕生日のパラドックスを見る

マルチレベルのデータ整合性チェックと修正に興味があります。複数のエラー訂正コードが使用されている場合 (同じタイプのコードが 2 つある場合もあります)。使用されている2つのハッシュコードが互いに直交している場合、2つのコードを使用するシステムが最大の効果を発揮するという印象を受けています。

どのコードが何と直交しているかのリストはありますか? または、同じハッシュ関数を使用する必要がありますが、パラメーターまたは使用方法が異なりますか?

最初のレベルの ecc はリード ソロモン コードになると思いますが、実際にはこの最初の関数を制御することはできません。そのため、機能が向上した単一のコードを使用することはできません。

暗号化のセキュリティには関心がないことに注意してください。

編集：これはの複製ではありません

• ハッシュ関数が互いに直交するのはいつですか? 本質的に、直交ハッシュ関数の定義が何であるかを尋ねるためです。直交するハッシュ関数の例が必要です。

文字列を double に変換する単純なハッシュ関数 (と呼べる場合) を作成しました。

最初の文字の値を取得して double にキャストし、次の文字のコサインを掛けてから、次の文字のコサインを掛けて...というように機能します。

これは機能です：

では、この関数で衝突の確率を計算するにはどうすればよいでしょうか?

1 - e^(k(k-1)/(2k)) になる式を 1 つ見つけましたが、私が読んだところによると、ハッシュ関数が適切な関数である場合にのみ機能します (適切な RNG のように、ハッシュ値を均等に分散します)。 、またはそのようなもの）。