时间戳

首页 > 解决方案 > 我们在 Java HashMap 的 put() 方法中比较什么？

java - 我们在 Java HashMap 的 put() 方法中比较什么？

问题描述

我打开了HashMap 源代码（Java 8+）并检查了put() 方法。在 Java 7（及更低版本）中，源代码有点简单，但我无法理解 Java 8+ 版本。

如果桶中的元素不存在，我们只需将其放入 HashMap 中：

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

但是如果元素已经存在，我们就会遇到碰撞。

在“else”块的开头，我们通过哈希（？）比较元素（？）和（什么？这个桶中的第一个元素？）：

else {
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;

但是，等等，我们后来又做了一次：

    ...
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    ...
}

我们遍历列表直到结束，并将新元素与桶中的所有元素（for循环）进行比较。所以，我不明白第一次比较的目的。它（第一种情况）是否意味着我们将最后添加的元素（已经在 hashmap 中）与新的“准备添加”元素进行比较，如果它们不在同一个桶中？

标签： javahashmap

解决方案

在位置tab[i = (n - 1) & hash]（即在散列索引处），我们有null（在这种情况下地图不包含条目）或 的实例Node，这是您感兴趣的。

从概念上讲，这个实例Node满足三个角色之一，每个角色对应于内部 if/else 结构中的一个分支：

  1. 这是我们正在寻找的实际条目；
  2. 它是树的根（当 bin 存储为树时）
  3. 它是链表的头部（当bin存储为链表时）

在第三种情况下，我们需要检查每个后续节点，直到找到所需的条目（或到达末尾），因此比较看起来类似于第一种情况中使用的比较。

推荐阅读