In Java’s ever-evolving concurrent programming landscape, thread-safe data structures play a critical role in building robust, scalable, and efficient applications. Two such powerful constructs are ConcurrentNavigableMap and its primary implementation, ConcurrentSkipListMap. These classes provide thread-safe access to sorted key-value pairs, making them highly suitable for applications that demand concurrent access, ordered traversal, and high performance.
ConcurrentNavigableMap
ConcurrentNavigableMap is an interface introduced in the java.util.concurrent package. It is a subinterface of ConcurrentMap and also extends NavigableMap. This combination endows it with all the characteristics of a concurrent map while also supporting navigational methods. As a result, developers can perform standard map operations such as put, get, and remove while also utilizing range-based and ordering-based operations like subMap, headMap, tailMap, firstKey, and lastKey.
The key strength of ConcurrentNavigableMap lies in its ability to allow safe and efficient access from multiple threads without external synchronization. Its methods are designed to work atomically, ensuring consistency and thread-safety even under heavy concurrency.
The Role of ConcurrentSkipListMap
ConcurrentSkipListMap is the primary and most commonly used implementation of ConcurrentNavigableMap. It is a scalable, concurrent, and sorted map that maintains entries in ascending key order. Internally, it uses a data structure called a Skip List, which is a probabilistic alternative to balanced trees like Red-Black Trees. Skip Lists allow logarithmic time complexity for basic operations such as insertion, deletion, and search by maintaining multiple levels of linked lists with different strides.
The skip list structure is particularly well-suited for concurrent environments because it supports fine-grained locking or even lock-free algorithms, depending on implementation. In ConcurrentSkipListMap, the operations are designed to be non-blocking wherever possible, allowing multiple threads to read and update the map concurrently without corrupting the data.
Important Features and Advantages
One of the core advantages of ConcurrentSkipListMap over other concurrent map implementations, such as ConcurrentHashMap, is that it maintains the natural ordering of keys or a custom comparator-defined order. This makes it ideal for scenarios where sorted data is required. Furthermore, all of its navigational methods, such as ceilingKey, floorKey, lowerKey, higherKey, and various sub-map views, are fully supported and thread-safe.
Another significant advantage is its scalability. The design of the skip list allows for multiple threads to work on different parts of the map concurrently. This leads to better performance in high-throughput systems compared to synchronized map implementations like Collections.synchronizedSortedMap.
Additionally, ConcurrentSkipListMap supports a lock-free read operation model in many of its read-only methods, enabling extremely fast data access even under concurrent modification.
Use Cases in Real-World Applications
There are numerous real-world use cases where ConcurrentNavigableMap and ConcurrentSkipListMap are particularly beneficial. For instance:
- Leaderboards and Rankings: Applications that maintain real-time rankings based on scores can benefit from the natural ordering and fast updates provided by
ConcurrentSkipListMap. - Event Scheduling Systems: Systems that need to process events in order of timestamps can use
ConcurrentSkipListMapto store events, ensuring that they are retrieved and processed in the correct order. - Financial Systems: In stock trading applications or banking systems where operations are sensitive to timing and order, maintaining a sorted and concurrently accessible data structure is crucial.
- Task Scheduling: Background processing systems that manage scheduled tasks based on execution time or priority can use a
ConcurrentSkipListMapto efficiently sort and retrieve tasks.
ConcurrentNavigableMap inteface Syntax and methods
package java.util.concurrent;
import java.util.Map;
import java.util.NavigableMap;
public interface ConcurrentNavigableMap<K, V> extends ConcurrentMap<K, V>, NavigableMap<K, V> {
// Methods from NavigableMap
K firstKey(); // Returns the first (lowest) key in the map.
K lastKey(); // Returns the last (highest) key in the map.
Map.Entry<K, V> firstEntry(); // Returns the first (lowest) entry in the map.
Map.Entry<K, V> lastEntry(); // Returns the last (highest) entry in the map.
Map.Entry<K, V> pollFirstEntry(); // Removes and returns the first (lowest) entry in the map.
Map.Entry<K, V> pollLastEntry(); // Removes and returns the last (highest) entry in the map.
K lowerKey(K key); // Returns the greatest key strictly less than the given key.
K floorKey(K key); // Returns the greatest key less than or equal to the given key.
K ceilingKey(K key); // Returns the least key greater than or equal to the given key.
K higherKey(K key); // Returns the least key strictly greater than the given key.
NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); // Returns a view of the portion of this map whose keys range from fromKey to toKey.
NavigableMap<K, V> headMap(K toKey, boolean inclusive); // Returns a view of the portion of this map whose keys are less than (or equal to) the specified key.
NavigableMap<K, V> tailMap(K fromKey, boolean inclusive); // Returns a view of the portion of this map whose keys are greater than (or equal to) the specified key.
NavigableMap<K, V> descendingMap(); // Returns a view of the map in reverse order.
// Methods from ConcurrentMap
V putIfAbsent(K key, V value); // Inserts the specified key-value pair if the key is not already present in the map.
boolean remove(Object key, Object value); // Removes the key-value pair if the key is present with the specified value.
boolean replace(K key, V oldValue, V newValue); // Replaces the old value with the new value if the current value is equal to the old value.
V replace(K key, V value); // Replaces the value associated with the specified key.
// Additional Methods from Map Interface
V get(Object key); // Returns the value associated with the specified key.
boolean containsKey(Object key); // Returns true if the map contains the specified key.
boolean containsValue(Object value); // Returns true if the map contains the specified value.
void clear(); // Removes all key-value pairs from the map.
int size(); // Returns the number of key-value pairs in the map.
boolean isEmpty(); // Returns true if the map is empty.
Set<K> keySet(); // Returns a set of all keys in the map.
Collection<V> values(); // Returns a collection of all values in the map.
Set<Map.Entry<K, V>> entrySet(); // Returns a set view of the key-value mappings in the map.
// Other methods as per your application need.
}Code language: PHP (php)ConcurrentSkipListMap is a concrete implementation of above ConcurrentNavigableMap.All methods of above interface are implemented in this class.
Program
This program is to demonstrate the usage of the ConcurrentSkipListMap class in Java, which is part of the java.util.concurrent package. The task involves managing a collection of river names and their corresponding lengths (in kilometers) using a thread-safe, sorted map. The program should showcase various operations such as adding, removing, and updating entries, as well as demonstrating the use of methods for navigating the map (e.g., submap retrieval, finding nearest entries based on keys, and accessing the first and last entries). Additionally, the program should highlight how to handle ranges of keys using the ConcurrentNavigableMap interface, and how thread-safe operations are supported in a multi-threaded environment.
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
public class ConcurrentSkipListMapDemo {
public static void main(String[] args) {
ConcurrentSkipListMap<Integer, String> riversMap = new ConcurrentSkipListMap<>();
riversMap.put(2525, "Ganges");
riversMap.put(1375, "Yamuna");
riversMap.put(3120, "Godavari");
riversMap.put(1465, "Narmada");
riversMap.put(1376, "Krishna");
System.out.println("Initial Rivers Map: " + riversMap);
ConcurrentNavigableMap<Integer, String> subMap = riversMap.subMap(1000, true, 2000, true);
System.out.println("SubMap (1000 to 2000 km): " + subMap);
System.out.println("Longest River: " + riversMap.lastEntry());
System.out.println("Shortest River: " + riversMap.firstEntry());
System.out.println("River shorter than 1465 km: " + riversMap.lowerEntry(1465));
System.out.println("River shorter or equal to 1465 km: " + riversMap.floorEntry(1465));
System.out.println("River longer or equal to 1465 km: " + riversMap.ceilingEntry(1465));
System.out.println("River longer than 1465 km: " + riversMap.higherEntry(1465));
riversMap.remove(1375);
System.out.println("Map after removing Yamuna: " + riversMap);
riversMap.put(4050, "Indus");
System.out.println("Map after adding Indus: " + riversMap);
System.out.println("River shorter than 2525 km: " + riversMap.lowerEntry(2525));
System.out.println("River longer than 2525 km: " + riversMap.higherEntry(2525));
}
}
/*
C:\>javac ConcurrentSkipListMapDemo.java
C:\>java ConcurrentSkipListMapDemo
Initial Rivers Map: {1375=Yamuna, 1376=Krishna, 1465=Narmada, 2525=Ganges, 3120=Godavari}
SubMap (1000 to 2000 km): {1375=Yamuna, 1376=Krishna, 1465=Narmada}
Longest River: 3120=Godavari
Shortest River: 1375=Yamuna
River shorter than 1465 km: 1376=Krishna
River shorter or equal to 1465 km: 1465=Narmada
River longer or equal to 1465 km: 1465=Narmada
River longer than 1465 km: 2525=Ganges
Map after removing Yamuna: {1376=Krishna, 1465=Narmada, 2525=Ganges, 3120=Godavari}
Map after adding Indus: {1376=Krishna, 1465=Narmada, 2525=Ganges, 3120=Godavari, 4050=Indus}
River shorter than 2525 km: 1465=Narmada
River longer than 2525 km: 3120=Godavari
*/
The ConcurrentNavigableMap interface and its implementation, ConcurrentSkipListMap, provide an efficient and thread-safe solution for managing and navigating through sorted maps in concurrent applications. ConcurrentSkipListMap ensures that operations such as insertion, deletion, and retrieval of elements are performed safely in a multi-threaded environment, without the need for explicit synchronization. It supports advanced navigational operations like submap creation, range-based searches, and key comparisons, which are essential for efficiently managing sorted data.