java - Java 库设计者明确要求 TreeMap 是红/黑树有什么原因吗？

Question

我正在阅读 Javadoc for the TreeMap type并且惊讶地发现它明确要求 TreeMap 使用红/黑树作为其内部实现。不仅如此，它还专门为红/黑树挑出了一个特定的实现策略:

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

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

我发现这很不寻常，因为我在 Java 文档中没有看到任何其他类似的东西(除了非常精确命名的类型，例如 CopyOnWriteArrayList)。如果你看Collections.sort ，例如，没有提到应该使用什么排序算法。 HashMap documentation没有指定内部表示是否使用链式哈希、线性探测、罗宾汉哈希等。

我对此特别好奇，因为我习惯于阅读 C++ 规范，其中 std::map 的实现仅受复杂性保证和迭代器失效限制的约束。 C++ std::map 原则上可以实现为红/黑树、替罪羊树、splay 树，甚至是确定性跳过列表。

为什么这里的 Javadoc 对 TreeMap 的内部实现如此具体以区别于其他类型，如 HashMap，是否有记录的原因> 或其他算法原语，如排序或搜索？我知道 C ISO 规范中有一个 rationale document解释委员会做出的许多决定，如果这里的决定有类似的东西，我很想看看它是什么。

Answer 1

Is there a documented reason why the Javadoc here is so specific about the internal implementation of TreeMap that would distinguish it from other types like HashMap or other algorithmic primitives like sorting or searching?

简而言之，没有。

I know for the C ISO spec that there's a rationale document explaining many of the decisions that the committee made, and if there's something analogous for the decision here, I'd love to see what it is.

没有这样的(公开的)文档来讨论 Java 的此类决定。至少，在过去的 20 多年里，我没有遇到过。

1. Java 设计者的运作方式与 C、C++ 和 ECMAscript 的正式标准组不同。

2. 由于 javadoc 嵌入在源代码中，因此必须由有权访问核心代码库的人员对其进行实际更改。这将遵循类似于代码审查的程序，而不是标准编写过程。

对于一些 JSR 团队来说，这可能有点不同，但实际上由各自的团队负责人决定他们选择记录多少(或多少)理由。不同的 JSR 运行方式非常不同。

---

在这个阶段任何人都可以说的最好的是，真正的原因已经过时了。我们实际上并不确定最初是谁编写了这些 javadoc，以及谁一直在维护它们。

我们确实知道的一件事是，随着时间的推移，Sun/Oracle 对包含在 javadoc 中的实现细节的数量采取了不同的立场。示例是 HashMap 和 Arrays.sort 的 javadoc，其中详细信息的数量随着不同的版本而改变。