java为什么HashMap在冲突或最坏情况下调整大小

Question

我问的这个问题是关于java版本直到1.7的。我使用反射来找出HashMap的当前容量。在下面的程序中，将12个唯一的人放入一个HashMap桶中（使用相同的hashcode）。然后我将第13个唯一的人放在相同或不同的桶中（使用相同或不同的哈希代码）。在这两种情况下，添加第13个元素后，HashMap将调整大小为32个存储桶。我了解到，由于负载系数.75和初始容量16，HashMap的大小调整为第13个元素的两倍。但是仍然有空桶可用，并且只有2个桶用于这些元素

我的问题是：

1. 我的理解正确吗。我没有犯任何错误。这是HashMap的预期行为吗

2. 如果所有这些都是正确的，那么即使有12个或11个空闲的bucket，为什么在这种情况下需要使用第13个元素将HashMap翻一番呢。调整HashMap的大小不是额外的开销吗？在这种情况下，需要将HashMap加倍，而根据hashcode，可以将HashMap放入任何可用的bucket中

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不关心使用了多少个存储桶。它只知道已经达到了负载系数，因此发生碰撞的概率变得太大，因此应该调整地图的大小。尽管已经发生了许多碰撞，但调整地图大小实际上可以解决这一问题。在您的情况下不是这样，因为您故意选择了相同的哈希代码，但在更现实的情况下，哈希代码应该有更好的分布。如果你故意选择了糟糕的哈希代码，HashMap就无法让自己变得高效，也没有必要为了处理极端情况而增加复杂性，这是不应该发生的，而且HashMap无论如何也无法修复

Answer 2

这里也有一个细微的方面；当你调整内部数组的大小（从16到32）时，你也在“触摸”所有的条目。让我解释一下：

当有16个bucket（内部数组大小为16）时，只有last 4 bits决定该条目的去向；想想%，但在内部它实际上是(n - 1) & hash，其中n是桶的数量

当内部数组增长时，需要考虑另外一个位来决定条目的位置：过去有4 bits，现在有5 bits；这意味着所有条目都被重新散列，它们现在可能会移动到不同的存储桶中；这就是为什么要调整大小，以分散条目

如果你真的想填补所有的“空白”，你可以指定一个load_factor的1；而不是默认的0.75；但正如HashMap构造函数中记录的那样，这会产生影响

Answer 3

是的，你观察到的行为是预期的行为

HashMap的实现要求您对键使用合理的hashCode。它假定hashCode会在可用的存储桶中尽可能均匀地分配密钥。如果您没有做到这一点（就像您在示例中所做的那样——所有键都具有相同的hashCode），您将获得糟糕的性能

在均匀分布的假设下，一旦通过负载因子，HashMap的大小就会翻倍。它不会检查实际有多少桶是空的（因为它无法知道新条目是分配给空桶还是分配给已占用的桶）。它只是检查每个bucket的平均条目数。一旦这个数量超过负载系数，铲斗的数量就会翻倍