Why do Set data structures in Java use Map internally?

Question

I am wondering why do HashSet uses HashMap, TreeSet uses TreeMap, and LinkedHashSet uses LinkedHashMap internally behind the scene ? since Set is only carrying and storing the key but the value, so isn't using extra memory space like being not economical ?

The Entry inner class that HashMap has is the following

class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 final int hash;
 ...
 ....
}

For Set we don't really need that V value variable, correct ? So what's the benefit and main reason of using a map object internally ?

Answer 1

Less code, less bugs, less testing.

By reusing the same code, you only need to optimize, debug and test it once. The memory overhead is minimal - another pointer for each entry, negligible compared to the Key.

• peter: so can we really say Set = Map in Java ?
• zmbq: Well, no, a Set is a set of elements, while a map maps keys to values. It's not the same thing at all.
• Peter: You could say that a Set is a Map keyed by just the value itself rather than by a separate key; or at least that appears to be how it has been implemented.
• zmbq: Guys, the interface a Set provides is nothing like the interface a Map provides. The fact that a Set is implemented with a Map is really just a technicality.
• peter: I am wondering are there any other significant differences between Set and Map except that value variable ?

Answer 2

Using a Map simplifies the code, but increases the memory usage slightly. It's not as much as you might think as the overhead is already high. ;)

Not all Maps have Sets and you can use the following.

Set<T> set = Collection.newSetFromMap(new ConcurrentHashMap<T>());
Set<T> set = Collection.newSetFromMap(new ConcurrentSkipListMap<T>());
Set<T> set = Collection.newSetFromMap(new IdentityHashMap<T>());

• Louis Wasserman: Actually, I think that due to alignment issues, the memory usage is exactly the same at least on 32-bit JVMs.
• Peter Lawrey: I suspect the same, but it would means on the 64-bit JVM you have an extra 8 bytes per element.
• maaartinus: @Peter Lawrey: Can you explain why? With all other things the same, the 64-bit JVM rounds up to a multiple of 8 bytes rather than of 4 bytes, so it increase the overhead, but only of there's any on the 32-bit machine.
• Peter Lawrey: This depends on the implementation but the Sun/Oracle JVMs both have an 8 byte boundary. In a 32-bit JVM you have a 8 byte header and on a 64-bit JVM you have a 12 byte header. When you have an Entry with two 32-bit references the total size is 8+2*4 or 16 bytes on the 32-bit JVM and 12 +2*4 + 4 padding = 24 bytes on the 64-bit JVM. i.e. the references are the same size but the object overhead is different.