問題タブ [integer-hashing]

私はこのクラスを持っています...

...そして、あるオブジェクトが他のオブジェクトと等しい場合にのみ、そのようなオブジェクト間の同等性をiStart定義しiStopます。iStartiStop

をオーバーライドしたのでequals()、オーバーライドする必要がありますhashCode()が、このクラスに適切なハッシュ関数を定義する方法がわかりません。iStartandを使用してこのクラスのハッシュ コードを作成するには、どのような方法がよいでしょうiStopか?

ハッシュ関数と言うとき、ほとんどの記事でキーのシーケンス バイトを 32 ビットまたは 64 ビットの符号なし整数に変換することを意味することがわかりました。たとえば、これを参照してください。

しかし、hash_table を実装すると、そのハッシュ関数は非常に大きな整数をより小さな内部配列インデックスに変換することを意味するように見え、このドメインでは、上記の「ハッシュ関数」の意味がキーのハッシュ値に変更されます。

1. 私の理解は正しいですか？
2. 大きな整数を小さな内部配列インデックスに変換することに関する洞察、リンク、または論文を誰かが提供できますか?

ありがとう

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

キーを数値として持つハッシュテーブル（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）になると想定しています。これは本当ですか ？

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

-

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

私は割り当てに取り組んでおり、10,000個の数値をロードサイズ.1、.2 .3 ....〜.9のハッシュテーブルにハッシュする必要がありました。私の問題は、ハッシュ関数がオーバーフローなどを発生させていることです。36077（mod）20,000のように負荷率が.5のテーブルのハッシュを実行している場合、キーとして16070が返されます。これは、負荷率を超える数値でのみ発生します。これは私のハッシュ関数のコードです。

ありがとうございました。

学校の課題用に独自のハッシュクラスを作成しようとしていますが、途中でデバッグできなかったエラーが発生します。

プロジェクトを実行すると、「デバッグアサーションに失敗しました！...式：無効なnullポインタ」が表示されます。

プログラムは、ドライバーファイル（test.cpp）の16行目にこのエラーを表示しています。私のクラスへのポインタはではないように見えNULLます。

このエラーの原因と、それを修正する方法についてのヘルプをいただければ幸いです。

2タプルの別のリストで一致する2タプルを見つける最も簡単な方法は何ですか？

次のコードは非常に非効率に見えます。loc1とloc2は、（x、y）座標のタプルのリストです。

ハッシュが鍵だと思いますが、Pythonでそれを行う方法がわかりません。エレガントなコードを教えてください。ありがとう。

I've been looking for finding the best solution to store highly sensitive information like an Amount or a balance in a banking application. Can I store that just as a numeric field or Do I need any encryption to encrypt that data? Am a bit worried about encryptions since these fields are frequently being accessed by the users. So when ever it gets accessed there needs to be some decryption mecahnism and to store back the new balance amount that again needs some encryption. Or is there is a better solution for that.

Database is SQL Server 2008 R2 and the platform is .NET 4.0

整数の順序が計算されたハッシュ値に影響を与えないように、一連の整数をハッシュしたいと考えています。すなわちH([32224,12232,564423]) == H([564423,32224,12232])。

ユニークなセットの数は、数百万の範囲になります。速度は非常に重要ですが、選択したアプローチとの衝突の上限を知る必要があります。

ウィキペディアにはベクトルのハッシュに関する優れたセクションがありますが、コードで自信を持って実装するための背後にある数学を理解していません。誰かがコードに関連する数学を説明できれば幸いです。理想的には、最終的なハッシュを 32 ビットにしたいと考えています。それが役に立ったら - 私はこれを Java で実装します。

更新：パフォーマンス上の理由から（そのようなセットを多数操作するため）、セット内の整数のソートを避けることを特に検討しています。

64 ビットのダイ リビジョン フィールドを 32 ビットの MAC アドレスに変換して、ワイヤレス アプリケーションで衝突を回避する方法についての提案を検討しています。

ダイス情報は

座標の範囲はわかりませんが、いくつかのサンプルに基づいて、座標は < 256 に制限されていると思います。これにより、スペースが効果的に 2 バイト削減されます。しかし、そのlot数は完全に取り込まれています。

これを試してみます（読みやすくするための疑似コード、キャストは省略しています）

の上位 16 ビットとslotの上位 8 ビットを破棄しcoordinateます。どこかの上位16ビットでXORする必要があるかもしれませんがlot、現実の世界でこれを経験したことはありません。

ダイ リビジョン情報のサンプルを次に示します。リトル エンディアン バイト ダンプ

背景情報:

私のプロジェクトでは、マリオ ドメインに強化学習 (RL) を適用しています。状態の表現には、カスタム オブジェクトをキーとして持つハッシュテーブルを使用することにしました。私のカスタム オブジェクトは不変で、(IntelliJ IDE によって生成された) .equals() と .hashcode() を上書きしました。

これは結果の .hashcode() です。追加情報としてコメントに可能な値を追加しました。

問題：

ここでの問題は、上記のコードの結果が を超える可能性があることInteger.MAX_VALUEです。これは問題である必要はないことをオンラインで読みましたが、私の場合はそうです。これは、Q ラーニング (RL メソッド) であるアルゴリズムが使用されているためであり、ハッシュテーブル内に格納されている正しい Q 値に依存しています。基本的に、値を取得するときに競合することはできません。実験を実行すると、結果がまったく良くないことがわかり、問題がハッシュテーブルからの Q 値の取得にあることは 95% 確信しています。（必要に応じて、これについて確信がある理由を詳しく説明できますが、これには、質問に関係のないプロジェクトに関する追加情報が必要です。）

質問：

整数オーバーフローを回避する方法はありますか?ここで何かを見落としている可能性がありますか? または、カスタムキーを指定して値を合理的に高速に取得する別の方法 (おそらく別のデータ構造) はありますか?

述べる：

いくつかのコメントを読んだ後、衝突を引き起こさない一意のキーが必要なため、HashTable を使用するための私の選択はおそらく最良のものではないことに気付きました。それでも HashTable を使用したい場合は、適切なエンコーディングが必要になるでしょう。