Java 中HashMap底层红黑树不需要实现Comparable接口，原因是底层是用的hash值来比较大小吗？
来源：8-1 什么是优先队列
Panda_io
2022-04-05
问题：老师说java.util中的TreeMap和TreeSet基于红黑树，其中的Key需要实现Comparable接口，看了底层确实如此，于是联想到了HashMap，HashMap中的Key不需要实现Comparable，我查看了下源码，大致底层在红黑树实现的地方是对比两个节点的hash值来判断节点的大小的，但是我又不敢百分百确定，那个源码我没有读透，想请问老师我的理解是对的吗？
联想：个人觉得TreeMap和TreeSet考虑的是集合的顺序性因此需要强制实现Comparable接口，而HashMap考虑的是查询的效率能达到O（1）级别，且一般情况下的哈希表都达不到树化的条件，因此在HashMap没有强制实现Comparable接口，而是在达到树化的条件后使用Key的Hash值来进行大小比较以确定插入的叶子节点位置。
1回答
-
liuyubobobo
2022-04-06
在我的其他课程中有过同学问我这个问题，我直接把我的文字搬运过来：
Java 标准实现中的 HashMap，其中转成的红黑树，就是正常的红黑树。
如果 HashMap 的 Key 不可比较的话，HashMap 会使用这个 key 的系统 hashcode 值作为红黑树的键，而系统的 hashcode 值一定可比较（其实就是一个 int，表示其内存地址。）但是此时，在查找一个 key 的时候，HashMap 会检索整个 tree 进行查找。（因为对于自定义的类，可能系统哈希值不一样，但是其“值”是一样的。）
换句话说，对于 Java 自带的 HashMap 来说，如果传入的 Key 不可比较的话，其自带的把链表转成红黑树的过程并不会带来性能的提升（因为检索了整棵树，这和遍历整个链表是一样的。甚至性能稍有拖慢，因为有一个转换的过程。）
这里是一个很好的 ref 解释这个事情：
https://yermilov.github.io/blog/2017/02/24/tiebreaker-regarding-java-hashmap-treenode-and-tiebreakorder/继续加油！：）
10
相似问题