0

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       }
JavaDeveloper
  • 5,320
  • 16
  • 79
  • 132

2 Answers2

3

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).

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
3

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.

SJuan76
  • 24,532
  • 6
  • 47
  • 87