問題タブ [hashcode]

次のプロパティを持つ特定のハッシュコードを探しています。私はそのようなハッシュコードを知りませんし、そのようなことをすることが可能かどうかもわかりません。ただそれをそこに出して、人々が言うことを見たかったのです。

私は2つのデータベース（大まかに使用される用語-SQLやそのようなものは考えないでください）、1つはマスター、もう1つはバックアップを持っています。2つのデータベースの同期を維持し、データベースが同期していないことを検出する必要があります。そこにあるすべてのデータを検証するのではなく、検証可能なハッシュコードを保持することが望ましいでしょう。ただし、2つのデータベースが必ずしもすべての変更を共有するわけではありません。マスターからバックアップへの変更はバッチ処理されるため、マスターからバックアップへの特定の変更が折りたたまれる可能性があります。

つまり、データベースの現在の状態に要素A-> X、B-> Y、およびC->Zがあるとします。ここで、BはB-> Y1に変更され、その後B->Y2に変更されます。マスターからバックアップに送信される唯一の変更は、B->Y2です。中間のB->Y1はスキップされます。

ここで、各データベースのすべての要素をループしてそれらが一致することを確認するのではなく、両方の場所で要素の実行中のハッシュコードを保持し、それを比較することをお勧めします。ハッシュコードは次のようなものを計算する必要があります。

hm0の以前のハッシュコードを想定：
ハッシュコードhm1 = f（hm0、A-> X、B-> Y、C-> Z）

Bが変更された場合：
ハッシュコードhm2 = f（hm1、B-> Y1）
、次に
ハッシュコードhm3 = f（hm2、B-> Y2）

したがって、マスターはh3のハッシュコードを持ちます。これで、バックアップは変更B-> Y2を受け取らないため、実行中のハッシュコードを計算すると、次のようになります。

ハッシュコードhb1=f（hb0、A-> X、B-> Y、C-> Z）
ハッシュコードhb2 = f（hb1、B-> Y2）

データベースの現在の状態は同じであるため、hb2とhm3を一致させる必要があります。しかし、ほとんどの（すべてではないにしても）ハッシュコードはこのようには機能しません。

したがって、最初にハッシュからB-> Yの寄与を「削除」し、次にB-> Y1の寄与を「追加」してから、B-> Y1の寄与を削除して、ハッシュコードへのB->Y2の寄与。したがって、次のようなものが必要です。

2つの関数f、g：fは、新しい要素の寄与を追加することによって既存のハッシュコードを変更し、gは、要素の寄与を削除することによって既存のハッシュコードを変更します。

マスターの場合：
hm1 = f（hm0、A-> X、B-> Y、C-> Z）

BがB->Y1に変更されたとき：
hm2 = g（hm1、B-> Y）
hm3 = f（hm2、B-> Y1）

BがB->Y2に変更された場合：
hm4 = g（hm3、B-> Y1）
hm5 = f（hm4、B-> Y2）

hm5は、データベースの現在の状態の新しいハッシュコードです（A-> X、B-> Y2、C-> Z）

バックアップ時：
hb1 = f（hb0、A-> X、B-> Y、C-> Z）

BがB->Y2に変更されたとき：
hb2 = g（hb1、B-> Y）
hb3 = f（hb2、B-> Y2）

これで、両方のデータベースの現在の状態が同じであるため、hm5とhb3が一致するはずです。

だから：そのようなアルゴリズムfとgはありますか？質問を明確にしたいと思います。ありがとうございます。

これは奇妙です。同僚が myArray.hashCode() の Java での実装について尋ねました。私は知っていると思っていましたが、いくつかのテストを実行しました。以下のコードを確認してください。私が気づいた奇妙なことは、最初の sys out を書き込んだとき、結果が異なっていたことです。メモリアドレスを報告し、クラスを変更するとアドレスか何かが移動したように見えることに注意してください。私が共有すると思っただけです。

オーバーライドに関する StackOverflow のすべての質問と回答を読んだ後GetHashCode()、簡単で便利なオーバーライドのために次の拡張メソッドを作成しましたGetHashCode()。

(私は基本的に誰かがそこに投稿したコードをリファクタリングしただけです。なぜなら、それが一般的に使用できることが本当に好きだからです)

私はこのように使用します：

このコードに問題はありますか?

Java String の hashCode 値は ( String.hashCode() ) として計算されます。

次の式が false と評価される状況 (JVM のバージョン、ベンダーなど) はありますか?

更新 #1:答えが「はい、そのような状況がある」と主張する場合は、「これは Java 文字列です」.hashCode() != 586653468 の具体例を挙げてください。具体的/具体的になるようにしてください。できるだけ。

更新 #2: hashCode() の実装の詳細に依存することは一般的に悪いことです。ただし、私は特に String.hashCode() について話しているので、答えは String.hashCode() に集中してください。Object.hashCode() は、この質問のコンテキストではまったく関係ありません。

有名なJDKのドキュメントには次のように書かれています：java.lang.String.hashCode()

String オブジェクトのハッシュ コードは次のように計算されます。

は文字列の * * 番目の文字、 は文字列の長さであり、べき乗を示しintます。s[i]in^

この式の標準的な実装は次のとおりです。

これを見ると、アルゴリズムのコースで寝ていたような気がします。その数式は、上記のコードにどのように変換されますか?

木を表すいくつかの大きなオブジェクトを比較し、何かをキャッシュして、新しいオブジェクトを既存のオブジェクトと毎回比較することを避けたいと思います...

質問は、何が最高のものでしょうか? （パフォーマンスと衝突の間の妥協...）。

一方では、さまざまなフィールドの値に基づいた通常の hashCode 関数があります ( effective Javaの第 3 章に従っています。しかし、このようなアプローチに伴う潜在的な衝突を評価することはできません。

一方、SHA-1アルゴリズムを使用した標準のJavaディストリビューションからのMessageDigestアプローチがあります。効率的ではないと思いますが、衝突が少ないかもしれません。私は正しいですか？私のコンテキストでは正しい解決策ですか、それとも完全に間違っていますか?

問題は、オブジェクトのサイズがどうなるかわからないということです。また、計算された値は HashTable では使用されないことに注意してください。

どうも...

私は、人々が次のことを行うためにどのデータ構造を推奨するのか疑問に思っています。私は3つの主要なプロパティを持つクラスを持っています.

別のクラスにはこれらのオブジェクトのコレクションが含まれており、頻繁にこれらを列挙する必要がありますが、これは主に LINQ で行います。多くの場合、主にプロパティ One の値に基づいてこれらのオブジェクトのサブセットのみを検索/列挙する必要があるため、そのプロパティに基づいて効率的なデータ構造にこれらを格納したいと考えています。次のようなことができます。

しかし、これは非常に非効率的だと思います。ある種のハッシュテーブルが必要であることは知っていますが、C# でこれまで使用したことがないため、何を使用すればよいかわかりません。

その他の要件/メモ:

• すべてのオブジェクトは不変であり、クラスがコンストラクターでインスタンス化される値から計算される固定ハッシュ コードを持っています。
• データ構造の同じ「スロット」にプロパティ One の同じ値 (およびハッシュ コード) を持つ複数のアイテムを格納できる必要があります。
• コレクションからオブジェクトを自由に追加および削除できる必要があります

Java のクラスがhashCode()をオーバーライドしない場合、このクラスのインスタンスを出力すると適切な一意の番号が得られます。

Object の Javadoc は、hashCode()について次のように述べています。

合理的に実用的である限り、クラス Object によって定義された hashCode メソッドは、個別のオブジェクトに対して個別の整数を返します。

しかし、クラスがhashCode()をオーバーライドする場合、一意の番号を取得するにはどうすればよいでしょうか?