How HashSet works?

Well earlier i wasnt sure how HashSet is created internally and which data structure is used. But when I looked at the class implemenation i was surprised because of following features i noticed:

Hashset is used to store the unique elements, in which their is no gurantee of the iteration order.

Hashset internally use HashMap .

Elements passed to Hashset are stored as a key of the HashMap with null as value. Since the objects passed to set are key so no extra check is done to identify duplicates. For eg after adding integer 1 and 2 if i add 1 again, no check is performed to identify whether 1 is present or not. The hashset simply performs the put with the same value( ‘1’) in this case as key.

Similariy when an element is removed from the Set the internal HashMap remove method is called.

So HashSet data structure is nothing but a HashMap with objects as key.

HashSet Implemenation from java.util package

  1. public HashSet() {
     map = new HashMap<E,Object>();
  2.    public boolean add(E o) {
     return map.put(o, PRESENT)==null;
  3.     /**
         * Removes the specified element from this set if it is present.
         * @param o object to be removed from this set, if present.
         * @return <tt>true</tt> if the set contained the specified element.
        public boolean remove(Object o) {
     return map.remove(o)==PRESENT;