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

我正在查看HashMapJava 7 中的源代码,我看到该put方法将检查是否已存在任何条目,如果它存在,那么它将用新值替换旧值.

    for (Entry 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;
        }
    }

所以,基本上它意味着给定密钥总是只有一个条目,我也通过调试看到了这一点,但如果我错了,那么请纠正我.

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

    for (Entry 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> Eran..：

---

table[indexFor(hash, table.length)]是HashMap可能包含我们正在寻找的密钥的桶(如果它存在于其中Map).

但是,每个存储桶可能包含多个条目(具有相同hashCode()或不同的键的不同键hashCode()仍然映射到同一个存储桶),因此您必须迭代这些条目,直到找到您要查找的键.

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

---

@pjj我从来没有说过给定密钥可以有多个条目.我说一个给定的桶可以有多个条目.

---

@pjj不同的密钥可以具有相同的哈希码值,因此最终在同一个桶中(根据密钥的哈希值选择桶)

2> 小智..：

---

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

public V get(Object key)  {
        if (key == null)
           return getForNullKey();
         int hash = hash(key.hashCode());
         for (Entry 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.

有时可能存在Hashcode冲突的可能性,并且为了解决此冲突,Hashmap使用equals(),然后将该元素存储到同一存储桶中的LinkedList中.

让我们举个例子:

获取密钥vaibahv的数据:map.get(new Key("vaibhav"));

脚步:

计算Key {"vaibhav"}的哈希码.它将生成为118.

使用索引方法计算索引将为6.

转到数组的索引6并将第一个元素的键与给定键进行比较.如果两者都是等于则返回值,否则检查下一个元素是否存在.

在我们的例子中,它不是第一个元素,节点对象的下一个不是null.

如果node的下一个为null,则返回null.

如果node的下一个非空遍历到第二个元素并重复进程3,直到找不到key或next不为null.

对于此检索过程,将使用循环.有关更多参考,请参阅 此内容

---

请不要将JPG用于非摄影图像.

---

@pjj不一样*key*,但是相同的*hash*(或相同的数组索引,即使不是相同的哈希).这里答案的要点是`HashMap`不会(**不能**)神奇地包含一个独特的地方来放置将来"放入"的每个条目.被置于`HashMap`中的键可能具有*hash-conflicts*,在这些键中,即使它们不是真正相同的键,它们也希望放在结构中的相同位置.当条目"放入"地图时,有一种特殊的方法可以解决这个问题.在`get`上,你必须考虑到这一点.

3> Eugene..：

---

对于记录,在java-8中,这也存在(有点,因为还有TreeNode):

if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }

基本上(对于bin不是a的情况Tree),迭代整个bin,直到找到我们要查找的条目.

看看这个实现,你可能会理解为什么提供一个好的哈希是好的 - 所以不是所有的条目都在同一个桶中,所以有更大的时间来搜索它.