HashSet is implemented using HashMap and when we add anything say e1 to HashSet, internally it adds (e1,new Object()) in the HashMap if e1 was not present in the set. My question is why they are inserting new Object(), when they could have inserted like (e1,null), which is more optimized approach as no new Objects are created. Is there any downside to inserting nulls here?
A HashSet doesn't add a new Object each time a new key is put into the map. It does use an Object, but it uses the same Object each time. This value is named PRESENT in the HashSet source code.
The add method calls put(key, PRESENT) on the internal HashMap. The remove method calls remove(key) on the internal HashMap, but it must return a boolean indicating whether the key was present. If null were stored as the value, then the HashSet would need to call containsKey first, then remove, to determine if the key was present -- additional overhead. Here, there is only the memory overhead of one Object, which is quite minimal.