java - hashmap 如何保证再次使用的键具有相同的“索引”？

Question

哈希图计算索引的方式是以下代码 -

static int indexFor(int h, int length) {
    return h & (length-1);
}

现在假设第二次使用密钥（假设另一个 put）并且当时长度已经改变。indexFor在这种情况下，当长度为 16 与长度为 64 时如何返回相同的索引？

Answer 1

当length哈希表发生变化时，必须重建整个表以确保每个条目都在它现在应该在的位置。（这称为重新散列。）

这是一个相当昂贵的操作，因此代码会尽量减少它发生的频率。这就是为什么HashMap在第一次构建它时告诉预期有多少元素很有用 - 它允许它避免在填充表格时进行任何重新散列。

Answer 2

长度不一定是哈希中的项目数，而是哈希的最大容量。

通常它是一个质数，只要没有空间添加额外的项目，它就会增加。在这种情况下，容量被增加到下一步并被rehashing执行。