我问的这个问题只针对 1.7 之前的 Java 版本。我正在使用反射来找出 HashMap 的当前容量。在下面的程序中,将 12 个唯一的人放入一个 HashMap 桶中(使用相同的哈希码)。然后我将第 13 个唯一的人放在相同或不同的桶中(使用相同或不同的哈希码)。在这两种情况下,在添加第 13 个元素后,HashMap 的大小都会调整为 32 个桶。我知道由于负载因子 .75 和初始容量 16 HashMap 调整到它的双倍与第 13 个元素。但是仍然有可用的空桶,并且只有 2 个桶用于这第 13 个元素。
我的问题是:
我的理解正确吗?我没有弄错吗?这是 HashMap 的预期行为吗?
如果所有这些都是正确的,那么即使有 12 或 11 个空闲桶,为什么在这种情况下需要将第 13 个元素加倍的 HashMap。调整 HashMap 的大小不是额外的开销或成本吗?在这种情况下需要将 HashMap 加倍,而 13th 可以根据哈希码放入任何可用的桶中?
.
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 不关心使用了多少桶。它只知道已经达到负载因子,发生碰撞的概率因此变得太大,因此应该调整 map 的大小。尽管已经发生了很多碰撞,但调整 map 大小实际上可以解决这个问题。不是你的情况,因为你故意选择相同的 hashCode,但在更现实的情况下,hashCodes 应该有更好的分布。如果您故意选择错误的 hashCode,HashMap 无法做任何事情来提高自身效率,并且没有必要增加复杂性来处理极端情况,这种情况永远不会发生,而且 HashMap 无论如何也无法修复。
关于java - 为什么 HashMap resize 在碰撞或最坏情况下,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44745811/