1

私はハッシュテーブルの基本クラスを持っており、それから派生してさまざまなタイプのハッシュテーブルを作成しています。IHashableインターフェイスを実装するオブジェクトのみを受け入れることを許可します。たとえば、-

class LinearProbingHashTable<T> : HashTableBase<T> where T: IHashable
{
...
...
...
}

interface IHashable
{
    /**
     * Every IHashable implementation should provide an indentfying value for use in generating a hash key.
     */
    int getIdentifier();
}

class Car : IHashable
{
    public String Make { get; set; }
    public String Model { get; set; }
    public String Color { get; set; }
    public int Year { get; set; }

    public int getIdentifier()
    {
        /// ???
    }
}

ハッシュ関数が車をハッシュテーブルに配置するために使用できる車の識別子を生成するための良い方法を誰かが提案できますか？

私は実際に、特定のクラスのIDを生成するための汎用ソリューションを本当に探しています。IHashableとそのgetIdentifierメソッドを実装するすべてのクラスの基本クラスHashableObjectが必要です。したがって、インスタンスの識別子を自動的に提供するHashableObjectから派生することができます。つまり、ハッシュテーブルに追加するオブジェクトごとに異なるgetIdentifierメソッドを作成する必要はありません。

public class HashableObject : IHashable
{
  public int getIdentifier()
  {
    // Looking for code here that would generate an id for any object...
  }
}

public class Dog : HashableObject
{
  // Dont need to implement getIdentifier because the parent class does it for me
}
4

2 に答える 2

1

私は問題を2つに分けます：

  1. プリミティブ型のハッシュコードを生成する方法：文字列、整数など。
  2. 複数のハッシュコードを1つのハッシュコードに組み合わせる方法

（1）を使用してから（2）を使用すると、任意のクラスまたは構造のハッシュコードを生成できます。

文字列に対して（1）を行う単純な方法は、文字列内のすべての文字のコードを追加することです。

public static int getStringIdentifier(string str)
{
   int result = 0;
   foreach (char c in str) {
     result += (int)c;
   }
   return result;
}

同様の単純なアルゴリズムを他の基本的なデータ型（最終的にはすべてバイトの配列）に使用できます。

（2）を行うための素朴な方法は、さまざまなハッシュコードをXORと単純に組み合わせる方法です。

public int getIdentifier() 
{ 
  return getStringIdentifier(Make) ^ getStringIdentifier(Model) ^ getStringIdentifier(Color);     
}

これらのアルゴリズムは機能しますが、ハッシュコード値の適切な分布を生成しません。つまり、衝突が発生します。

より優れたアルゴリズムが必要な場合は、.NET Frameworkがどのように機能するかを確認できます。これは、複数のハッシュコードを組み合わせるために頻繁に使用されるクラスのソースコードです。クラスのソースコードは、を含みます。StringString.GetHashCode()

ご覧のとおり、これらは上記のナイーブなもののバリエーションであり、開始値が異なり、より複雑な組み合わせになっています。

異なるクラスで機能する単一のメソッドが必要な場合は、リフレクションを使用してクラスに含まれるすべてのプリミティブフィールドを検出し、プリミティブ関数を使用してハッシュコードを計算してから、それらを結合します。getIdentifier()ただし、これはトリッキーで非常に.NET固有です。私の好みは、プリミティブ型を処理するメソッドを作成してから、クラスごとに再定義することです。

于 2012-10-03T19:38:02.680 に答える
1

デフォルトのGetHashCode方法を使用する必要があります。それはあなたが必要とするすべてをします。ドキュメント。これはすべてのオブジェクトに存在し、仮想であるため、必要に応じてオーバーライドすることを選択できます。

プリミティブデータ型（int、float、strings、非拡張オブジェクト、その他いくつか）のハッシュを生成し、複数のハッシュを組み合わせる方法を知っていると思いますので、詳細については説明しません。

どうしても独自の汎用ハッシュ関数を作成する必要がある場合は、Reflectionを使用できます。これらのケースを手動で処理する必要があるプリミティブ型に到達するまで、各データメンバーを再帰的にハッシュします。管理されていないデータを持つ特定のデータ型で問題が発生する可能性があります。特に、1つの例は、データ構造が指定されていないクラスへのポインターを持つ.netクラスです。リフレクションは明らかにこのケースを処理できず、クラスの管理されていない部分をハッシュすることはできません。

于 2012-10-03T18:43:15.157 に答える