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

Question

我试图理解,当超过所占用的桶数或所有桶中的条目总数时,会发生散列图的重新发生.意思是,我们知道如果16个桶中的12个(每个桶中有一个条目)已满(考虑到默认的loadfactor和初始容量),那么我们就知道在下一个条目中将重新散列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 肯定会改变，因为它们是不同的对象。

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

我已经运行了评论中提到的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 个节点（阅读更多）。

关于Hashmap的文档和关于hashmap 中存储桶的讨论在这方面会有所帮助。