問題タブ [hash-code-uniqueness]

オブジェクトのハッシュを生成するための次のコードがありました。

つまり、すべてのプロパティのハッシュコードを追加してから、このハッシュを取得します。

レビューでは、同僚はこれがあまりにも頻繁に衝突することを示唆しました。これが正しいかどうかはわかりません。理由は次のとおりです。

1. ハッシュコードが正の数と負の数の間で同じ頻度で選択され、それらが折り返されることを考えると、数自体ではなく、これらの数の合計の可能性について私たちが得る追加情報はないと思います
2. それらの合計がランダムでない限り、ハッシュコードは、「互いに近い」数値が「離れた」数値になるように設計されているため、関数に不均一に分散された値をフィードすることは問題になりません。

誰が正しいですか？

答えが言語固有の場合に備えて、C＃です。

次の 2 つの条件の下で、ハッシュ関数を作成する必要があります。

• メソッドに渡されるものについては何も知りませんObject o-それは文字列、整数、または実際のカスタムオブジェクトです。
• 通話hashCode()は一切できません。

ハッシュコードを計算するために、私が現在使用しているアプローチ：

1. オブジェクトをバイト ストリームに書き込みます。
2. バイト ストリームをバイト配列に変換します。

3. バイト配列をループし、次のようにしてハッシュを計算します。

   ハッシュ = ハッシュ * PRIME + byteArray[i]

私の質問はまずまずのアプローチであり、それを改善する方法はありますか? 個人的には、この関数の範囲が広すぎるように感じます。オブジェクトが何であるかについての情報はありませんが、この状況ではほとんど何も言えません。

インスタンスでGetHashCode()メソッドを呼び出すときに重複する値を取得する確率を知りたいです。stringたとえば、このブログ投稿によると 、x86 マシンで同じハッシュコード (1758039503) を持っていますblair。brainlessness

たとえば、 .forSetのみHashSetを含むものを作成します が、これらはプリミティブ型で表されませんが、オブジェクトがありますchara,b,c,d,e,f,g...char

今、私はオブジェクトをセットに追加したいのですFirstCharが、繰り返し要素を避けるために実装HashCode()しなければなりませんequals()

実装方法は知っていますが、セットに要素を 1 つしか持たないように実装するにはequalsどうすればよいですか?hashcode

注意。Eclipse を使うように言わないでください

次のような単純なカスタム Point クラスがあり、hashCode の実装を改善できるかどうか、またはこれが最善かどうかを知りたいです。

2つの異なるオブジェクトが同じハッシュコードを持っている場合でもSystem.identityHashCode()、オブジェクトのメモリポインタを返すようです。Sun JDK、OpenJDKを含む32ビットJVM実装でも例外はないと思います。ただし、ソースコードは確認していません。実際には、同じものを持つ2つのオブジェクトが同じであると想定できSystem.identityHashCode()ますか？

オブジェクトを渡すときは、その参照を値として渡していることを知っています。しかし、あなたが得たこの値はhashcode()正しい方法を使用しています(私のテストによれば同じです)? はメモリ アドレスではなく、常に一意の値を取得できる保証もないためhashcode()、オブジェクトを渡すときに衝突などの奇妙なことが起こる可能性はありますか?

(オーバーライドされていないと仮定hashcode()します。つまり、 と同じ値を返しますSystem.identityHashCode())

このような質問は 3 つありますが、渡される値とは何か、どのように取得するのかを説明している関連リソースが見つかりません。

編集： これが私のテストです。デフォルトでtoSting()は、hashCode()内部を使用して 16 進値に変換します。では、オブジェクトを渡すとき、これは渡される値ですか? または、Java は (渡される) すべてのオブジェクトを追跡して、参照の衝突が発生しないようにするために何をしますか?

こんにちは、HashMap に裏打ちされた Set を使用して、グラフ内で既に通過したエッジを追跡しています。各エッジに格納されているデータのハッシュコードを追加した結果によってセットをキーイングすることを計画していました。

しかし、contains を使用してエッジがセット内にあるかどうかを確認する場合、これはどの程度信頼できるのでしょうか? 仮説的に偽陽性を得ることができませんでしたか? とにかくこれを克服する方法はありますか？

私が懸念する正確な声明は次のとおりです。

ありがとう！

あ、ちなみに私はJavaを使っています。

編集：

私は質問でこれを明確にするべきでした。私のグラフにはエッジ オブジェクトはありません。それぞれがより多くの頂点オブジェクトのリストを保持する頂点オブジェクトがあり、これがエッジです。したがって、あなたの回答と合わせて、次の質問が続くと思います。

オブジェクトではなく、情報への参照を格納するために Set を使用できますか? つまり、頂点のデータ オブジェクトの 2 つのハッシュコードを加算した結果を保存できますか?

EDIT2：

私は実際にハッシュマップに Java ライブラリを使用しています。以下のように宣言します。

2 つの int の単純なコンテナー オブジェクトの equals メソッドと hashcode メソッドをオーバーライドしています。各 int は、別のオブジェクトのインデックスを反映します (そのオブジェクトが何であるかは関係ありません)。クラスのポイントは、2 つのオブジェクト間の接続を表すことです。

接続の方向は重要ではないため、equals メソッドは、2 つの int がオブジェクト Eg 内のどの方向にあるかに関係なく、true を返す必要があります。

これが私が持っているものです（整数のソースコードから変更されています）：

これは機能しますが、私の質問は次のとおりです。これを達成するためのより良い方法はありますか?

私の主な心配は、 hashcode() メソッドが乗算して同じ数に等しくなる 2 つの整数に対して同じハッシュコードを返すことです。例えば

ドキュメントhttp://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Object.html#hashCode()には、次のように記載されています。

equals(java.lang.Object) メソッドに従って 2 つのオブジェクトが等しくない場合、2 つのオブジェクトのそれぞれで hashCode メソッドを呼び出すと、異なる整数結果が生成される必要はありません。ただし、プログラマーは、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上する可能性があることに注意する必要があります。

一致するハッシュコードの数を減らす簡単な方法を誰かが見ることができれば、私は答えに感謝します.

ありがとう！

ティム

PS私は、いくつかのインポートの煩わしさを引き起こす可能性のある java.sql.Connection があることを認識しています。このオブジェクトには、実際にはアプリケーション内でより具体的な名前が付けられていますが、簡潔にするために、ここでは Connection に短縮しています。