为什么 HashMap 调整大小以防发生碰撞或最坏的情况

本文介绍了为什么 HashMap 调整大小以防发生碰撞或最坏的情况的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着跟版网的小编来一起学习吧！

问题描述

我只针对 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.

我的问题是:

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

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

为什么 HashMap 调整大小以防发生碰撞或最坏的情况

问题描述

推荐答案

相关文档推荐