Ottenere un oggetto uguale da HashSet <T> in O (1)

Question

A HashSet<T> può determinare in O (1) se contiene un determinato elemento. Se sovrascrivo Equals() e GetHashCode() sulla mia classe personalizzata, posso avere un oggetto A e un altro oggetto A' che sono non uguale per identità, ma per i quali Equals() rendimenti true e GetHashCode() restituisce lo stesso codice hash.

Ora, dato che A è nel set di hash, voglio recuperare A in O (1) dato A '(che è uguale ad A dal punto di vista dell'hash set).

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); 

Come fare?

(Si noti che this non ha la risposta che sto cercando, e this non ha risposte a tutti.)

---

Alcune informazioni di base: Voglio utilizzare il set per stagista mia oggetti allo stesso modo C# interns stringhe: gli oggetti uguali hanno bisogno di una sola istanza. In questo modo posso aggiungere i metadati a un tale oggetto ed essere sicuro che non ci siano altre istanze uguali ovunque senza i metadati.

Answer 1

Non esiste alcun metodo su HashSet che fa ciò che si desidera.

È possibile utilizzare un Dictionary invece:

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

Answer 2

Se ricordo bene, Dictionary non avere implementazioni di tempo costanti delle operazioni di set di base, mentre HashSet ha. Ecco un modo per implementarlo con una costante ricerca di uguale tempo, senza aumentare le altre complessità da HashSet. È fondamentale utilizzare questo approccio se è necessario acquisire molti elementi casuali. Quello che scrivo qui sotto è la sintassi Java, in quanto non conosco C#, ma l'idea è indipendente dalla lingua.

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() 
}