A concurrent ConcurrentNavigableMap implementation.
This class implements a Copy-on-Write (CoW) variant of a Red-black Tree, the same algorithm used in TreeMap, providing expected log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads.
Unlike other copy-on-write TreeMap implementations that copy all underlying nodes, this implementation copies only the nodes that are necessary (path copying) and swaps the root atomically.
This means that iterators and spliterators are strongly consistent and do not throw ConcurrentModificationException, but they do not reflect modifications made to the map after the creation of an iterator or spliterator instance.
The CopyOnWriteTreeMap class can be copied as a drop-in replacement for TreeMap in your Java applications. You can find it in here.
The class itself implements the ConcurrentNavigableMap, Clonable, and Serializable interfaces, so it can be used wherever a ConcurrentNavigableMap is expected.
To ensure the correctness of the implementation, tests from openjdk have been adapted to include CopyOnWriteTreeMap whenever TreeMap, or ConcurrentSkipListMap is used. Including a JSR166 tests for CopyOnWriteTreeMap and its submap implementation. (Found in test/java/com/casperswebsites/util/concurrent).
The performance is compared to