Section 16.5. ConcurrentNavigableMap

16.5. ConcurrentNavigableMap

ConcurrentNavigableMap (see Figure 16.7) inherits from both ConcurrentMap and NavigableMap, and contains just the methods of these two interfaces with a few changes to make the return types more precise. The range-view methods inherited from SortedMap and NavigableMap now return views of type ConcurrentNavigableMap. The compatibility concerns that prevented NavigableMap from overriding the methods of SortedMap don't apply here to overriding the range-view methods of NavigableMap or SortedMap; because neither of these has any implementations that have been retrofitted to the new interface, the danger of breaking implementation subclasses does not arise. For the same reason, it is now possible to override keySet to return NavigableSet.

Figure 16-7. ConcurrentNavigableMap

16.5.1. ConcurrentSkipListMap

The relationship between ConcurrentSkipListMap and ConcurrentSkipListSet is like that between treeMap and TReeSet; a ConcurrentSkipListSet is implemented by a ConcurrentSkipListMap in which every key is associated with the same standard value, so the mechanism and performance of the skip list implementation given in Section 13.2.2 applies equally here: the basic operations (get, put, and remove) perform in O(log n) time); iterators over the collection views execute next in constant time. These iterators are fail-fast.