为什么HashMap的get方法有一个FOR循环？

hashmap java

2022-09-01 00:26:38

我正在查看Java 7中的源代码，我看到该方法将检查是否存在任何条目，如果它存在，那么它将用新值替换旧值。HashMapput

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

因此，基本上这意味着给定的键始终只有一个条目，我也通过调试看到了这一点，但是如果我错了，请纠正我。

现在，既然给定键只有一个条目，为什么该方法有一个FOR循环，因为它可以简单地直接返回值？get

    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }

我觉得上面的循环是不必要的。如果我错了，请帮助我理解。

答案 1

table[indexFor(hash, table.length)]是可能包含我们正在寻找的密钥的存储桶（如果它存在于中）。HashMapMap

但是，每个存储桶可能包含多个条目（具有相同或具有不同键的不同键仍映射到同一存储桶），因此您必须循环访问这些条目，直到找到要查找的键。hashCode()hashCode()

由于每个存储桶中的预期条目数应该非常小，因此此循环仍会在预期时间内执行。O(1)

答案 2

如果你看到HashMap的get方法的内部工作。

public V get(Object key)  {
        if (key == null)
           return getForNullKey();
         int hash = hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
         {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                 return e.value;
         }
             return null;
}

首先，它获取传递的键对象的哈希代码，并查找存储桶位置。
如果找到正确的存储桶，它将返回值（e.value）
如果未找到匹配项，则返回 null。

有时可能会发生哈希代码冲突，为了解决这种冲突，哈希映射使用equals（），然后将该元素存储到同一存储桶的LinkedList中。

让我们举个例子：

获取 key vaibahv 的数据： map.get（new Key（“vaibhav”））;

步骤：

计算 Key {“vaibhav”} 的哈希代码。它将生成为 118。
使用索引方法计算索引，它将是6。
转到数组的索引 6，并将第一个元素的键与给定键进行比较。如果两者都相等，则返回值，否则检查下一个元素（如果存在）。
在我们的例子中，它没有被找到为第一个元素，节点对象的下一个不是空的。
如果节点的下一个为 null，则返回 null。
如果下一个节点不是空，则遍历到第二个元素并重复该过程 3，直到找不到 key 或 next 不为 null。

对于此检索过程，将使用循环。有关更多参考，您可以参考此