7

AHashSet<T>は、特定のアイテムが含まれているかどうかを O(1) で判断できます。カスタム クラスでをオーバーライドするEquals()とGetHashCode()、オブジェクト A と別のオブジェクト A' を持つことができます。これらはID では等しくないが、同じハッシュ コードをEquals()返しtrueたり返したりします。GetHashCode()

ここで、A がハッシュ セットに含まれていることを考えると、A' (ハッシュ セットの観点からは A に等しい) を指定して、O(1) で A を取得したいと考えています。

var a = new MyClass("A");
var a_prime = new MyClass("A");
Debug.Assert(a.Equals(a_prime));
Debug.Assert(a.GetHashCode() == a_prime.GetHashCode());

var set = new HashSet<MyClass>();
set.Add(a);
Debug.Assert(set.Contains(a_prime));

// This:    
var retrieved_a = set.Get(a_prime);

これを行う方法？

（これには私が探している答えがなく、これにはまったく答えがないことに注意してください。）

背景情報: セットを使用して、C# が文字列をインターンするのと同じ方法で自分のオブジェクトをインターンしたい: 等しいオブジェクトにはインスタンスが 1 つだけ必要です。このようにして、そのようなオブジェクトにメタデータを追加し、そのメタデータを持たない同等のインスタンスが他に存在しないことを確認できます。

4

3 に答える 3

7

あなたが望むことをする方法はありHashSetません。

Dictionary代わりにa を使用できます。

var dict = new Dictionary<MyClass, MyClass>();
dict[a] = a;
Debug.Assert(dict.ContainsKey(a_prime));
var retrieved_a = dict[a_prime];
于 2012-06-06T23:07:17.103 に答える
1

私の記憶が正しければ、Dictionaryには基本集合操作の一定時間の実装はありませんが、ありHashSetます。これは、HashSet から他の複雑さを増やさずに、一定時間の等しいルックアップでそれを実装する方法です。多くのランダムな要素を取得する必要がある場合は、このアプローチを使用することが重要です。私は C# を知らないので、以下に Java 構文を書きますが、考え方は言語に依存しません。

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();

     //selects equal element in constant time
     A equalElement(A input) {
         return contents.get(indices.get(input));
     }

     //adds new element in constant time
     void add(A a) {
         indices.put(a,contents.size());
         contents.add(a);
     }

     //removes element in constant time
     void remove(A a) {
         int index = indices.get(a);
         contents.set(index,contents.get(contents.size()-1));
         contents.remove(contents.size()-1);
         indices.set(contents.get(contents.size()-1),index);
         indices.remove(a);
     }

     //all other operations (contains(), ...) are those from indices.keySet()
}
于 2012-09-13T22:22:12.757 に答える