Sequenced Collections in Java 21

On September 19, 2023, a new version of Java 21, was released.  It is an LTS version and these are the features that characterize it:

In this article we will take a closer look at JEP 431, the Sequenced Collections.

The Danish philosopher Sơren Kierkegaard argues that our understanding of events can only come after we have experienced them: “Life can only be understood backwards; but it must be lived forwards”. The developers of Java version 21 were probably inspired by these words when they introduced new interfaces for representing collections with a defined order of occurrence. Each of these collections has a first well-defined element, a second element and so on, up to the last element. In addition, uniform APIs are provided to access the first and last items and process their items in reverse order.

Ordered Access in Java Collections

A long-standing problem with Java’s collections framework has been the lack of a single collection type that guarantees a specific order for its elements. This has caused problems and frustrations for developers. In addition, the framework has historically lacked consistent methods for accessing the first and last elements of collections, or for easily iterating through them in reverse order.

Consider collections such as List and Deque. Both maintain a particular order for their elements, but their common supertype, Collection, doesn’t guarantee order. Similarly, Set itself doesn’t have an order, but some of its subtypes such as SortedSet and LinkedHashSet do. This inconsistency means that support for ordered access is scattered throughout the collection hierarchy, and methods for working with order are either inconsistent or entirely missing.

Java’s New Sequenced Collection Implementations

Here’s a detailed breakdown of how developers have integrated sequenced collections into the existing Java Collections Framework.

Superinterface Adjustments

• List and Deque: These two interfaces, which already maintain order, now directly extend SequencedCollection. This ensures that they inherit the functionality related to accessing the first and last elements, as well as getting a reverse view.
• LinkedHashSet: This set implementation, which preserves insertion order, now also implements SequencedSet. This allows it to use  methods specifically designed for ordered sets, such as adding elements at specific positions while preserving the overall order.
• SortedSet: This interface, which inherently maintains order based on a sort criteria, now extends SequencedSet. This reinforces the ordered nature of SortedSet and provides access to functions such as first() and last(). Importantly, SortedSet implementations such as TreeSet can still use their specific sort logic alongside the SequencedSet methods.
• LinkedHashMap and SortedMap: Similar to LinkedHashSet and SortedSet, these interfaces, which maintain order based on insertion or key sorting respectively, now additionally implement SequencedMap. This allows them to benefit from methods like firstEntry() and lastEntry() that are specifically designed for ordered maps.

Covariant Overrides for reversed

To ensure type safety and clarity, the developers have implemented covariant overrides for the reversed () method in relevant interfaces. This means that when called on a specific sequenced collection type (e.g., List), the reversed view returned will also be of that specific type (e.g., List). This avoids potential issues with unexpected return types. For example, List::reversed is overridden to return a List instead of a SequencedCollection.

New Methods in Collections Class

The Collections utility class has been extended with new methods to create unmodifiable wrappers for the three new sequenced types:

• Collections.unmodifiableSequencedCollection(sequencedCollection): This method takes a SequencedCollection and returns an unmodifiable version of it. This allows developers to create read-only versions of sequenced collections to prevent accidental changes.
• Collections.unmodifiableSequencedSet(sequencedSet): Similar to the previous method, this takes a SequencedSet and returns its unmodifiable counterpart.
• Collections.unmodifiableSequencedMap(sequencedMap): This method creates an unmodifiable version of a SequencedMap.

These new methods promote data immutability, which can be beneficial for security and thread safety in concurrent environments. By integrating Sequenced Collections in this way, the developers have significantly improved the consistency and usability of ordered collections in the Java Collections Framework.

Exploring the Functionality of Sequenced Collections

Let’s look at how these interfaces are used in practice:

Processing a Large Log File in Reverse Order

Imagine a scenario where you need to analyze a massive log file, starting with the most recent entries. A straightforward approach would be to read the entire file line by line, but this can be inefficient for large files. Sequenced Collections and streams come to the rescue.

Prioritized Task Queue with Dynamic Updates

Consider a task scheduling system where tasks arrive with different priorities. You need to maintain a queue that prioritizes tasks based on their urgency while allowing for dynamic updates (insertion and removal) of tasks.

Risks and Considerations in Introducing Sequenced Collections

While sequenced collections offer significant benefits, their introduction  hasn’t been without its challenges. Here’s a breakdown of the key risks and assumptions that the developers considered.

Method Name Collisions

Adding new methods high in the inheritance hierarchy can cause conflicts with existing method names in subclasses. Methods such as reversed() and getFirst() could potentially conflict with existing implementations, causing unexpected behavior.

Covariant Overrides and Binary Incompatibility

A particular concern was the covariant overrides for the reversed() method on both List and Deque. While this approach ensured type safety, it introduced source and binary incompatibility with existing collections that implemented both interfaces. This could potentially break code that relied on these collections.

Impact on Existing Implementations

Two examples in the JDK were affected: LinkedList and an internal class sun.awt.util.IdentityLinkedList.

• LinkedList was addressed by introducing a new covariant override for reversed() specific to LinkedList.
• The internal IdentityLinkedList class, which was deemed unnecessary, has been removed.

Balancing Risks and Benefits

An earlier proposal considered covariant overrides for the keySet(), values(), and entrySet() methods of SequencedMap. However, this approach carried a high risk of breaking existing subclasses due to the significant change in behavior.

As a result, the developers opted for a safer approach:

• introducing new methods: sequencedKeySet(), sequencedValues(), and sequencedEntrySet() were added to SequencedMap. 

This avoided modifying existing methods and minimized potential incompatibilities.

Conclusions

The developers of sequenced collections carefully considered potential risks and made informed decisions to minimize disruption and maintain compatibility with existing codebases. While some adjustments were required (as with LinkedList), the overall approach ensured a smoother transition to a more consistent way of handling ordered collections in Java.

---

Main Author: Luigi Cerrato, Software Engineer @ Bitrock