3

任意の数のデータ フィールドを取得し、それらを何らかの方法で組み合わせてハッシュ可能なオブジェクトにし、後でこのオブジェクトを辞書でハッシュして後で検索できるようにする必要があるメソッドを作成しました。

これまでのところ、私が思いついた最良のアルゴリズムは、各フィールドに ToHashCode() を使用し、結果のハッシュコードをある種の区切り文字 (「|」など) を使用して文字列に結合し、この結果の文字列を次のように使用することです。ディクショナリの一意のキー。

これを行うためのより効率的な方法を知っている人はいますか? 各フィールドのハッシュコードを取得し、それらを一意のハッシュ可能な数値に結合するために何らかの数学演算を行う方法があるのではないかと考えていましたが、これは単なる推測にすぎません。

助けてくれてありがとう。

編集: 私が正確に何を意味するかについて、人々は混乱するかもしれないと思います. タプルはこの状況では機能しません。これは、任意の数のフィールドを 1 つのハッシュ可能なオブジェクトに結合する必要があるためです。フィールドの数は、設計時ではなく、実行時にのみわかります。

辞書へのキーとして使用できるオブジェクトが必要なため、すべてのハッシュコードを数学的に新しいハッシュコードに結合するという他の解決策も機能しません。Dictionary のキーとしてハッシュコードを使用することは非常に危険だと思います。

編集2:これについてもう少し考えた後、私の元の解決策は良いものではないと思います。単一のフィールドがある限定的なケースでは、私のソリューションは、ハッシュコードの文字列バージョンを辞書に入れることに退化しました。

おそらくより良い解決策は、コンストラクターで列挙型を取り、GetHashCode() を実装する新しい型を作成することだと思います。GetHashCode() 関数は、列挙可能な各値をループし、ハッシュ コード関数で通常のタイプのアキュムレータ ロジックを実行します。このようにして、オブジェクトは辞書やハッシュセットなどにスタックされ、期待どおりに動作します。

4

4 に答える 4

1

ここで重要なのは、任意のサイズのオブジェクトのコレクションをハッシュコードが列挙の内容に依存する IEnumerable として扱うだけでハッシュできることを認識することでした。

これを行うには、IEnumerable を実装する ValueAwareEnumerable クラスを作成するだけです。このクラスは、唯一のコンストラクターで列挙型を取ります。次に、GetHashCode() と Equals() をオーバーライドして、enumerable の内容に依存するようにします。GetHashCode メソッドは単純です。

public override int GetHashCode()
{
    unchecked
    {
        int hash = 983;
        foreach (var item in _wrappedEnumerable)
           if(item != null)
              hash = hash * 457 + item.GetHashCode();
        return hash;
    }
}

および等しい:

 public override bool Equals(object obj)
 {
     if (ReferenceEquals(null, obj)) return false;
     if (ReferenceEquals(this, obj)) return true;
     if (obj.GetType() != typeof (ValueAwareEnumerable<T>)) return false;
     return Equals((ValueAwareEnumerable<T>) obj);
 }

 public bool Equals(ValueAwareEnumerable<T> other)
 {
     if (ReferenceEquals(null, other)) return false;
     if (ReferenceEquals(this, other)) return true;

     return _wrappedEnumerable.SequenceEqual(other);                               
 }

ここでの注意点は、列挙可能な順序に依存することです。必要に応じて、反復する前に GetHashCode() と Equals() で列挙型をソートするだけで、順序に依存しないようにすることができます。

最後に、拡張メソッドを適切な場所に追加するだけです。

public static IEnumerable<T> ToValueAwareEnumerable<T>(this IEnumerable<T> enumerable)
{
   return new ValueAwareEnumerable<T>(enumerable);
}

次のようなことができます。

var dictionary = new Dictionary<IEnumerable<int>>();
var veryImportantNumbers = new[] { 5, 8, 13, 20, 3, 100, 55, -5, 0 };
dictionary[veryImportantNumbers.ToValueAwareEnumerable()] = "Pastrami";

これは、データ型をIEnumerable<Object>.

于 2012-04-27T17:37:57.353 に答える
1

最も簡単な方法は、 Tuple<> を使用してフィールドのハッシュコードを結合することです。

var dict = new Dictionary<Tuple<int, string>, MyClass>();
dict[Tuple.Create(myObj.Num, myObj.Str)] = myObj;

ハッシュを自分で組み合わせることもできますが、間違えるリスクがあります。

于 2012-04-13T19:13:38.007 に答える
0

各フィールドのハッシュコードを取得し、それらを一意のハッシュ可能な数値に結合するために何らかの数学演算を行う方法があるのではないかと考えていましたが、これは単なる推測にすぎません。

はい、それはまさにあなたがすべきことです。一般的な実装は次のとおりです。

unchecked
{
    int hash = 983;
    hash = hash * 457 + x.GetHashCode();
    hash = hash * 457 + y.GetHashCode();
    hash = hash * 457 + (z != null ? z.GetHashCode() : 0);
    return hash;
}

ハッシュコードは一意ではないため、辞書のキーとして使用することは想定されていないことに注意してください(通常、衝突はまれですが、不可能ではありません)。Equalsオブジェクト自体をキーとして使用する場合は、 if x.Equals(y), thenのようにオーバーライドする必要がありますx.GetHashCode() == y.GetHashCode()(逆は true である必要はありません)。

于 2012-04-13T19:15:49.237 に答える
0

この場合、標準の has テーブルを安全に使用することはできません (追加の制限を提供できない限り)。

適切な代替案を提供するには追加情報が必要ですが、以下に 1 つの提案があります。追加情報には次のものが含まれる場合があります。

  • ユース ケース (ルックアップ システムの使用方法、キーのフィールド部分が必要な理由)
  • 設計時に定義された結合可能なフィールドです (注: これは、結合されるフィールドの数や結合されるフィールドではありません。代わりに、結合できるようにこれらのフィールドがどこで、いつ、どのように定義されるかに関連しています)。
  • フィールドが実行時に定義されている場合、フィールドの合計数 (すべてのフィールドの数)。
  • この奇妙な鍵にはどのようなデータが保存されていますか?
  • データはどのくらいの頻度で読み書きされますか?

簡単な解決策:
ネストされたハッシュ テーブルを使用します。このソリューションでは、フィールドをソートする必要があります。最初のフィールドは、最初のテーブルのキーです。これは、2 番目のフィールドがキーになる別のハッシュ テーブルを指します。これは、最後のフィールドまで各フィールドで発生します。最後のフィールドは、探しているデータのキーになります。
これを機能させるには、データのプロパティとハッシュ テーブルのプロパティを持つカスタム オブジェクトを定義する必要があります。

これは既存の .net データ構造を使用する適切なソリューションですが、あまり効率的ではありません。より効率的なソリューションについては、追加情報を提供してください。

于 2012-04-13T20:29:37.470 に答える