Why is Set at all required when we have Maps?

Question

Sets are essentially Maps from an existential point of view. There is nothing a Map can not do which a Set can, I assume. We have these overheads of defining key-value pairs in Maps which is not there in the Sets. But again the elements of a Set are just the keys of the underlying Map, right? So what is the point of having Sets around when Maps are able to do all the things required? I hope a Set takes the same amount of memory as a Map does?

What are key arguments in favor of existence of Sets?

For instance, in the case of Lists, we have ArrayList and LinkedList which have differences and we can choose between these two as per our requirements.

Answer 1

I would argue that a Map is actually a Set!

Map<Key,Value> can be implemented with Set<Entry<Key,Value>>

This is similar to the mathematical foundations of what sets, maps, and functions are.

Firstly, can we agree that a Map is a function from Key=>Value (or Domain=>Range). Each key corresponds with at most one value, so it is a partial function (or a complete function only upon those keys in the map). So a map is a function. (Scala even goes so far as to have Map implement the Function1 interface.)

Secondly, what is a function? A function is a set of tuples where each first element occurs only once in the set. The second element of the tuple is the value returned by the function.

So we have Map is a Function is a Set.

---

On a practical note, there are very good reasons for having Sets. They are very often the correct data structure to use from a conceptual point of view, even before you start worrying about performance. I'd use them over a List in most situations.

Answer 2

The primary difference between a Set and a Map is that a Map holds two object per Entry e.g. key and value and it may contain duplicate values but keys are always unique. But Set holds only keys and those are unique.