CODEWITHSUNDEEP
javahashmap
JavaDeveloper
JavaDeveloper

Reputation: 5660

A loop in HashMap.get

This is a code to fetch a value from a key in HashMap. Why does it need to loop on line 317 to fetch the value ? Should this not be an O(1) operation ? 

  public V get(Object key) {
  315           if (key == null)
  316               return getForNullKey();
  317           int hash = hash(key.hashCode());
  318           for (Entry<K,V> e = table[indexFor(hash, table.length)];
  319                e != null;
  320                e = e.next) {
  321               Object k;
  322               if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  323                   return e.value;
  324           }
  325           return null;
  326       }

Upvotes: 0

Views: 565

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

The part that's O(1) is here:

table[indexFor(hash, table.length)]

Finding the list to iterate is exactly O(1). If the hash function is good, most lists that you iterate have length of only a few items. On the average, the search would stop after a small number of iterations that does not depend on the total number of hashed items. This gives you amortized access time O(1).

Upvotes: 3

SJuan76
SJuan76

Reputation: 24780

The HashXXXX collections consist of:

  • an array. An object is assigned to a position in the array (a bucket) by its hashCode

  • a list of entries. Since you can have many entries whose hashcode points them to the same bucket, each bucket holds a list of items. A new item will be added to that list (so it does not deletes previous items).

The iteration is running along that list from the second point.

Upvotes: 3

Related Questions