一道关于哈希表的题目
来源：1-1 哈希表基础
weixin_慕圣6334738
2021-10-30 07:44:39
老师你好这里有一道关于哈希表的题目但是我没想明白得到结果的过程
题目如下Assume that HashMap is a separate chaining hash table with 4 buckets indexed 0 through 3 and never resizes. Recall that get returns null if the key is not in the map.
相关代码
import java.util.HashMap;
public class Husky {
public String name;
public Husky(String name) {
this.name = name;
}
public boolean equals(Object o) {
Husky other = (Husky) o;
return this.name.equals(other.name);
}
public int hashCode() {
return this.name.length();
}
public static void main(String[] args) {
HashMap<Husky, Integer> map = new HashMap<>();
Husky a = new Husky("jeter");
Husky b = new Husky("diana");
map.put(a, 1);
map.put(b, 2);
a.name += a.name;
map.put(a, 3);
map.put(b, 4);
b.name += b.name;
map.put(b, 5);
System.out.println(map.size());
System.out.println(map.get(new Husky("jeter")));
System.out.println(map.get(new Husky("jeterjeter")));
}
}结果是 4, null, 3
我再intellij上跑了每个put 后面表的所有key和value但是我没懂为什么是那样
1回答
-
liuyubobobo
2021-10-30
我没有理解你具体不理解的点在哪里。
请阐述：在哪一句执行以后，你认为应该是什么结果？为什么？实际却是什么结果。所以你不理解。
==========
这个问题的核心有两个：
1）是：Husky 这个类的 hashcode 是 name.length，而不是 name。所以，在哈希表中，将首先以 name 的长度分组，name 的长度相同，则造成了哈希冲突，才会进一步比较具体的 name
2）是，当把一个元素存进哈希表以后，改变这个元素的 name，即使长度改变了，这个元素在哈希表中存储的位置不会跟着变。（哈希表没有实时更新，不会一遍一遍地扫描表内的元素，看这些元素是否发生了改变。）（所以，这样做是不安全的。）
所以：
map.put(a, 1) 和 map.put(b, 2) 后，更准确的记录是：
hashcode: 5 : {"jeter": 1} {"diana": 2}其中 hashcode 5 表示哈希值是 5。因为 jeter 和 diana 的长度都是 5。
=========
之后，虽然有 a.name += a.name，但是，整个表变成了：
hashcode: 5 : {"jeterjeter": 1} {"diana": 2}也就是哈希值为 5 的元素里，存了一个 name 长度为 10 的元素。
==========
之后，map.put(a 3)，哈希表变成了
hashcode: 5 : {"jeterjeter": 1} {"diana": 2} hashcode: 10: {"jeterjeter": 3}此时，新加入了 jeterjeter 由于长度为 10，哈希值为 10，直接去哈希值为 10 的 bucket。在这里没有找到哈希冲突，直接加进去。
但是，map.put(b, 4)，diana 可以正常找到，所以，哈希表变成了：
hashcode: 5 : {"jeterjeter": 1} {"diana": 4} hashcode: 10: {"jeterjeter": 3}==========
现在，你应该明白了 b.name += b.name 后，哈希表是：
hashcode: 5 : {"jeterjeter": 1} {"dianadiana": 4} hashcode: 10: {"jeterjeter": 3}map.put(b, 5) 后，是：
hashcode: 5 : {"jeterjeter": 1} {"dianadiana": 4} hashcode: 10: {"jeterjeter": 3} {"dianadiana": 5}请根据上面的哈希表的结果，再看最后打印输出的结果，应该很清晰。
值得一提的是最后一个打印输出，查询 jeterjeter，此时会按照 长度为 10 去查（而不是 5），所以得到的结果是 3。
继续加油！：）
0h021-11-03
