I was reading over the Javadoc for the TreeMap type and was surprised to see that it explicitly requires that TreeMap use a red/black tree as its internal implementation. Not only that, it specifically singles out a particular implementation strategy for the red/black tree:
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.
I found this unusual because I haven’t seen anything else comparable to this in the Java documentation (with the exception of very precisely named types like CopyOnWriteArrayList, for example). If you look at Collections.sort, for example, there’s no mention of what sorting algorithm should be used. The HashMap documentation doesn’t specify whether the internal representation uses chained hashing, linear probing, Robin Hood hashing, etc.
I was especially curious about this because I’m used to reading the C++ spec, where the implementation of std::map is constrained only by complexity guarantees and restrictions on iterator invalidation. The C++ std::map could in principle be implemented as a red/black tree, or a scapegoat tree, or a splay tree, or even a deterministic skiplist.
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.