問題描述

我只針對 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 調整大小以防發生碰撞或最壞的情況的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！