Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why the internal implementation of HashSet creates dummy objects to insert as values in HashMap rather than inserting nulls?

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?

like image 333
sahil bansal Avatar asked May 04 '15 18:05

sahil bansal


People also ask

What is dummy values in HashSet?

2. Dummy value : There is no concept of dummy value in HashMap . HashSet internally uses HashMap to add elements. In HashSet , the argument passed in add(Object) method serves as key K . we need to associate dummy value (automatically created by jdk) for each value passed in add(Object) method.

What does HashSet internally uses in its implementation?

HashSet internally uses HashMap to store the elements. When we insert an element to it using the add() method, the element is internally stored in a HashMap. For example, when we add 5 to HashSet via hashSet. add(5), it will be internally stored in HashMap via map.

Does HashSet uses HashMap for its implementation?

Hashset internally uses Hashmap for its implementation. HashMap Stores elements in form of key-value pair i.e each element has its corresponding key which is required for its retrieval during iteration. HashSet stores only objects no such key value pairs maintained.

How are HashMap and HashSet implemented internally?

When we create an object of HashSet, it internally creates an instance of HashMap with default initial capacity 16. HashSet uses a constructor HashSet(int capacity) that represents how many elements can be stored in the HashSet. The capacity may increase automatically when more elements to be store.


1 Answers

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.

like image 115
rgettman Avatar answered Oct 12 '22 23:10

rgettman