Java ConcurrentSkipListMap: ordered concurrent lookups and live ranges

Java 8+. This is a complete program using JDK classes.

Order is a requirement, not a bonus

A dispatch board needs the next due job and a range of jobs before a cutoff. A plain concurrent hash map supplies independent keyed operations but does not supply sorted nearest-key queries. This board needs an ordered map contract.

A subMap is a range view backed by the original map. Removing a job through the view removes that mapping from the board. Keep a copied snapshot when a report must stay unchanged after it is handed to another component; a live range means later updates can be visible.

Individual concurrent operations still do not make a multi-step decision atomic. Checking a value and then removing a key can remove a newer replacement. Use a conditional remove(key, expectedValue) for that claim, and decide how the caller handles a failed claim.

Settle identity and comparison

Comparator equivalence decides whether two sorted keys occupy the same position. Include the necessary tie-breaker if two jobs with the same due time must remain distinct. Null keys and values are not accepted here, so absence cannot be represented by inserting a null mapping.

Working program

import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ConcurrentNavigableMap;
public class DueJobBoard {
    public static void main(String[] args) {
        ConcurrentSkipListMap<Integer, String> jobs = new ConcurrentSkipListMap<>();
        jobs.put(30, "dispatch-30"); jobs.put(10, "dispatch-10"); jobs.put(20, "dispatch-20");
        System.out.println(jobs.ceilingKey(15));
        ConcurrentNavigableMap<Integer, String> early = jobs.headMap(25, false);
        System.out.println(early.keySet());
        System.out.println(jobs.remove(20, "dispatch-20"));
        System.out.println(early.keySet());
    }
}

Output

20
[10, 20]
true
[10]

Costs and boundaries

Search, insertion and removal have expected O(log n) cost. A traversal costs work proportional to the visited mappings and is not a transactional snapshot. Copying a report adds O(k) entries for a range of k keys and still shares mutable values unless copied separately.

Common Mistakes

• Do not treat a weakly consistent traversal as an atomic report.
• A backed range is not independent storage.
• A key-only removal can discard a replacement inserted by another worker.

Read next

Sorted map decisions, Concurrent hash operations.