問題タブ [hash-collision]

サードパーティ（「クローズドソース」を含む）ツール（同期、重複排除など）が、同じサイズのファイルとダイジェストチェックサム（人気のあるファイルCRC32、MD5、SHA-1）の存在下で動作することをテストしたいと思います。など）。これらのハッシュメソッドのいくつかには既知の脆弱性があるため、衝突を生成する方法があります。

そのようなデータセットのソース（ブルートフォースがいくつかを作成しようとする以外の:)）またはそのようなデータセットを作成するためのジェネレーターについて知っていますか？

これを明確にするために：チェックサムが同じで、ファイルサイズが異なるが内容が異なるファイルのセットに興味があります。

コード：

さて、私の理解では、両方のputケースのキー値が同じであるため、つまりa、衝突が発生するため、連鎖が発生します。[間違っていたら訂正してください]。

key value にマップされたすべての値のリストを取得したい場合a、どうすれば取得できますか?

今は私のprintlnプリントvのみです。

C++でHashtableクラスを実装しています。私が使用している衝突解決方法は、レイジー削除を使用した線形プロービングです。私はこれの実装を見てきましたが、insertメソッドに関して質問がありました。ハッシュテーブルの各セルには、状態（アクティブ、削除済み、空）があります。何らかの理由で、新しい要素を挿入するときに見た実装では、キーをハッシュしてから、EMPTYセルが見つかるまで（または同じキーが既に含まれているセルが見つかるまで）テーブルをプローブします。

サンプルコード：

私の質問は、削除済みとしてタグ付けされたセルに停止して挿入しない理由はありますか？つまり、このfindPosメソッドでは、whileステートメントをに変更しwhile(data[currentPos].state==ACTIVE && data[currentPos].key!=key)て、キーのあるセルまたは最初に削除された/空のセルが見つかったときにループが終了するようにします。次に、挿入で、セルの状態をテストします。アクティブな場合、エントリはすでに存在するため、falseを返します。それ以外の場合は、要素を挿入します。

私はハッシュテーブルのputメソッドのJavaの実装を調べていて、これに出くわしました：

衝突をチェックするにはキーが必要であることを理解していますが、なぜJavaはキーのハッシュ値を保存し、それもチェックするのですか？

私は次のようにハッシュの概念にいくつかの理解の問題を抱えています：

キーを数値として持つハッシュテーブル（1-D配列、たとえばA [100] ）を実装したとします。単純なハッシュ関数H（Key）％Table_Sizeが1つあります。これは、ターゲットインデックスをハッシュテーブルに返します（この特定のキーに関連付けられた値にアクセスしている間）。

0（キー）をテーブルに格納したいとします。このキーをH（ハッシュ関数）に渡すと、ランダムなインデックス、たとえば25が返されます。

配列A（インデックス25）のこの場所には2つの可能性があります。

1. A [25]には、すでに保存されている0以外のキーが含まれています（以前）
2. A[25]には0が含まれています

最初の可能性には衝突があり、簡単に識別できます（現在のkey：0とすでに保存されているkey：kが異なるため）。したがって、最初の可能性では問題ありません。

しかし、2つ目は、衝突の有無をどうやって知ることができるでしょうか。

私が知っている限り、ハッシュテーブルまたは配列はメインメモリの一部になります。A[25]がメモリ位置500に格納されているとします。

この場所（500）が実際に空であるか、他のキーで既に埋められている天気をどのように知ることができますか？

メモリーセルのどのステータスまたは値がEMPTYまたはNULLまたはUNUSEDの場所を表しますか？

そして、衝突チェックを行ってこの場所にキーとして0を格納したい場合はどうなりますか？

現在、メモリの場所がEMPTY、NULL、またはUNUSEDの場合、RESET状態（すべてのセルが0）になると想定しています。これは本当ですか ？

ばかげた質問かもしれませんが、そのような場合の衝突をどうやってチェックするのか気になります。

-

前もって感謝します！！（ハイテイン、ハイデラバード）

adler32() をハッシュ関数として使用する場合、まれに衝突が発生することが予想されます。

衝突の確率を正確に計算することはできますが、大まかに言えば、
これは 32 ビットのハッシュ関数である
ため、数千のアイテムのサンプル セットで多くの衝突が発生することはありません。

これはほとんど当てはまりません。

以下に例を示します: 真ん中に日付を含む文字列を考えてみましょう。

ここで、日付の形式は yyyy-mm-dd で、2012 年をループします。

この例では 91 回の衝突があります。

さらに悪いことに、3 つの日付が重なったケースが 7 つあります。

このように一般的に使用されるハッシュ関数のパフォーマンスが低いのはなぜでしょうか?
または、何か不足していますか？

上記の例の詳細な結果は次のとおりです。

特定の文字列に対して一意のハッシュを作成したいのですが、md5 と sha1 の重複ハッシュに違いがあるかどうか疑問に思っていました。

議論のために、次のコードを想定してみましょう。

sha1 と md5 で発生確率に違いはありますか? また、大きな重複がある文字列 (「blabla1」、「blabla2」) を使用すると、違いはありますか?

ところで。アルゴリズムのセキュリティには興味がありません。できるだけ一意のハッシュを作成したいだけです。

GUID's間（128ビット）またはSHA1ハッシュGUID's（160ビット）のときに衝突が発生する可能性は高くなりますか？私の意見では、GUID（32ビット少ない場合でも）（保証がないため）一意であることを確認するための特別なメカニズムがあるため、（例：タイムスタンプ）の可能性は低くなります。

注：私は、aGUIDが別のaと衝突する可能性が非常に低いことをすでに知っていGUIDます。これについては、これ以上議論しないでください。

BがconstでCが変数の場合、Aを見つける方法は? (C で解決策がない場合は変更できます)

A は DWORD、B は DWORD、C は BYTE != 0

Edit1: GalacticJello の回答の後、別の質問があります:ループなしでそれを行う方法はありますか (式を単純化します)?

なぜこれが必要なのですか?

現在、ランダムな C を生成してから A を検索するループがあります ([A の] ランダムな値を生成するループを使用して A を検索し、上記の式が true かどうかを確認します)。

Edit2:これは、衝突を検索するための現在のコードであり、現在テストしています..

3種類のプロービングを使用して、プロジェクトのハッシュテーブルを実装しています。現在、リニアに取り組んでいます。

線形プロービングについては、プロービングがどのように機能するかを理解しており、私のインストラクターは、ステップサイズを1にしたいとほのめかしました。つまり、重複は許可されていません。ですから、値を挿入する前に、値を「検索」する必要がありますよね？しかし、すべてのセルが「占有」または「削除」されるまでテーブルが使用された場合はどうなるでしょうか。次に、特定のキーを検索してそのキーがテーブルにないことを確認するには、テーブル全体を検索する必要があります。つまり、検索操作（ひいては挿入操作）はO（n）です。

それは正しくないようで、私は何かを誤解したと思います。

テーブルは少なくとも半分空である必要があり、決定された数の要素のみをプローブするため、2次プローブで同じ問題に遭遇する必要はないことを私は知っています。また、ダブルハッシュの場合、挿入するキーが存在しないことを証明するためにテーブルを検索する必要があるため、これがどのように機能するかはわかりません。しかし、どのセルも「占有されていない」場合に検索を停止する方法をどのように知ることができますか？

したがって、過去にテーブル内のすべてのエントリが占有されていたオープンハッシュでは、要素を検索するためにO（n）プローブが必要ですか（重複が許可されていない場合は挿入します）？