java - 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

这O(1)是这里的部​​分：

table[indexFor(hash, table.length)]

找到要迭代的列表正是O(1). 如果散列函数很好，您迭代的大多数列表的长度只有几个项目。平均而言，搜索将在不依赖于散列项总数的少量迭代后停止。这为您提供了摊销的访问时间O(1)。

Answer 2

HashXXXX收藏品包括：

• 数组。一个对象通过其 hashCode分配给数组（一个桶）中的一个位置

• 条目列表。由于您可以有许多条目的哈希码将它们指向同一个存储桶，因此每个存储桶都包含一个项目列表。一个新项目将被添加到该列表中（因此它不会删除以前的项目）。

迭代从第二点开始沿着该列表运行。