Why does the get method of HashMap have a FOR loop?

Question

I am looking at the source code for HashMap in Java 7, and I see that the put method will check if any entry is already present and if it is present then it will replace the old value with the new value.

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {         Object k;         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {             V oldValue = e.value;             e.value = value;             e.recordAccess(this);             return oldValue;         }     } 

So, basically it means that there would always be only one entry for the given key, I have seen this by debugging as well, but if I am wrong then please correct me.

Now, since there is only one entry for a given key, why does the get method have a FOR loop, since it could have simply returned the value directly?

    for (Entry<K,V> e = table[indexFor(hash, table.length)];          e != null;          e = e.next) {         Object k;         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))             return e.value;     } 

I feel the above loop is unnecessary. Please help me understand if I am wrong.

Answer 1

table[indexFor(hash, table.length)] is the bucket of the HashMap that may contain the key we are looking for (if it is present in the Map).

However, each bucket may contain multiple entries (either different keys having the same hashCode(), or different keys with different hashCode() that still got mapped to the same bucket), so you must iterate over these entries until you find the key you are looking for.

Since the expected number of entries in each bucket should be very small, this loop is still executed in expected O(1) time.

Answer 2

If you see the internal working of get method of HashMap.

public V get(Object key)  {         if (key == null)            return getForNullKey();          int hash = hash(key.hashCode());          for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next)           {              Object k;              if (e.hash == hash && ((k = e.key) == key || key.equals(k)))                  return e.value;          }              return null; } 

• First, it gets the hash code of the key object, which is passed, and finds the bucket location.
• If the correct bucket is found, it returns the value (e.value)
• If no match is found, it returns null.

Some times there may be chances of Hashcode collision and for solving this collision Hashmap uses equals() and then store that element into LinkedList in same bucket.

Lets take example:

Fetch the data for key vaibahv: map.get(new Key("vaibhav"));

Steps:

1. Calculate hash code of Key {“vaibhav”}.It will be generated as 118.

2. Calculate index by using index method it will be 6.

3. Go to index 6 of array and compare first element’s key with given key. If both are equals then return the value, otherwise check for next element if it exists.

4. In our case it is not found as first element and next of node object is not null.

5. If next of node is null then return null.

6. If next of node is not null traverse to the second element and repeat the process 3 until key is not found or next is not null.

For this retrieval process for loop will be used. For more reference you can refer this