HomeTagSubmit NotesAsk AnythingLoginSubscribe Us
1. Feel Free to ask and submit anything on and get satisfactory answer
2. Registration is not compulsory, you can directly login via google or facebook
3. Our Experts are looking for yours ?.

corejava-collection: How HashMap works internally?

Please explain the internal working principle of HashMap.

corejava x 353
collection x 52
Posted On : 2014-04-14 22:29:00.0
profile Garima Gupta - Garima Gupta


HashMap works internally on the principal of "Hashing". Let´s focus upon Hashing principle.

Hashing is a way to assign an unique code for any variable/object after applying any formula/algorithm on its properties. A Hashing function should follow the following rule:
"Hash function should return the same hash code at each and every time, whenever function is applied on same or equal objects. In other words, two equal objects must produce same hash code consistently."

Note: All objects in java inherit a default implementation of hashCode() function defined in Object class. This function produce hash code by typically converting the internal address of the object into an integer, thus producing different hash codes for all different objects.

HashMap is an array of Entry objects:
Assume HashMap as just an array of objects.

Let´s have a look what this Object is:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;

Each Entry object represents key-value pair. Field next refers to other Entry object if a bucket has more than 1 Entry.

Sometimes it might happen that hashCodes for 2 different objects are the same. In this case two objects will be saved in one bucket and can be presented as LinkedList. The entry point is most recently added object. This object refers to other object with next field and so on. Last entry refers to null.

Creating HashMap with default constructor: HashMap hashMap = new HashMap();

Adding a new key-value pair:
Calculate hashcode for the key-
Calculate position hash % (arrayLength-1)) where element should be placed(bucket number)
If you are trying to add a value with a key which has already been saved in HashMap, then value gets overwritten.
Otherwise element is added to the bucket. If bucket has already at least one element - a newer one gets added and placed in the first position in the bucket. Its next field refers to the old element.

Calculate hashcode for the given key
Calculate bucket number (hash % (arrayLength-1))
Get a reference to the first Entry object in the bucket and by means of equals method iterate over all entries in the given bucket. Eventually we will find correct Entry. If desired element is not found - return null

Posted On : 2014-04-14 23:32:20
Satisfied : 6 Yes  0 No
profile Saksham Kumar - Saksham Kumar
Reply This Thread

Post Answer
Please Login First to Post Answer: Login login with facebook -