16

テーブルにキーを設定する必要があるカスタムオブジェクトに問題があります。一意の数字キーを生成する必要があります。衝突の問題が発生しているので、辞書を利用して支援できるかどうか疑問に思っています。私がこのようなオブジェクトを持っていると仮定します：

class Thingy
{
    public string Foo;
    public string Bar;
    public string Others;
}

など、より多くのフィールドがあります。FooとBarが私のキーフィールドだとしましょう。2つのThingys間で等しい場合、2つのオブジェクトは等しいと見なす必要があります（一方が他方の更新を表し、Othersフィールドが更新されている場合があります）。

public override bool Equals(object obj)
{
    Thingy thing = (Thingy)obj; // yes I do type check first
    return (this.Foo == thing.Foo && this.Bar == thing.Bar);
}

public override int GetHashCode()
{
    return (this.Foo + this.Bar).GetHashCode(); // using default string impl
}

したがって、これはほとんどの部分で機能しますが、実際には異なる2つのThingysが同じハッシュコードを持っている場合はまれです。

私の質問はこれです：<Thingy, intThingysを入れた辞書を使用して、辞書から出てくるシーケンシャル値を実際のキーとして使用できますか？ディクショナリが、まれなハッシュコードの衝突を検出したときに、Equalsメソッドを呼び出して、オブジェクトが実際に異なると判断し、それらを異なる方法で格納するかどうか疑問に思っています。イメージングしてから検索すると、そのハッシュのバケットが表示され、比較のためにEqualsを使用して、正しいThingyが検索されます。

これは辞書の場合ですか、それともハッシュコードが異なるが（ハッシュ％サイズ）が同じである衝突のみを解決しますか？これがうまくいかない場合は、どうすればよいですか？

4

3 に答える 3

27

ハッシュの衝突はパフォーマンスにのみ影響し、整合性には影響しません。

簡単なテストは、GetHashCode（）を変更して1;を返すようにすることです。辞書は引き続き適切に動作しますが、適切なデータセットを使用すると、ひどく機能します。

于 2010-02-10T20:52:39.070 に答える
19

ハッシュの衝突は主にパフォーマンスに影響しますが、正確さには影響しません。Equals()正しく動作する限り。

Dictionaryアイテムを個別の「バケット」に整理する方法としてハッシュコードを使用します。同じハッシュコードを共有するアイテムが多すぎると、パフォーマンスの問題が発生する可能性があります。Equals()ただし、インスタンスを正しく区別できる限り、正しい結果が得られるはずです。

ハッシュコードが問題を引き起こす可能性があるのは、可変オブジェクトの場合です。Thingyクラスでディクショナリ内のアイテムの変更が許可Fooまたは変更された場合Bar、その後のアクセス試行でそのアイテムを見つけることができない場合があります。これは、現在生成されるハッシュコードが、ディクショナリに値を格納するために使用されるものとは異なるためです。

于 2010-02-10T20:53:03.000 に答える
1

GetHashCodeは、衝突を最小限に抑える必要があるが排除する必要がないハッシュテーブルで使用するように設計されています。真に一意のキーを生成する必要がある場合、GetHashCodeは妥当な開始点です（GUIDほど長くはありません）が、オブジェクトの一部としてキーを保存し、使用されているキーのリストを個別に維持する必要があります。

辞書の内部から使用可能に見えるものを取得できる場合もありますが、おそらく確実に機能することはありません。たとえば、辞書が最初に処理に割り当てられたよりも多くのアイテムを追加すると、基になるデータ構造が再構築され、個別になります。アイテムは、辞書のまったく異なる部分に配置される可能性があります。

于 2010-02-11T00:50:58.640 に答える