Get an equal object from HashSet<T> in O(1)

Question

A HashSet<T> can determine in O(1) whether it contains a certain item. If I override Equals() and GetHashCode() on my custom class, I can have an object A and another object A' that are not equal by identity but for which Equals() returns true and GetHashCode() returns the same hash code.

Now, given that A is in the hash set, I want to retrieve A in O(1) given A' (which is equal to A from the perspective of the 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);

How to do this?

(Note that this has not the answer I'm looking for, and this has no answers at all.)

---

Some background information: I want to use the set to intern my own objects the same way C# interns strings: equal objects need only one instance. This way I can append metadata to such an object and be sure that there is no other equal instance anywhere without that metadata.

Answer 1

There is no method on HashSet that does what you want.

You can use a Dictionary instead:

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

Answer 2

If I recall correctly, Dictionary does not have constant time implementations of the basic set operations, while HashSet has. Here is a way to implement it with constant time equal lookup, without increasing other complexities from HashSet. It is crucial to use this approach if you need to grab many random elements. What I write below is Java syntax, as I don't know C#, but the idea is language-independent.

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