Sometime back I’ve written an article on difference between HashMap, ConcurentHashMap and SynchronizedMap. In this tutorial we will go over ConcurrentNavigableMap and ConcurrentSkipListMap with all detailed explanation.
Do you have any of below questions?
- Comparing ConcurrentHashMap v/s ConcurrentSkipListMap
- Java ConcurrentSkipListMap Tutorial
- TreeMap vs ConcurrentSkipListMap
- ConcurrentHashMap or LinkedHashMap
Why SkipListMap in Java?
As per a wiki page, SkipList is a data structure which is sorted and allow fast search concurrently. All the elements are sorted based on their natural sorting order of keys. In our tutorial we will create an object crunchifyCompanyMap with below signature.
ConcurrentNavigableMap<Integer, String> crunchifyCompanyMap = new ConcurrentSkipListMap<Integer, String>();
Next we will add 5 different elements to crunchifyCompanyMap. Key would be the random integer numbers and value would be the Company Name.
In our tutorial we will go over number of different operations performed on ConcurrentSkipListMap.
package crunchify.com.tutorial;
import java.util.Iterator;
import java.util.NavigableSet;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.ConcurrentSkipListMap;
/**
* @author Crunchify.com
* Simple java ConcurrentNavigableMap and ConcurrentSkipListMap Tutorial
*/
public class CrunchifySkipListMap {
public static void main(String[] args) {
// ConcurrentNavigableMap: A ConcurrentMap supporting NavigableMap operations, and recursively so for its navigable
// sub-maps.
// ConcurrentSkipListMap: Constructs a new, empty map, sorted according to the natural ordering of the keys.
ConcurrentNavigableMap<Integer, String> crunchifyCompanyMap = new ConcurrentSkipListMap<Integer, String>();
crunchifyCompanyMap.put(100, "Crunchify");
crunchifyCompanyMap.put(250, "Google");
crunchifyCompanyMap.put(300, "Apple");
crunchifyCompanyMap.put(275, "Facebook");
crunchifyCompanyMap.put(325, "Twitter"); // NOTE: these are sample numbers
log("Let's get ceilingEntry: " + crunchifyCompanyMap.ceilingKey(200)); // Returns a key-value mapping associated with
// the least key greater than or equal to the
// given key
log("Let's get firstKey: " + crunchifyCompanyMap.firstKey()); // Returns the first (lowest) key
log("Let's get lastEntry: " + crunchifyCompanyMap.lastEntry()); // Returns greatest key
log("Let's get floorEntry: " + crunchifyCompanyMap.floorKey(320)); // Returns the greatest key less than or equal to the
// given key
NavigableSet<Integer> crunchifyNavSet = crunchifyCompanyMap.descendingKeySet(); // Returns a reverse order NavigableSet
// view of the keys contained in this map.
log("\nHere is a Reverse order NavigableSet ~~~~~~~~~~~~~~~~ ");
Iterator<Integer> crunchifyIterator = crunchifyNavSet.iterator(); // Standard Java Iterator
while (crunchifyIterator.hasNext()) { // Returns true if the iteration has more elements
Integer mapKey = crunchifyIterator.next();
log(mapKey.toString());
}
log("\nLet's do some deugging ~~~~~~~~~~~~~~~~");
log("pollFirstEntry: " + crunchifyCompanyMap.pollFirstEntry()); // Removes and returns a key-value mapping associated with
// the least key in this map
log("now firstEntry: " + crunchifyCompanyMap.firstEntry());
log("pollLastEntry: " + crunchifyCompanyMap.pollLastEntry()); // Removes and returns a key-value mapping associated with
// the greatest key in this map
log("now lastEntry: " + crunchifyCompanyMap.lastEntry());
}
private static void log(String result) {
System.out.println(result);
}
}
Eclipse Console Output:
Let's get ceilingEntry: 250 Let's get firstKey: 100 Let's get lastEntry: 325=Twitter Let's get floorEntry: 300 Here is a Reverse order NavigableSet ~~~~~~~~~~~~~~~~ 325 300 275 250 100 Let's do some deugging ~~~~~~~~~~~~~~~~ pollFirstEntry: 100=Crunchify now firstEntry: 250=Google pollLastEntry: 325=Twitter now lastEntry: 300=Apple
ConcurrentHashMap and ConcurrentSkipListMap Comparison
- ConcurrentSkipListMap guarantees
O(log(n))time complexity performance for most of its operations like firstKey, firstEntry, lastEntry, pollFirstEntry, pollLastEntry, etc. - ConcurrentSkipListMap does not allow to modify the concurrent thread count.
- ConcurrentSkipListMap is both a NavigableMap and a SortedMap (like Java Set).
- ConcurrentSkipListMap is a Skip List.
When to use ConcurrentSkipListMap?
So basically, if you need faster in-order traversal, and if you are totally fine for an extra cost for insertion, use the ConcurrentSkipListMap. Data will be sorted by default. You could also use TreeMap if you don’t need to use object in concurrent environment.
TreeMap & ConcurrentSkipListMap Comparison
- TreeMap is not synchronized
- The iterators returned by the iterator() method of Map’s “collection view methods” are fail-fast. means any structural modification made to TreeMap during iteration using any of 3 Iterator will throw ConcurrentModificationException.
- Both are sorted by natural order.
- Both doesn’t allow NULL in Key but you could put more NULL in Value.
O(lon(n))complexity.
ConcurrentHashMap & LinkedHashMap Comparison
- LinkedHashMap is ordered but not thread safe
- The ConcurrentHashMap is thread safe but not ordered
Here is an Eclipse Debug result for above Java program:
