Why does LinkedHashMap not implement SortedMap?

Question

LinkedHashMap is clearly an ordered Map. It orders based upon insertion.

So why does it not implement SortedMap?

Answer 1

From the LinkedHashMap Javadocs:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

While SortedMap is:

A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.

So both exist for different purposes. LinkedHashMap provides iteration in the same order of key insertion while SortedMap is for sorting using Comparator or Comparable.

Answer 2

SequencedMap

Java 21 introduced the SequencedMap interface, which perhaps makes the reasoning and difference more explicit.

Per its Javadocs, SequencedMap is "a Map that has a well-defined encounter order." The term "encounter order" is defined in the Javadocs for SequencedCollection:

The elements of a sequenced collection have an encounter order, where conceptually the elements have a linear arrangement from the first element to the last element. Given any two elements, one element is either before (closer to the first element) or after (closer to the last element) the other element.

SortedMap

SortedMap, on the other hand, imposes a total ordering on its elements:

A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.

Both SortedMap and LinkedHashMap implement SequencedMap, as they both have a well-defined encounter order. However, the elements of LinkedHashMap are not ordered in the "total ordering" sense required by SortedMap, but rather are have an encounter order based on insertion order (or much more rarely, access order). Therefore, LinkedHashMap does not implement SortedMap.

Class diagram

Class diagram of sequenced collections, with maps on the right side:

More info

See:

• Creating Sequenced Collections, Sets, and Maps guide in Java 21 documentation.
• JEP 431: Sequenced Collections
• Sequenced Collections - Deep Dive with the Expert talk by Stuart Marks