O（1）内のHashSet <T>から等しいオブジェクトを取得します。

Question

A HashSet<T>は、O（1）に特定の項目が含まれているかどうかを判断できます。私は私のカスタムクラスのEquals()とGetHashCode()をオーバーライドする場合、私は、オブジェクトAを持つことができ、ある別のオブジェクトA」ではないアイデンティティによって等しいがため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); 

どのようにするには？

（thisは私が探している答えをしていない、とthisは全く答えを持っていないことに注意してください。）

---

いくつかの背景情報に：私はインターン自分へのセットを使用したいですオブジェクトはC＃のinterns文字列と同じ方法です。等しいオブジェクトは1つのインスタンスしか必要ありません。このようにして、私はそのようなオブジェクトにメタデータを追加し、そのメタデータなしで他の同等のインスタンスが存在しないことを確認できます。

Answer 1

HashSetには方法がありません。

代わりDictionaryを使用することができます。

var dict = new Dictionary<MyClass, MyClass>(); 
dict[a] = a; 
Debug.Assert(dict.ContainsKey(a_prime)); 
var retrieved_a = dict[a_prime]; 

Answer 2

私が正しくリコールHashSetがありながら、Dictionaryは、基本的な集合演算の時定数の実装を持っていません。これは、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() 
}