問題タブ [hash-collision]

次のコードがあります。これは、30 個の文字列 (数値) を取り、"%29" で計算した後、それらをハッシュ テーブルに入れます。

便宜上、出力は次のとおりです。

ご覧のとおり、この特定のハッシュ テーブルを構築するときに発生した衝突の平均回数を教えてくれるように設定しました。30 個の数字と 30 個のスペースがあります。使用可能なスペースの量のパラメータを 30 から 60 に変更しようとしましたが、何も変わりませんでした。これを修正する方法を見つけたいと思います。

このコードをワンランク上のものにしたいので、これは私にとって重要です。このプログラムをより大きな数のセット、おそらく1000以上の数で試してみたいと思いますが、1000以上の文字列番号を手動で入力したくありません。これを行うループをどのように記述すればよいでしょうか? たとえば、パラメーターに 1000 を入力すると、使用される文字列表記 (コードで見られるように) で 1000 の数字が生成されます。

また、これらの文字列番号を 1 回のプログラム実行で複数実行できるようにしたいと考えています。たとえば、ハッシュテーブルは1000個の数値を保持できるため、1つの数値、次に2、3などでプログラムを実行し、1000まで実行します。そして、これを実行するたびに、その特定の実行で発生した衝突の平均数を出力したい。数が 1 つだけの場合は衝突は発生せず、最終的には数が増えるにつれて衝突が発生します。

これを行うことで、使用可能なスポットに対する数の比率が変化するにつれて、衝突の量がどのように変化するかを示すグラフを作成できます。たとえば、x 軸は平均衝突数であり、y 軸は使用可能な合計スペースと比較した入力数値の量の比率です (値の範囲が 0 から 1.00 になることを意味します)。

時間を割いて教えてくださったすべての方々に、事前に感謝します。ほんとうにありがとう。

連続する整数 (0、1、2、3 など) から一意の 8 文字の文字列を生成する必要があります。

intをmd5/sha256/sha512でハッシュしてから8文字に短縮しようとしましたが、可能であれば回避したい衝突がかなりあります。

私は crc32 などのアルゴリズムを調べましたが、それから生成されたハッシュには好みの数値が多すぎます。

私が必要とすることを行う別の方法を誰かが提案できますか?

この方法で、特定の Type を Vector2i タイプにマップするコレクションを作成しようとしています。

以前に C# で作成したプロジェクトを Haxe に変換しています。C# では、Vector2i を使用して Dictionary をインデックス化できるようにするために、Vector2i にインターフェイスを実装するだけで済みましたが、Haxe で同じことを達成するために何をしなければならないかわかりません。

大きなテキスト (検索、貼り付け、削除) の操作速度 O(1) でハッシュ テーブルを作成する必要があります。それは本当ですか？衝突を最小限に抑えるには？例はありますか？後で C++ を使用したことはありません。テキストの辞書を持つハッシュテーブルの例が見つかりません。
ターゲット言語 C++ (STL のみ)。

Web サイトにアクセスするすべてのユーザーの一意の識別子として、IP + ユーザー エージェントのハッシュを使用しています。これは非常に明確な落とし穴がある単純なスキームです:識別子の衝突. 複数の個人が、同じ IP + ユーザー エージェントの組み合わせでインターネットを閲覧します。同じハッシュで識別される一意のユーザーは、1 人のユーザーとして認識されます。この識別子エラーが発生する頻度を知りたいです。

頻度を計算するために、理論的には 0% で変換する必要がある 2 段階のじょうごを作成しました: publish.click> signup.complete. (ユーザーは、公開する前にサインアップする必要があります。) この目標到達プロセスを 1 日間実行すると、0.37%のコンバージョン率が得られます。その数字は、そのじょうごの一意の識別子の衝突確率であると私は考えました。生データ (約 10,000 行の長さのテーブル) を見て、この仮説を確認しました。publish.clickファネル期間 (1 日)に完了した古いユーザーと同じハッシュによって識別される新しいユーザーによって、37 のサインアップが完了しました。(私はこれを知っています。なぜなら、サインアップ時に割り当てられる UID は一致しなかったのに対し、ハッシュはファネル全体で一致したからです。)

全部解ったと思ったのに…

しかし、ファネルを 1 週間実行したところ、コンバージョン率は0.78%に上昇しました。5 か月間で、コンバージョン率は1.71%に跳ね上がりました。

ここで何が起こっているのでしょうか? テスト期間を長くするとコンバージョン (衝突) 率が高くなるのはなぜですか?

これは、ユニーク ユーザーが通常 1 回しか発火しないのに対し、期間中に複数回signup.complete発火する可能性があるという事実と関係があるのではないかと思います。publish.clickしかし、私はこの仮説を言葉にするのに苦労しています。

どんな助けでも大歓迎です。

次のコード スニペットに基づく:

.

1. ここで連鎖が起こっていないのはなぜですか？Zara をキーとして再入力すると、古い値が上書きされます。Zara".hashcode()インデックスのリンク リストの最後に追加されることを期待していました。
2. Java は衝突処理にのみ個別のチェーンを使用しますか?
3. チェーンを使用できない場合（上記で試したように）、チェーンを使用するための一般的な方法を提案してください。

Android ミュージック プレーヤー アプリにシャッフル オプションを追加したいと考えています。その目的のために、Java でランダム関数を呼び出して、0 から現在再生中の曲リストのサイズまでの数値を返します。問題は、関数が以前と同じ値を返し、値で繰り返しが発生することです。この問題を回避するために、スタック オーバーフロー自身で利用できる多くの解決策があります。私の場合、その解決策と以下は機能しません。1. シャッフル配列の作成には、0 から最大リスト サイズの値が含まれます。曲リストのサイズは動的であるため、失敗します。2. 曲リスト配列自体をシャッフルします。時間の複雑さのために失敗します。

私が必要とするのは、次のことを行う数学的なハッシュ関数です..

50 が最大範囲の場合、入力番号 1 は 34 などの他の番号にマップされます。21 などの他の番号に 2 を入力します。10 などの他の番号に 3 を入力します繰り返しは許可されません。(マッピング中は連携なし) また、その番号へのマッピングは許可されません。最大範囲が同じ (この場合は 50) で、この関数への入力数値 2 は、アプリケーション全体でいつでも値 21 を返す必要があることに注意してください。

関数時間の複雑さは少なくなるはずです。

このページから、毎秒 50 億回のハッシュを実行できるようです。これは、衝突を起こすのは難しくないということですか? 特定の MD5 または SHA1 でファイルを作成したい場合、どのくらいの時間がかかりますか?

私の計算 (2^160 を使用) によると、まだ長い時間がかかりますが、160 ビットの sha1 ハッシュをブルート フォースするのは 2^160 ではないと聞いています。