我知道在 Java 8 中,HashMap
针对分布不均的 hashCode
进行了优化。在超过阈值的情况下,它会将桶中的节点从链表重建为树。也是stated这种优化不适用于不可比较的键(至少性能没有提高)。在下面的示例中,我将 not Comparable
键放入 HashMap
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;
class Main {
public static void main(String[] args) throws InterruptedException {
Map<Key, Integer> map = new HashMap<>();
IntStream.range(0, 15)
.forEach(i -> map.put(new Key(i), i));
// hangs the application to take a Heap Dump
TimeUnit.DAYS.sleep(1);
}
}
final class Key {
private final int i;
public Key(int i) {
this.i = i;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Key key = (Key) o;
return i == key.i;
}
@Override
public int hashCode() {
return 1;
}
}
但检查堆转储显示节点已重新排列为树。
我的问题是,如果节点不会提高性能,为什么要将节点重建到树中?在这种情况下,节点根据哪些标准进行比较,以确定哪个键应该是右节点,哪个是左节点?
最佳答案
我认为您有点误解了该回答的意思。 Comparable
不是需要的,它只是一种优化,可以在哈希值相等时使用 - 为了决定将条目移动到哪里 - 向左或向右( 完美平衡的红黑树节点
)。稍后如果键不可可比,它将使用System.identityHashcode
。
figure out which key should be right node and which left
它向右移动 - 较大的键向右移动,但树可能需要平衡。 一般您可以查找树
如何成为完美平衡的红黑树
的确切算法,例如here
关于java - 为什么 HashMap 使用 TreeNode 作为非 Comparable 键?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45117319/