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       }

回答1:

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.

回答2:

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