java - Hashmap loadfactor - 基于占用的桶数或所有桶中的条目数？

Question

我试图了解在超过占用的桶数或所有桶中的条目总数时，会发生 hashmap 的重新散列。意思是，我们知道如果 16 个桶中有 12 个(每个桶中有一个条目)已满(考虑到默认负载因子和初始容量)，那么我们知道在下一个条目中 HashMap 将被重新散列。但是如果假设只有 3 个桶被占用，每个桶有 4 个条目(总共 12 个条目，但 16 个中只有 3 个桶在使用中)，情况会怎样呢？

所以我尝试通过制作最差的哈希函数来复制它，该函数会将所有条目放在一个桶中。

这是我的代码。

class X {

    public Integer value;

    public X(Integer value) {
        super();
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        X a = (X) obj;
        if(this.value.equals(a.value)) {
            return true;
        }
        return false;
    }

}

现在我开始将值放入 HashMap 中。

HashMap<X, Integer> map = new HashMap<>();
    map.put(new X(1), 1);
    map.put(new X(2), 2);
    map.put(new X(3), 3);
    map.put(new X(4), 4);
    map.put(new X(5), 5);
    map.put(new X(6), 6);
    map.put(new X(7), 7);
    map.put(new X(8), 8);
    map.put(new X(9), 9);
    map.put(new X(10), 10);
    map.put(new X(11), 11);
    map.put(new X(12), 12);
    map.put(new X(13), 13);
    System.out.println(map.size());

所有节点都按预期进入单个存储桶，但我注意到在第 9 个条目上， HashMap 重新散列并将其容量增加了一倍。现在在第 10 个条目上，它的容量再次翻了一番。

谁能解释这是怎么发生的？

提前致谢。

Answer 1

在 HashMap 中，如果它们的哈希码相同，条目将出现在同一个桶中。如果将唯一的 Integer 对象放在一个 hashMap 中，它们的 hashcode 肯定会发生变化，因为它们是不同的对象。

但在您的情况下，所有对象都具有相同的哈希码。这意味着您指定的所有条目都将在一个存储桶中。这些桶中的每一个都遵循特定的数据结构(链表/树)。这里的容量根据特定的数据结构和 HashMap 而变化。

我已经运行了评论中提到的 JB Nizet 的代码 ( https://gist.github.com/jnizet/34ca08ba0314c8e857ea9a161c175f13/revisions )，循环限制为 64 和 128(添加 64 和 128 元素):

1. 添加 64 个元素:将第 49 个元素添加到 HashMap 时容量翻倍(128)(因为负载因子为 0.75)
2. 添加 128 个元素时:将第 97 个元素添加到 HashMap 时容量翻倍(256)(也是因为负载因子为 0.75)。

增加容量到64后，HashMap正常工作。

综上所述，bucket使用一定长度(8个元素)的链表。之后它使用树数据结构(容量有波动)。原因是访问树结构 (O(log(n))) 比链表 (O(n)) 更快。

此图显示了 JAVA 8 HashMap 的内部数组，其中包含树(在桶 0 处)和链表(在桶 1、2 和 3 处)。 Bucket 0 是一棵树，因为它有超过 8 个节点 ( readmore )。

有关 Hashmap 的文档和关于 bucket in hashmap 的讨论在这方面会有帮助。