为什么 HashMap 调整大小以防发生碰撞或最坏的情况 [英] Why HashMap resize In case of collision or worst case

问题描述

我只针对 1.7 之前的 java 版本提出这个问题.我正在使用反射来找出 HashMap 的当前容量.在下面的程序中，将 12 个唯一的人放入一个 HashMap 桶中(使用相同的哈希码).然后我将第 13 个独特的人放在相同或不同的存储桶上(使用相同或不同的哈希码).在这两种情况下，添加第 13 个元素后，HashMap 都将大小调整为 32 个桶.我知道由于负载因子 0.75 和初始容量 16 HashMap 调整到其第 13 个元素的两倍.但是仍然有可用的空桶，并且只有 2 个桶用于这第 13 个元素.

I am asking this question with respect to java version till 1.7 only. I am using reflection to find out current capacity of HashMap. In below program is putting 12 unique person into a single bucket of HashMap (using same hashcode). Then i am putting 13th unique person on same or different bucket(using same or different hashcodes). In both cases after adding this 13th element, HashMap resizes to 32 buckets. I understand that due to load factor .75 and initial capacity 16 HashMap resizes to its double with 13th element. But there are still empty buckets available and only 2 buckets are used for these 13th elements.

我的问题是:

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

1. Is my understanding correct. Am I not making any mistake. Is this the expected behavior of HashMap?

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

If all this is correct then even though there are 12 or 11 free buckets why the need to double the HashMap with 13th element in this case. Isn't it extra overhead or costly to resize the HashMap? What is the need to double the HashMap in this case While 13th can be put in any available bucket according to hashcode?

.

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

推荐答案

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

这篇关于为什么 HashMap 调整大小以防发生碰撞或最坏的情况的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！