Get an equal object from HashSet 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.

possible duplicate of [How to retrieve actual item from HashSet?](http://stackoverflow.com/questions/7760364/how-to-retrieve-actual-item-from-hashsett) — nawfal, May 26 '14 at 10:11
Another [how-to-access-the-reference-values-of-a-hashset-without-enumeration?](http://stackoverflow.com/questions/7290443/how-to-access-the-reference-values-of-a-hashsettvalue-without-enumeration?) — nawfal, May 26 '14 at 10:39

score 7 · Accepted Answer · answered Jun 06 '12 at 23:07

7

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

answered Jun 06 '12 at 23:07

Mark Byers

811,555
193
1,581
1,452

I've always avoided making dicts that maps to themselves. Is this bad practice? Or am I just worrying about nothing? – Hans Z Jun 06 '12 at 23:30
@Hans As always, that depends. Why do you think it's a bad practice? Why do you avoid them? – svick Jun 06 '12 at 23:33
3

@svick I don't know, it just seems strange to me. I guess I don't have any concrete reasons for avoiding it, but I've never had to use a construct like that, but for some reason looking at `dict[a] = a;` makes me cringe. – Hans Z Jun 06 '12 at 23:37
1

It makes me cringe as well. If nothing else, it has an obvious redundancy. Probably not worth fixing unless you hit a performance issue, though. – Brian Jun 07 '12 at 20:00

user1111929 · Answer 2 · 2012-12-08T00:38:23.527

1

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

edited Dec 08 '12 at 00:38

answered Sep 13 '12 at 22:22

user1111929

6,050
9
43
73

Sorry, the random was a typo, I meant equal instead of random. I have corrected the method now. Basically, instead of using a HashSet, I use a HashMap *and* an ArrayList, containing the same elements and with the HashMap pointing to the indices of that element in the ArrayList. Instead of the simple "Yes I already have this key" from the HashSet, the HashMap says "Yes I already have this key and it points to the integer `i`". Then in the ArrayList you can fetch your object by taking the object at position `i`. – user1111929 Dec 08 '12 at 00:35
Thanks for the corrections! Now it is much more relevant! As a side note, still I'd be very careful about that "constant time" claim. I don't think that HashMaps have guaranteeded worst-case-O(1) fetch time, I think it is average-O(1), and you can get much worse if you, for example, evilishly tinker with GetHashCode of the keys of the map. Anyways, removed -1 and the previous comment, as it doesn't match the post as it is now. – quetzalcoatl Dec 08 '12 at 19:53
You are right, with "constant time" I meant "average time: constant". – user1111929 Dec 10 '12 at 16:40
This is brilliant, +1. Though the performance-ist in me would implement this as `HashMap` and implement set operations manually. – nawfal May 26 '14 at 10:09
A small correction I think: You cant do `contents.get(contents.size()-1)` after you remove the item from `contents`. It will give you the wrong item. It should be `indices.set(contents.get(contents.size()-1),index);` before `contents.remove(contents.size()-1);` – nawfal May 26 '14 at 10:13

score 0 · Answer 3 · answered Dec 09 '20 at 14:56

0

Use HashSet.TryGetValue. (Available starting from .NET Framework 4.7.2.)

answered Dec 09 '20 at 14:56

Mike Rosoft

628
7
10

Get an equal object from HashSet in O(1)

3 Answers3