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

Question

A HashSet<T> can determine in O (1) whether it contains a specific element. If I override Equals() and GetHashCode() in my custom class, I can have an object A and another object A 'that are not equal in identifier, 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 get A in O (1), given A '(which is equal to A in terms of the set of hashes).

 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 it?

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

---

Some background information: I want to use a set to put my own objects in the same way as C # inline lines: equal objects only need one instance. Thus, I can add metadata to such an object and be sure that there is no other equal instance anywhere without this metadata.

Answer 1

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

You can use 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 remember correctly, the Dictionary does not have constant realizations of the time of the main operations with the set, but a HashSet . Here is a way to implement it with constant constant search, without increasing other difficulties from HashSet. It is imperative to use this approach if you need to capture many random elements. I write Java syntax below 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() }