Null Object in HashSet implementation

Question

In the Java API, the implementation of HashSet is using an Object as a value for the inside HashMap,

   // 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;
}

but HashMap allows its value is null. I think that's not necessary to fill the value, so why is this needed?

Answer 1

Because the HashSet contract specifies that remove() return true if the specified object existed and was removed. To do this, it uses the wrapped HashMap#remove() which returns the removed value.

If you were to store null instead of an object, then the call to HashMap#remove() would return null, which would be indistinguishable from the result of attempting to remove a non-existent object, and the contract of HashSet.remove() could not be fulfilled.

Answer 2

but HashMap allows its value is null

Why would that matter, when the value is entirely controlled by HashSet? That ensures that the only value ever associated with a key is PRESENT. So if map.put returns null, that could only be because there was previously no entry for that key.

The value is just there because some value has to be specified, and if the value were specified as null, that would be bad - it would make it harder to tell whether there was a value before the call to add. If you're going to specify any non-null value, you might as well force it to be the same value all the time - you wouldn't want it to hold up garbage collection, for example.

Now if you're asking why HashSet is implemented in terms of HashMap rather than being a more efficient implementation which doesn't record a value at all, that's a different question, and one I don't have an answer to.