为什么 HashMap 会在发生冲突或最坏情况时调整大小

Question

我问的这个问题仅涉及 java 版本，直到 1.7。我正在使用反射来找出 HashMap 的当前容量。在下面的程序中，将 12 个不同的人放入 HashMap 的单个存储桶中（使用相同的哈希码）。然后我将第 13 个唯一的人放在相同或不同的存储桶中（使用相同或不同的哈希码）。在这两种情况下，添加第 13 个元素后，HashMap 都会将大小调整为 32 个存储桶。据我所知，由于负载因子为 0.75 且初始容量为 16，HashMap 的大小调整为第 13 个元素的两倍。但是仍然有空桶可用，并且只有 2 个桶用于这第 13 个元素。

我的问题是：

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

2. 如果所有这些都是正确的，那么即使有 12 或 11 个空闲桶，为什么在这种情况下需要将 HashMap 的第 13 个元素加倍。调整 HashMap 的大小是否会带来额外的开销或成本？既然可以根据hashcode将第13个放入任何可用的桶中，那么在这种情况下需要将HashMap加倍吗？

。

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