Why PRESENT is a dummy value in map.put(e,PRESENT) in add method in HashSet?

Question

When we call

HashSet set = new HashSet();
set.add(1);

the add method will internally call the put method of map with value map.put(1,PRESENT);.

Why is PRESENT passed as a dummy value in map.put?

Unrelated: please read https://stackoverflow.com/questions/2770321/what-is-a-raw-type-and-why-shouldnt-we-use-it — GhostCat, Jul 05 '19 at 09:58

GhostCat · Accepted Answer · 2019-07-05T10:11:20.907

3

From a conceptual point, a Map represents a superset of a Set: it contains all the keys of a Set.

Thus, it is very well possible to implement a Set by re-using a Map. But of course a Map needs a key plus a value.

So: when you decide to implement a Set by re-using a Map, adding a key to the set results in adding a key plus a dummy value to that map. And it is useful to use a non-null value, so that you can later decide whether removing a specific key actually removed anything.

edited Jul 05 '19 at 10:11

answered Jul 05 '19 at 09:57

GhostCat

137,827
25
176
248

Same as for removing, you also get information when _adding_ about whether there was already a value there (without having to do `containsKey` first). `map.put(e, PRESENT)` will be `null` if not previously added (and so for a `Set`, the `add` succeeded), or `PRESENT` if it was previously added (and so the `add` failed). – BeUndead Jul 05 '19 at 11:19
Additionally, I assume using `key` would be a bad idea whenever someone chose to add a `null` element to the `HashSet`, falling into the same pitfalls already mentioned when using `null`. – BeUndead Jul 05 '19 at 11:20
@GhostCat I understood that it should be non-null value but why PRESENT is passed over there, keyword could be anything instead of PRESENT. – Dipen Khatri Jul 09 '19 at 10:20

score 0 · Answer 2 · answered Jul 05 '19 at 09:57

Because in the implementation of HashSet, a Map is used to remember which values the set contains. Or, to put it in other words, which value is present.

So in order to store the Set's values, each value is put into the Map as a key. Since the value behind the key does not matter, a dummy value is used. That dummy value is very simple and small in order to minimize memory footprint:

private static final Object PRESENT = new Object(); //from HashSet's sourcecode

score 0 · Answer 3 · answered Jul 05 '19 at 09:58

If you check the instantiation of a HashSet :

public HashSet() {
        map = new HashMap<>();
    }

It's represented as a hashmap, the values you add to the set are added as keys to the map with dummy object values, that's how HashSet avoids duplications

Why PRESENT is a dummy value in map.put(e,PRESENT) in add method in HashSet?

3 Answers3