Sorted collection in Java

java

collections

performance

best-practices

byAlex Kataev·Dec 22, 2024

For sorted sets in Java, use TreeSet, and for sorted key-value pairs, opt for TreeMap. They automatically sort items and allow for logarithmic time complexity with most operations. Here is a TreeSet example:

Set<Integer> sortedSet = new TreeSet<>(Arrays.asList(3, 1, 2));
System.out.println(sortedSet); // [1, 2, 3] Who said maths was complicated?

Check out this TreeMap example:

Map<Integer, String> sortedMap = new TreeMap<>();
sortedMap.put(3, "C");
sortedMap.put(1, "A");
sortedMap.put(2, "B");
System.out.println(sortedMap.keySet()); // [1, 2, 3] Now that's a perfectly ordered sequence!
System.out.println(sortedMap.values()); // [A, B, C] And a perfect ABC order!

Both structures sort by natural order or can be custom sorted via a Comparator.

Choose your tool: Describing collection types

Real-time sorting: `PriorityQueue`

For real-time needs, the PriorityQueue is a powerhouse. While sacrificing indexed access, it compensates with O(log(n)) insertion time and order maintenance via Comparable or Comparator implementations.

Changing lists: `ArrayList` with `Collections.sort()`

Frequently modified collections? ArrayList and Collections.sort() is your dynamic duo. It even supports efficient item search thanks to Collections.binarySearch().

Duplicate-friendly: Guava's `TreeMultiset`

For collections accommodating duplicate items, the TreeMultiset from Google's Guava library is a smart choice, especially when you appreciate extra API functionality beyond standard Java Collections.

Dig deeper: Advanced usage and insights

`Comparable` and `Comparator` for custom sorting

When dealing with custom objects, embrace Comparable and Comparator to navigate through collections like TreeSet or PriorityQueue:

PriorityQueue<CustomObject> queue = new PriorityQueue<>(new CustomObjectComparator());

Trade-offs: Performance considerations

Choosing the right collection pays back in performance. TreeSet restricts elements to uniqueness but keeps them sorted, while ArrayList flexes its muscles in handling frequent modifications.

Adventurous choice: Alternative libraries

The standard libraries are great but don't limit yourself. Be adventurous with Google Guava and explore advanced collections like TreeMultiset.

Binary Search: Speedy retrieval in `ArrayList`

While ArrayList doesn't provide direct access to sorted order, it doesn't shy away from utilizing binarySearch() after being sorted by Collections.sort():

Collections.sort(list);
int index = Collections.binarySearch(list, key); // Where are you, key?

`Comparable` and `Comparator`: Custom object sorting

In a world of custom objects, ensure they play nice with Comparable or via a Comparator with TreeSet, keeping your collection in consistent order.

Multi-criteria sorting: Chained comparators

When one attribute isn't enough, bring out the big guns—chained comparators. Sort by multiple criteria, because why settle for less?

sortedSet = new TreeSet<>(Comparator.comparing(CustomObject::getPrimaryField)
                                     .thenComparing(CustomObject::getSecondaryField)); // Double the fun!

explain-codes / Java / Sorted collection in Java

Linked

Big-o summary for Java Collections Framework implementations?



How to retrieve a single entry from a HashMap without iterating



Intersection and union of ArrayLists in Java



Java 8 Distinct by property



Sort a Map by values

