java - 为什么我们在 TreeMap 中转换为 Comparable

Question

我正在学习 Java 中的 Collections，并在 TreeMap API 中遇到了以下代码，

 if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);

为什么我们首先需要转换为Comparable？由于key已经实现了Comparable并覆盖了compare()。为什么我们不能调用 key.compare(t.key) ？

关键是实现 Comparable。

Answer 1

TreeMap 文档提供以下信息:

A Red-Black tree based {@link NavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time, depending on which constructor is used.

以下两个 TreeMap 构造函数(还有更多，但适用相同的规则)也适用于该特定规则。第一个假设 key 本质上是Comparable(并且每个插入的 key 都需要这样做)，而第二个则提供了提供自定义Comparator的可能性。

public TreeMap() {
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

为了确定应使用哪种行为，实现经常验证Comparator是否已初始化。

final int compare(Object k1, Object k2) {
    return comparator == null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

因此您的以下假设不适用:

Since the key is already implementing Comparable and having the compare() overriden.

Map的键K可以是任何类型，不限于Comparable。这提供了更大的灵 active ，因为有时您无法使类相互比较(例如，如果它来自第三方库)或者类在逻辑上没有自然顺序。我建议阅读 Comparable 和 Comparator 的文档。