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

Method	Description
`add(E e)`	Adds an element if not already present
`remove(Object o)`	Removes an element
`contains(Object o)`	Checks if an element exists
`size()`	Returns number of elements
`isEmpty()`	Checks if set is empty
`first()`	Returns the first (lowest) element
`last()`	Returns the last (highest) element
`lower(E e)`	Greatest element < e
`floor(E e)`	Greatest element ≤ e
`ceiling(E e)`	Smallest element ≥ e
`higher(E e)`	Smallest element > e
`pollFirst()`	Removes and returns the first element
`pollLast()`	Removes and returns the last element
`iterator()`	Returns iterator in ascending order
`descendingIterator()`	Returns iterator in descending order
`subSet(E from, boolean fromInclusive, E to, boolean toInclusive)`	Returns a subset view
`headSet(E to, boolean inclusive)`	Returns head set view
`tailSet(E from, boolean inclusive)`	Returns tail set view

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:

Operation	Time
add()	O(log n)
remove()	O(log n)
contains()	O(log n)

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

Feature	TreeSet	ConcurrentNavigableSet
Thread-safe	No	Yes
Fail-safe iterator	No	Yes (weakly consistent)
Backed by	Red-black tree	Skip-list
Best for	Single-thread	Multi-thread
Order	Sorted	Sorted + navigable

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