在发生碰撞或最坏情况下，为什么要调整大小

Question

我在Java版本中提出这个问题，直到1.7。我正在使用反射来找出当前的哈希图能力。在下面的程序中，将12个独特的人放入一个桶中的哈希图(使用相同的哈希码(中。然后，我将第13个独特的人放在相同或不同的桶上(使用相同或不同的哈希码(。在这两种情况下，添加了此第13个元素后，Hashmap的大小为32桶。我知道，由于负载系数.75和初始容量16 HashMap的重量为13个元素。但是仍然有空的存储桶，这些13个元素仅使用2个存储桶。

我的问题是：

1. 我的理解是正确的。我不是犯任何错误吗？这是hashmap的预期行为吗？

2. 如果所有这些都是正确的，那么即使有12或11个自由存储桶，为什么在这种情况下需要使用13个元素将哈希图倍加倍。调整哈希图的大小不是额外的开销还是昂贵？在这种情况下，需要将哈希姆普加倍，而可以根据哈希码将13个可用的存储桶放入任何可用的存储桶？

   ？

。

public class HashMapTest {
    public static void main(String[] args)
            throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException {
        HashMap<Person, String> hm = new HashMap<Person, String>();
        for (int i = 1; i <= 12; i++) {
            // 12 Entry in same bucket(linkedlist)
            hm.put(new Person(), "1");
        }
        System.out.println("Number of Buckets in HashMap : " + bucketCount(hm));
        System.out.println("Number of Entry in HashMap :  " + hm.size());
        System.out.println("**********************************");
        // 13th element in different bucket
        hm.put(new Person(2), "2");
        System.out.println("Number of Buckets in HashMap : " + bucketCount(hm));
        System.out.println("Number of Entry in HashMap :  " + hm.size());
    }
    public static int bucketCount(HashMap<Person, String> h)
            throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(h);
        return table == null ? 0 : table.length;
    }
}
class Person {
    int age = 0;
    Person() {
    }
    Person(int a) {
        age = a;
    }
    @Override
    public boolean equals(Object obj) {
        return false;
    }
    @Override
    public int hashCode() {
        if (age != 0) {
            return 1;
        } else {
            return age;
        }
    }
}

输出

Number of Buckets in HashMap : 16
Number of Entry in HashMap :  12
**********************************
Number of Buckets in HashMap : 32
Number of Entry in HashMap :  13

Answer 1

1. 是的，这是预期的行为。
2. Hashmap不在乎使用多少存储桶。它只知道已经达到了负载因子，因此碰撞的可能性变得太大，因此应该调整地图。即使已经发生了许多碰撞，调整地图的大小实际上也可以解决。不是在您的情况下，因为您是故意选择相同的哈希码，但是在更现实的情况下，Hashcodes应该具有更好的分布。如果您是故意选择不良的hashcodes，则Hashmap无能为力，并且添加复杂性来处理极端情况是没有意义的，这绝不应该发生，并且hashmap无法解决。<<<<<<<<<<<<<<<<<<<<<<

Answer 2

是的，您观察到的行为是预期的行为。

HashMap的实现希望您使用合理的hashCode对键。它假设您的hashCode将在可用的存储桶中尽可能均匀地分发键。如果您不这样做(就像您在示例中所做的那样 - 所有密钥都具有相同的hashCode(，您将获得不良的性能。

在平均分布的假设下，通过负载因子，HashMap的大小翻倍就有意义。它没有检查实际上有多少存储桶(因为它无法知道将新条目分配给空桶还是被占用的存储桶(。它只是检查每个存储桶的平均条目数。一旦该数字超过了负载因子，将加倍的存储桶数。

Answer 3

这里也有一个轻微的方面；当您调整内部数组大小(从16到32(时，您也在"触摸"所有条目。让我解释一下：

当有16个存储桶(内部数组为16(时，只有last 4 bits决定该条目将在哪里；思考%，但在内部实际上是(n - 1) & hash，其中n是桶的数量。

当内部阵列生长时，考虑了另外一位以决定条目的去向：曾经有4 bits，现在有5 bits；这意味着所有条目都是重新限制的，现在它们可能会移至不同的存储桶。这就是为什么调整大小的原因是分散条目的原因。

如果您真的想要填补所有"间隙"，则指定1的load_factor;而不是0.75的默认值；但这具有Hashmap构造函数中记录的含义。