HashMap.get中的循環

Question

這是從HashMap中的鍵中獲取值的代碼。爲什麼需要在第317行循環取值？如果這不是O（1）操作？

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  } 

Answer 1

的HashXXXX集合包括：

• 陣列。將一個對象分配給陣列中的一個位置（一個存儲桶）通過其hashCode

• 一個條目列表。由於您可以有多個條目，其哈希碼指向相同的存儲區，因此每個存儲區都包含列表中的項目。一個新的項目將被添加到該列表（所以它不會刪除以前的項目）。

迭代從第二點開始沿着該列表運行。

Answer 2

這O(1)的部分是在這裏：

table[indexFor(hash, table.length)] 

查找列表進行迭代恰好O(1)。如果散列函數是好的，那麼你迭代的大多數列表的長度只有幾個項目。平均而言，搜索將在經過少量迭代後停止，而這些迭代不依賴於散列項目的總數。這給你分期付款存取時間O(1)。