TreeMap 不会比较地图中的每个元素

Question

这是一个常见的问题： 我正在 TreeMap 中编写自定义比较器来比较自定义 class A（由我自己定义）。我发现，当我不断地向树图中添加键值对时，新添加的键并没有比较树图中的每个键，而是只比较底部的几个键而跳过顶部的一些键。所以树图中有重复的键。

以前有人问过这个问题吗？同样，这是一个普遍的问题，代码尤其是用于测试的数据集未对 public.

开放

Answer 1

这是预期的行为。 TreeMap class 被实现为二叉搜索树。因此，它只需要访问节点总数的以 2 为底的对数。您可以在 TreeMap.java 实现中亲眼看到这种行为，其中代码确定它是否需要访问左子节点或右子节点。有关详细信息，请查看 put() 和 get() 方法实现。