問題タブ [hash-collision]

私のウェブアプリでは、パフォーマンスレベルを最適化するために、ハッシュで生成されたファイル名を含むキャッシュファイルをさまざまなサブディレクトリに保存しています。パフォーマンスを向上させる方法の1つは、生成された名前が8.3ファイル名構造に従うようにすることです。これにより、NTFSで短いファイル名を生成する必要がなくなります（レジストリで設定できなくなります）。

そのためには、ハッシュ（SHA1を考えていた）を8文字にトリミングする必要がありますが、これにより、衝突の可能性が大幅に高まります。私が知りたいのは、衝突の確率はどれくらいかということです。

ここで完全なSHA1ハッシュ衝突率に関する答えを見てきましたが、私の計算はひどいので、値の計算は私をはるかに超えています。

thisによると、ハッシュテーブル内の検索の時間計算量は O(1) です。

ただし、衝突が発生した場合、明らかにこれは O(1) + 何かになるはずです。

私の質問は：

あなたが言う時

ハッシュテーブルから、ハッシュ関数が someKey に適用され、データがその場所から直接取得されます。

しかし、衝突の解決に分離チェーンが使用されていると想像してください。そして、ハッシュ関数が適用された後、 someKey と someOtherKey が同じ出力を持つと想像してください。それが値「25」であるとします。

だから私が言うとき

ロケーション「25」からデータを取得します。これにより、O(1) になります。偉大な。

しかし、私が言うとき

someOtherKeyがsomeKeyの場所にリンクされるようになりました。

ハッシュがsomeOtherKeyに適用されると、25 になります。

必要な値を取得するにはどうすればよいですか? 内部構造は何ですか？他のテーブルはありますか？アルゴリズムの流れは？すべての衝突を保存するための他のテーブルはありますか?

ありがとうございました。私の質問が明確であることを願っています！

このコード ブロックは、辞書ファイルを読み取り、それをハッシュ配列に格納します。このハッシュ配列は、リンクされたリストの競合解決を使用します。しかし、どういうわけか、途中で読みが止まってしまいます。(リンクされたリストが作成されたときに何らかの問題が発生すると想定しています。) データが空のハッシュ配列要素に格納されている場合、すべて正常に機能します。

createListとaddNode両方とも ADT 関数です。前者は関数ポインタ（compare関数内に私が作成したmain関数です）をパラメータとして取り、後者はリスト名とvoid型データをパラメータとして取ります。compareリンクされたリストを並べ替えます。問題を見つけてください。

MD5 と同様の特性を持つ、暗号的に安全なハッシュ関数が必要です。つまり、128 ビット サイズで高速です。最近は MD5 自体がかなり壊れているので、別のハッシュを使用したいと考えています。SHA1 は最近、少なくとも私のコンピューターでは (openssl speed md5 sha1あなたのコンピューターで試してみてください)、実際には MD5 より高速です。ただし、セキュリティと衝突の影響についてはわかりません。

1. そのようなハッシュ関数は、実際の 128 ビット ハッシュ関数よりも安全性が低くなりますか?
2. そのようなハッシュ関数は、実際の 128 ビット ハッシュ関数よりも衝突しやすいですか?

_{ps元の質問の範囲外であっても、高速な128ビットハッシュの代替案に関する代替案も歓迎します。}

私は、ゲームの世界のすべてがグローバルな一意の識別子によって表されるゲームを開発しています。

これらの ID はそれぞれ 64 ビットを測定し、作成時間、マシンのネットワーク アドレス、および乱数を一緒にハッシュすることによって生成されます。ウィキペディアの誕生日問題に関する記事によると、ハッシュ衝突の確率は 2 億レコードで 0.1% です。

それほど多くのレコードを取得する可能性は低いため、ハッシュが衝突することはないと考えることができます。しかし、私はそれを望んでいませんが、ID の衝突、つまりハッシュの衝突というまれなケースをアプリケーションで処理できるようにします。

そうしないと、ゲーム ワールド内の 2 つの独立したものが接続され、位置、動き、ヘルス ポイントなどのプロパティが共有されるため、この動作は望ましくないものになります。

ハッシュの衝突を処理するにはどうすればよいですか? それらは通常どのように処理されますか？

一部のデータをハッシュして、グローバルで一意の ID を生成する必要があります。

一方では、タイムスタンプとネットワーク アドレスの組み合わせを使用できます。これは、すべてのコンピューターが同時に 1 つの ID しか作成できないため、一意です。しかし、このデータは長すぎるため、ハッシュする必要があり、衝突が発生する可能性があります。(補足として、タイムスタンプが十分に正確でない場合は、乱数を投入することもできます。)

一方、乱数を使用してそれをハッシュすることもできます。最初のアプローチとまったく同じハッシュ衝突確率をもたらすべきではありませんか? このアプローチはより高速で、実装がはるかに簡単であるため、興味深いものです。

ランダム データではなく一意のデータを使用する場合、ハッシュ衝突に関して違いはありますか? (ちなみに、私は標準で説明されているように実際の G​​UID を使用しませんが、私のものは 64 ビット長のみです。しかし、それは質問に影響を与えるべきではありません。)

問題

行ごとに 1 つの文字列を含むテキスト ファイルがあります (改行 \r\n)。このファイルは、2 つの異なる方法で CRC16 を使用して保護されています。

1. 4096 バイトのブロックの CRC16
2. 32768 バイトのブロックの CRC16

ここで、これらの 4096 バイト ブロックのいずれかを変更する必要があるため、(ブロック)

• 特定の文字列を含む
• テキストファイルのサイズを変更しません
• 元のブロックと同じ CRC 値を持つ (この 4k ブロックを含む 32k ブロックも同じ)

その制限を除いて、ファイル自体がそのフォーマットを壊さない限り、ブロックを満たすために必要な変更をブロックに加えることができます。最後のブロックではなく、完全に満たされた 4k ブロックのいずれかを使用するのが最善だと思います。

質問

その問題を解決するにはどうすればよいですか？私が思いつく最初のことは、ある種のブルートフォースですが、両方のCRC値が同じままになる変更を見つけるのに非常に時間がかかりませんか? おそらくそれを解決する数学的な方法はありますか？

数秒または最大で実行する必要があります。数分。

私は今、Apache commons langのHashCodeBuilderのような組み込みユーティリティを利用できることを知っていますが、自分でそれを実装する方法を理解しようとしていて、http://en.wikipedia.org/wiki/Java_hashCodeでEmployeeクラスのhascode関数の例に出くわしました()

Googleのどこでも、ゼロ以外の値に奇数の素数を掛けてからインスタンス変数と合計するなど、同じ種類の手法が提案されています（インスタンス変数に対して実行します）。

質問:-

1) 一意であるため、employeeId を hascode として返すことができないのはなぜですか。シンプルで、hascode の目的を果たします。ユニークでない場合は、おそらくそのようなテクニックが必要です。そうですか？

2)従業員IDが一意ではない場合でも、奇数の素数を掛けることが提案されているのはなぜですか? なぜいまいましい整数を取ることが良いと見なされないのですか?

アップデート：-

ピーター私はあなたがそれが印刷されたと述べた例を実行しました

[0, 32, 64, 96, 128, 160, 192, 224, 288, 256, 352, 320, 384]

[0, 32, 64, 96, 128, 160, 192, 224, 288, 256, 352, 320, 384]

私はあなたがあなたの答えで述べたように概念を理解することを期待していたように、今のところその出力を想定しています

[373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]

[0, 34, 68, 102, 137, 171, 205, 239, 275, 305, 343, 373]

コメントで示唆したように、この例では、一意のハッシュコードでも同じバケットになる可能性があることを示しました。この例は、この動作をどのように示しましたか? integers の場合は 373 で、integers2 の場合は 0 が同じバケットになるということですか?

この例で素数はどの程度役に立ち、34 は役に立たなかったのでしょうか?