aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes HashSet internal working Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "HashSet internal working" Watch "HashSet internal working" New topic
Author

HashSet internal working

Deepak Jain
Ranch Hand

Joined: Aug 05, 2006
Posts: 637
HashSet:This class implements the Set interface, backed by a hash table (actually a HashMap instance).

While adding elements into HashSet i never specify the key and offcourse it does not make sense to specify the key since its a set. I am wondering since the HashSet is implemented via a HashMap instance , what would be the key that would be used to put data into HashSet.

The answer is they key is a the value that is passed into the the hashset. For example
HashSet<String> names = new HashSet<String>();
names.add("Deepak");

Internally since the HashSet is implemented by a HashMap instance , and HashMap requires a key and value. So here the key = "Deepak" and value = "new Object()". The Value is a dummy object.Which is infact a static constant so that each add operation does not create a dummy instances of Object.
Hence names.add("Deepak");
gets converted to
internalHashMap.put("Deepak",object);
Here object defined as
private static final Object object = new Object();

I had this doubt but after reading a bit i got the solution as well. Hence i thought i would post it.


SCJP, SCWCD, SCBCD
siraj siddiqui
Greenhorn

Joined: Dec 05, 2008
Posts: 11
HashSet uses HashMap internally to store objects.
you are saying

HashSet<String> names = new HashSet<String>();
names.add("Deepak");

when you add object("Deepak") internall it is stored in HashMap where
key is "Deepak" & value is dummy object
But when you iterate through Hashset means internally you are iterating thtough HashMap.In HashMap key is "Deepak" & value is dummy object, so it should return dummy object rather than key i.e. "Deepak" . So you are getting dummy object out of the HashSet not orignal object ("Deepak").

I am not getting your point ,Will you explain please?
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9303
    
  17

First of all Deepak thanks for sharing the info. I used to think that the hasMap contains the hash values as the keys and the actual object that we put in the hasSet as the values to the keys.

Siraj when you iterate over the internal HashMap, the iteration will be over the keySet of the hashMap. As you know that you can call keySet on a map to get the keys as a set of values. So this must be the internal implementation although I am not sure...


SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Deepak Jain
Ranch Hand

Joined: Aug 05, 2006
Posts: 637
Good question.
As you know to get the data from the HashSet you would need to use the iterator.
HashSet<String> hashSet = new HashSet<String>();
hashSet.add("Test");
hashSet.add("Test1");
hashSet.add("Test2");

Hence when you use iterator as follows
Iterator<String> iter = hashSet.iterator();
Here hashSet.iteator() would return you the iterator of the Keys and not the values as shown below
internalHashMap.keySet().iterator();

And hence when you iterate over an HashSet you would see the data that you entered which are infact the keys into HashMap and not the dummy object.

Hope this clears
siraj siddiqui
Greenhorn

Joined: Dec 05, 2008
Posts: 11
Deepak & Ankit thanks for the information. But i still have a doubt.
Will you explain,
Why HashMap do not use the hashcode value as a key and actual object as a value.
Deepak Jain
Ranch Hand

Joined: Aug 05, 2006
Posts: 637
I think its just a matter of implementation
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
Great Information :

Here is the internal HashMap

private transient HashMap<E,Object> map;


and here is the Dummy Object that is static final.

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

this is the no-arg constructor
public HashSet() {
map = new HashMap<E,Object>();
}
HashMap default capacity is 16.



public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}


public void clear() {
map.clear();
}


SCJP 6
Navnish Agarwal
Greenhorn

Joined: Feb 10, 2014
Posts: 3
Here is the best explanation of how hash set works in java

http://javahungry.blogspot.com/2013/08/how-sets-are-implemented-internally-in.html

I think it almost resembles the same as mentioned above in the forum , but the examples explained in the shared link made it much easy for the reader to understand .
 
wood burning stoves
 
subject: HashSet internal working