How does Hashing work for HashSet?

Question

I have just read and understood how hashing works with HashMap: how it uses a hashtable, makes hashcodes with a hash function etc.

My question is: If the same principles apply to HashSet? Well obviously it cannot compute a hashcode from HashSet's key, because it doesn't have one. But does it compute the hashcode from the value of the HashSet then?

It computes the hash from the image currently on the PC's camera. Just kidding, it uses the value. — Tyler Durden, Jun 19 '13 at 19:31

arshajii · Accepted Answer · 2013-06-19T20:00:52.397

8

Actually, a HashSet is backed by HashMap that maps all its keys to a single constant object. The key-set of this map acts as the set. See for yourself by looking at the HashSet source. So yes, the mechanisms by which the two operate are very similar.

edited Jun 19 '13 at 20:00

answered Jun 19 '13 at 19:31

arshajii

127,459
24
238
287

6

And this can apply to absolutely any map. In fact, Java has the library method [`Collections.newSetFromMap`](http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#newSetFromMap(java.util.Map)) which can take any `Map` and create a `Set` from it. That way you can get, for example, a [concurrent hash set even though Java doesn't include ConcurrentHashSet](http://stackoverflow.com/questions/6992608/why-there-is-no-concurrenthashset-against-concurrenthashmap). The `Set` ends up exhibiting the same semantics and performance characteristics as the backing `Map`. – Mark Peters Jun 19 '13 at 19:35

score 2 · Answer 2 · answered Jul 04 '20 at 13:55

HashSet uses HashMap internally to store it’s objects. Whenever you create a HashSet object, one HashMap object associated with it is also created. This HashMap object is used to store the elements you enter in the HashSet. The elements you add into HashSet are stored as keys of this HashMap object. The value associated with those keys will be a constant. Whenever you insert an element into HashSet using add() method, it actually creates an entry in the internally backing HashMap object with element you have specified as it’s key and constant called “PRESENT” as it’s value. This “PRESENT” is defined in the HashSet class as below.

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e)
{
        return map.put(e, PRESENT)==null;
}

You can notice that, add() method of HashSet class internally calls put() method of backing HashMap object by passing the element you have specified as a key and constant “PRESENT” as it’s value.

Sergey Kalinichenko · Answer 3 · 2013-06-19T19:37:23.937

1

Iс the same principles for HashSet's?

Yes, HashSet uses the same exact general principle: the keys inserted into the set are arranged according to their hash codes, using the equals method to resolve collisions.

Obviously, it cannot compute a hashcode from HashSet's key, because it doesn't have one

Of course it has, and it can! In fact, hash keys is all the HashSet has -- just keys, no values.

In a HashMap the "value" is passive: that's something stored at the key; hash maps never look at values; in particular, maps never check values for equality, or compute their hash code. You can think of a hash set as a hash map that maps everything to null.

edited Jun 19 '13 at 19:37

answered Jun 19 '13 at 19:30

Sergey Kalinichenko

714,442
84
1,110
1,523

3

...or to a constant, which would be more than just thinking, it would be how it actually is :) – Marko Topolnik Jun 19 '13 at 19:33
@MarkoTopolnik That's a minor implementation detail. Big picture is that sets are "mapping something to nothing", or at least "nothing that would be of particular interest". – Sergey Kalinichenko Jun 19 '13 at 19:35
Yes, it is, but still it is satisfying to know how it actually is, especially since your argument would be as clear. – Marko Topolnik Jun 19 '13 at 19:36
@MarkoTopolnik actually, it would be much less clear. Novice programmers understand the concept of a object being `null` far better than they would understand some bla about 'arbitrary objects'. – AJMansfield Jun 19 '13 at 19:38
3

@AJMansfield That's just your opinion. I've never witnessed anything similar. What I *have* witnessed is the power of concretness and specificity. "It is precisely like this" has far better educational value than "you can imagine it's something like this". – Marko Topolnik Jun 19 '13 at 19:39

How does Hashing work for HashSet?

3 Answers3