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;
        }
Advertisements

One thought on “How HashSet works?

  1. Hi There,

    Allow me to show my gratitude bloggers. You guys are like unicorns. Never seen but always spreading magic. Your content is yummy. So satisfied.

    I mainly would like to know is a int[4][4] or a int [4*4] is more efficient to use. Which takes more storage? Which requires more to process? that kind of stuff. Any answer or links to reading material that might help would be appreciated.


    It was cool to see your article pop up in my google search for the process yesterday. Great Guide.
    Keep up the good work!

    Thanks a heaps,

    Irene Hynes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s