Java HashMap的bucket是否真的存储链表？代码异常场景求教

问题原因分析 #

核心逻辑遗漏：自定义类作为HashMap键必须同时重写hashCode()和equals() #

HashMap判断两个键是否为同一个键的规则是两步校验，缺一不可：

• 第一步校验两个键的哈希值是否相等，不相等直接判定为不同键
• 第二步哈希值相等的前提下，调用equals()方法比较，返回true才会判定为同一个键

你的MyString类只重写了hashCode()方法，没有重写equals()，默认使用Object类的equals()实现，该实现仅比较对象的内存地址。你每次调用new MyString()都会生成全新的实例，内存地址互不相同，因此所有MyString实例的equals()对比都会返回false。

对应你代码的执行逻辑拆解 #

1. 两次put操作时，两个MyString实例的哈希值都是4，会被分配到同一个bucket
2. 由于两个实例地址不同，equals()返回false，HashMap会判定为两个不同的键，依次存入同一个bucket的链表中
3. 调用get方法时，你传入的是新创建的MyString("key1")实例，和之前两次put存入的实例地址都不相同，遍历bucket链表时equals()匹配全部失败，因此返回null

你调试时观察到bucket只有一个条目大概率是观察位置错误，只要两个键哈希值相同且equals()返回false，就会被存入同一个bucket的链表中。

关于HashMap bucket存储结构的说明 #

HashMap的bucket确实支持存储链表或红黑树：

• 当同一个bucket内的节点数≥8且HashMap总容量≥64时，链表会转换为红黑树提升查找效率
• 当节点数回落至≤6时，红黑树会转回链表
  你当前场景下bucket内只有2个节点，存储结构就是普通的单链表。

关于你看到的Baeldung表述的说明 #

Java核心库的Map实现确实不允许单个键对应多个值，这里的「同一个键」特指同时满足哈希值相等且equals()返回true的两个键，你的场景中两个MyString实例属于不同的键，因此不涉及该规则的限制。

内容的提问来源于stack exchange，提问作者Chris Milburn