I have been reading/researching the reason why HashMap
is faster than HashSet
.
I am not quite understanding the following statements:
HashMap
is faster than HashSet
because the values are associated to a unique key.
In HashSet
, member object is used for calculating hashcode value which can be same for two objects so equals()
method is used to check for equality. If it returns false
, that means the two objects are different. In HashMap
, the hashcode value is calculated using the key object.
The HashMap
hashcode value is calculated using the key object. Here, the member object is used to calculate the hashcode, which can be the same for two objects, so equals()
method is used to check for equality. If it returns false
, that means the two objects are different.
To conclude my question:
I thought HashMap
and HashSet
calculate the hashcode in the same way. Why are they different?
Can you provide a concrete example how HashSet
and HashMap
calculating the hashcode differently?
I know what a "key object" is, but what does it mean by "member object"?
HashMap
can do the same things as HashSet
, and faster. Why do we need HashSet
? Example:
HashMap <Object1, Boolean>= new HashMap<Object1, boolean>();
map.put("obj1",true); => exist
map.get("obj1"); =>if null = not exist, else exist
Hashmaps use the hashcode of the key to access directly the bucket where the entry is stored. This is an O(1) access. If more than one element is in that bucket because of the same or similar hashcode, then you have a few more checks, but it's still way faster than iterating through a list and searching for an element.
HashMap, being a hashtable-based implementation, internally uses an array-based data structure to organize its elements according to the hash function. HashMap provides expected constant-time performance O(1) for most operations like add(), remove() and contains(). Therefore, it's significantly faster than a TreeMap.
HashMap is faster than HashSet because the values are associated to a unique key. In HashSet , member object is used for calculating hashcode value which can be same for two objects so equals() method is used to check for equality. If it returns false , that means the two objects are different.
HashMap allows duplicate values but does not allow duplicate keys. The ArrayList always gives O(1) performance in best case or worst-case time complexity. The HashMap get() method has O(1) time complexity in the best case and O(n) time complexity in worst case.
Performance:
If you look at the source code of HashSet (at least JDK 6, 7 and 8), it uses HashMap internally, so it basically does exactly what you are doing with sample code.
So, if you need a Set implementation, you use HashSet, if you need a Map - HashMap. Code using HashMap instead of HashSet will have exactly the same performance as using HashSet directly.
Choosing the right collection
Map - maps keys to values (associative array) - http://en.wikipedia.org/wiki/Associative_array.
Set - a collection that contains no duplicate elements - http://en.wikipedia.org/wiki/Set_(computer_science).
If the only thing you need your collection for is to check if an element is present in there - use Set. Your code will be cleaner and more understandable to others.
If you need to store some data for your elements - use Map.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With