Java库设计者明确要求TreeMap成为红/黑树是否有原因？

Question

我正在阅读类型的Javadoc,TreeMap并惊讶地发现它明确要求TreeMap使用红/黑树作为其内部实现.不仅如此,它还特别指出了红/黑树的特定实施策略:

基于红黑树的NavigableMap实现.地图根据其键的自然顺序进行排序,或者根据使用的构造函数在地图创建时提供的比较器进行排序.

此实现为containsKey,get,put和remove操作提供有保证的log(n)时间成本.算法是Cormen,Leiserson和Rivest的算法导论中的算法的改编.

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

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

是否有一个记录在案的原因,为什么这里的Javadoc对内部实现如此具体TreeMap,以区别于其他类型HashMap或其他算法原语如排序或搜索？我知道C ISO规范中有一个基本原理文件解释了委员会做出的许多决定,如果这里的决定有类似的话,我很想看看它是什么.

Answer 1

是否有记录的原因说明为什么这里的 Javadoc 对于 TreeMap 的内部实现如此具体，以将其与其他类型（如 HashMap）或其他算法原语（如排序或搜索）区分开来？

简而言之，没有。

我知道 C ISO 规范有一个基本原理文档解释了委员会做出的许多决定，如果这里的决定有类似的内容，我很想看看它是什么。

没有这样的（公共）文档来讨论 Java 的此类决策。至少，在过去 20 多年里我从未遇到过。

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

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

对于某些 JSR 团队来说，情况可能有点不同，但实际上由各自的团队负责人决定他们选择记录多少（或很少）的基本原理。不同的 JSR 的操作方式非常不同。

在这个阶段，任何人能说的最好的一句话就是，真正的原因已经随着时间的推移而消失了。我们实际上并不确定最初是谁编写了这些 javadoc，以及谁一直在维护它们。

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