ConcurrentNavigableSet in Java

ConcurrentNavigableSet is a thread-safe, sorted, and navigable Set interface introduced in Java 6.

It extends NavigableSet and adds support for concurrent access without external synchronization.

It belongs to:

java.util.concurrent package.

What Is ConcurrentNavigableSet?

It is a sorted set that supports:

• Concurrent operations safely
• Lock-free / scalable performance
• Sorted order (natural or custom comparator)
• Navigation methods (like ceiling, floor, subSet, headSet, etc.)

It is similar to TreeSet, but:

• TreeSet → NOT thread-safe
• ConcurrentNavigableSet → thread-safe (non-blocking, high performance)

Hierarchy of ConcurrentNavigableSet

Iterable
   │
Collection
   │
Set
   │
SortedSet
   │
NavigableSet
   │
ConcurrentNavigableSet   ← Interface
         │
         └── Implemented By:
                └── ConcurrentSkipListSet (Class)

Only concrete implementation → ConcurrentSkipListSet

Features of ConcurrentNavigableSet

1. Thread-Safe

Multiple threads can read/write simultaneously.

2. Sorted Set

Maintains ascending order (or custom comparator).

3. Navigable Operations

Includes:

• ceiling(E e)
• floor(E e)
• higher(E e)
• lower(E e)
• subSet(E from, E to)
• headSet(E toElement)
• tailSet(E fromElement)

4. Non-blocking / Lock-free

Internally uses ConcurrentSkipListMap → skip-list based.

5. Weakly Consistent Iterator

Iterator:

• Never throws ConcurrentModificationException
• Reflects some (not all) changes while iterating

6. High performance for concurrent apps

Better than synchronized TreeSet.

Common Methods of ConcurrentNavigableSet

Example

import java.util.concurrent.ConcurrentNavigableSet;
import java.util.concurrent.ConcurrentSkipListSet;

public class Main {
    public static void main(String[] args) {
        ConcurrentNavigableSet<Integer> set = new ConcurrentSkipListSet<>();

        set.add(10);
        set.add(30);
        set.add(20);
        set.add(40);

        System.out.println("Set: " + set);

        // Navigable methods
        System.out.println("Lower than 25: " + set.lower(25));   // 20
        System.out.println("Floor of 30: " + set.floor(30));     // 30
        System.out.println("Ceiling of 25: " + set.ceiling(25)); // 30
        System.out.println("Higher than 30: " + set.higher(30)); // 40

        // Polling elements
        System.out.println("Poll First: " + set.pollFirst());    // 10
        System.out.println("Poll Last: " + set.pollLast());      // 40

        System.out.println("Updated Set: " + set);
    }
}

Output:

Set: [10, 20, 30, 40]
Lower than 25: 20
Floor of 30: 30
Ceiling of 25: 30
Higher than 30: 40
Poll First: 10
Poll Last: 40
Updated Set: [20, 30]

Internal Working

• Backed by a skip-list data structure

  (multi-level linked structure for fast searching)

• Ordered keys like TreeMap

• But operations are lock-free or minimal-lock

Skiplist complexity:

Creating a ConcurrentNavigableSet

It is an interface → you use ConcurrentSkipListSet.

Example

ConcurrentNavigableSet<Integer> set =
        new ConcurrentSkipListSet<>();

SubSet / HeadSet / TailSet Example

ConcurrentNavigableSet<Integer> set =
        new ConcurrentSkipListSet<>();

set.add(10);
set.add(20);
set.add(30);
set.add(40);

System.out.println(set.subSet(10, 30));   // [10, 20]
System.out.println(set.headSet(30));      // [10, 20]
System.out.println(set.tailSet(20));      // [20, 30, 40]

When to Use ConcurrentNavigableSet?

Use it when you need:

• Thread-safe sorted set
• Range operations (subSet, headSet, tailSet)
• High concurrency
• Non-blocking iterators
• Alternative to synchronized TreeSet

Perfect for:

• Real-time applications
• Messaging queues
• Leaderboards
• Concurrent scheduling
• Caches

ConcurrentNavigableSet vs TreeSet

Points To Remember

ConcurrentNavigableSet = Thread-safe, sorted, and navigable set backed by ConcurrentSkipListSet.

• Allows high-concurrency operations
• Maintains ascending order
• Supports navigable and subset operations
• Iterators are weakly consistent, safe for concurrent access