Java中HashMap的奇怪行为
我在下面的课堂上发现hashmap有一些奇怪的行为
class Employee {
private String a;
private int b;
public Employee(String a, int b) {
this.a = a;
this.b = b;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((a == null) ? 0 : a.hashCode());
result = prime * result + b;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Employee other = (Employee) obj;
if (a == null) {
if (other.a != null)
return false;
} else if (!a.equals(other.a))
return false;
if (b != other.b)
return false;
return true;
}
public static void main(String[] args) {
HashMap<Employee,Integer> map = new HashMap<>();
for(int i = 0; i < 13; i++) {
map.put(new Employee( i + "", i), i + i);
}
}
}
当我使用new Employee(“,i”)作为在map中存储数据的键时,它运行良好,并在插入第12个节点后调整了map的大小。但是在使用 新员工(i+“”,i)作为键,它显示出奇怪的行为,使用此键添加第10个元素时,它将映射从16调整为32,添加第11个元素时,它再次将映射从32调整为64。 如果您发现这种行为的任何原因,请提供帮助
# 1 楼答案
正如@G_H提到的,我相信您指的是地图的内部结构,可以通过调试器看到。 HashMap使用hashCode()方法将对象分组到“bucket”中
重写的hashCode()方法使用字符串成员a的值。当a为“”时,其哈希代码为0,因此要插入的元素的哈希代码相对更接近,而不是将a设置为具有更高哈希代码的更有意义的字符串时
出于某种原因(取决于哈希桶的具体实现方式),当哈希代码值相距更远时,HashMap对象决定更快地扩大其内部结构
对于插入的元素,请查看它们的哈希代码值,这将是有意义的
# 2 楼答案
原因是Java 8中HashMap的新组织。当特定bin中的列表变得太长时
HashMap
会将该列表迁移到树中,而不是链表中——这个过程称为树化TREEIFY_THRESHOLD=8表示当给定bin中有8个条目时,给定bin应该在二叉树中存储冲突值,而不是链表(从而将此bin的搜索复杂度从O(n)更改为O(logn))
方法treeifyBin替换bin中的所有链接节点作为散列,除非表太小,在这种情况下,它会调整表的大小
所以在你的例子中,你得到了64个大小(这段代码使大小调整了两次,将标签大小增加到32,并且64(MIN_TREEIFY_CAPACITY)):
# 3 楼答案
我试着重写你代码的has方法。通过您的实现(使用反射获取地图细节)
改写如下:
那么尺寸的增加就如预期的那样
虽然我无法确定地解释,但下面来自HashMap实现的片段表明,哈希计算值可能会增加映射的大小