問題タブ [hash-collision]

バイナリ アセットごとに、MD5 ハッシュを生成します。これは、特定のバイナリ アセットがアプリケーションに既に存在するかどうかを確認するために使用されます。しかし、2 つの異なるバイナリ アセットが同じ MD5 ハッシュを生成する可能性はありますか? では、2 つの異なる文字列が同じ MD5 ハッシュを生成する可能性はありますか?

アプリケーションの一部にファイルを保存しています。同じファイルを多数追加する可能性があるため、最初に各ファイルのハッシュを保持します。2つのファイルが同じハッシュを持っている場合、1つを破棄し、そのファイルへの両方の「参照」が同じ物理ファイルを指します。

1. ハッシュの衝突についてどのくらい心配する必要がありますか？

2. 衝突の場合はどうすればいいですか？これまでの私のコードの核心は、同じハッシュを持つ2つの異なるファイルがないことに依存しています。現在衝突が発生した場合、私のアプリは合法的に異なるファイルをスローし、同じハッシュを持つファイルを指します。

3. MD5以外のものを使用する必要がありますか？SHA-1の方が衝突率は高くなりますか？

HashMapの配置中に衝突が発生した場合、マップのサイズが変更されますか、それともその特定のバケットのリストにエントリが追加されますか？

テーブルにキーを設定する必要があるカスタムオブジェクトに問題があります。一意の数字キーを生成する必要があります。衝突の問題が発生しているので、辞書を利用して支援できるかどうか疑問に思っています。私がこのようなオブジェクトを持っていると仮定します：

など、より多くのフィールドがあります。FooとBarが私のキーフィールドだとしましょう。2つのThingys間で等しい場合、2つのオブジェクトは等しいと見なす必要があります（一方が他方の更新を表し、Othersフィールドが更新されている場合があります）。

したがって、これはほとんどの部分で機能しますが、実際には異なる2つのThingysが同じハッシュコードを持っている場合はまれです。

私の質問はこれです：<Thingy, intThingysを入れた辞書を使用して、辞書から出てくるシーケンシャル値を実際のキーとして使用できますか？ディクショナリが、まれなハッシュコードの衝突を検出したときに、Equalsメソッドを呼び出して、オブジェクトが実際に異なると判断し、それらを異なる方法で格納するかどうか疑問に思っています。イメージングしてから検索すると、そのハッシュのバケットが表示され、比較のためにEqualsを使用して、正しいThingyが検索されます。

これは辞書の場合ですか、それともハッシュコードが異なるが（ハッシュ％サイズ）が同じである衝突のみを解決しますか？これがうまくいかない場合は、どうすればよいですか？

私はハッシュテーブルとCでの実装方法についてたくさん読んでいますが、頭の中にはほとんどすべての概念があるので、自分でコーディングを開始できると思います。まだいくつか質問があります。正しく理解します。

参考までに、私はこれを読んでいます：http: //eternallyconfuzzled.com/jsw_home.aspx

1）上記のサイトで読んだように、ハッシュテーブルのサイズには2の累乗または素数をお勧めします。これは基本的に配列であり、配列のサイズは固定されているため、探している値をすばやく検索できます。大きな入力がある場合は収まらないため、小さな配列を宣言できません。また、入力データがそれほど大きくないためにメモリが無駄になるため、非常に大きな配列を宣言できません。

ハッシュテーブルの最適なサイズはどれくらいですか？何に基づいて決定する必要がありますか？

2）また、そのサイトには、まだすべてを読んでいないハッシュ関数がいくつかあります。また、よく知られたアルゴリズムを使用し、独自のアルゴリズムを使用することが常に最善であるとも述べています。そして、私はまさにそれを行うかもしれません。そのサイトから1つを選び、コードでテストして、入力データに基づいて衝突が最小限に抑えられるかどうかを確認します。

私を悩ませているのは、ハッシュ範囲をどのように制御するかです。ハッシュを返すことができず、ハッシュテーブルのサイズよりも大きい整数を返すことができません。そうしないと、深刻な問題が発生します。どうすればこれに対処できますか？

ハッシュテーブルの現在の実装は線形プロービングを使用しており、今度は2次プロービングに移行したいと思います（後でチェーン化とおそらくダブルハッシュにも移行します）。いくつかの記事、チュートリアル、ウィキペディアなどを読みましたが、まだ正確に何をすべきかわかりません。

線形プロービングは、基本的に1のステップがあり、それは簡単に実行できます。ハッシュテーブルから要素を検索、挿入、または削除するときは、ハッシュを計算する必要があり、そのために次のことを行います。

次に、検索、挿入、または削除中に、次のように空きバケットが見つかるまでテーブルをループします。

Quadratic Probingに関しては、「インデックス」ステップサイズの計算方法を変更する必要があると思いますが、それをどのように行うべきかわかりません。私はさまざまなコードを見てきましたが、それらはすべて多少異なります。

また、ハッシュ関数がそれに対応するように変更されたQuadratic Probingのいくつかの実装を見てきました（すべてではありません）。その変更は本当に必要ですか、それともハッシュ関数の変更を避けてQuadratic Probingを使用できますか？

編集： 以下のEli Benderskyによって指摘されたすべてを読んだ後、私は一般的な考えを得たと思います。http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspxのコードの一部は次のとおりです。

私が得られないことが2つあります...彼らは、二次プロービングは通常、を使用して行われると言いますc(i)=i^2。ただし、上記のコードでは、次のようなことを行っていますc(i)=(i^2-i)/2

私はこれを自分のコードに実装する準備ができていましたが、単純に次のようにします。

...ではなく：

どちらかといえば、私はします：

...他のコード例が2つに分かれているのを見たからです。理由はわかりませんが...

1）なぜステップを引くのですか？
2）なぜ2でダイビングするのですか？

私は多数のファイルをハッシュしており、ハッシュの衝突を避けるために、ファイルの元のサイズも保存しています。これにより、ハッシュの衝突があったとしても、ファイル サイズも同じになる可能性はほとんどありません。この音 (ハッシュの衝突はどのようなサイズでも同じように発生する可能性があります) ですか、それとも別の情報が必要ですか (衝突がオリジナルと同じ長さである可能性が高い場合)。

または、より一般的には、元のファイルのサイズに関係なく、すべてのファイルが特定のハッシュを生成する可能性は同じですか?

現在、私のハッシュテーブルは、ハッシュテーブルに挿入されたすべての要素の数を数えています。このカウントとハッシュ テーブルの合計サイズを使用して負荷率を計算し、70% 程度に達したら再ハッシュします。

挿入された要素をすべてではなく、空のスロットを埋めるだけでカウントする必要があるのではないかと考えていました。私が使用している衝突方法は、個別の連鎖です。要素の負荷は増加し続けますが、いくつかの衝突が発生する可能性がある場合は、ハッシュ テーブルに多くの空のスロットが残ります。

あなたはおそらく、これほど多くの衝突が発生した場合、最適なハッシュ方法を使用していないのではないかと考えているでしょう。しかし、それはポイントではありません。私は既知のハッシュ アルゴリズムの 1 つを使用しています。サンプル データで 3 つのアルゴリズムをテストし、衝突が少ないアルゴリズムを選択しました。

私の疑問はまだ残っています。挿入されたすべての要素を数え続けるべきですか、それともハッシュ テーブルの空のスロットを埋める要素だけを数えるべきですか?

リンクされたリストではなく (2 次元) 配列にオブジェクトを格納する C でのハッシュテーブルの実装を探しています。つまり、衝突が発生した場合、衝突を引き起こしているオブジェクトは、リンクされたリストの先頭と最初の要素にプッシュされるのではなく、次の空き行インデックスに格納されます。

さらに、ポインターによって参照されるのではなく、オブジェクト自体をハッシュテーブルにコピーする必要があります。(オブジェクトはプログラムの存続期間全体にわたって存続するわけではありませんが、テーブルは存続します)。

そのような実装には深刻な効率上の欠点がある可能性があり、「標準的なハッシュ方法」ではないことはわかっていますが、非常に特殊なシステムアーキテクチャに取り組んでいるため、これらの特性が必要です。

ありがとう