APIdia Launch Partner
Top Description Inners Fields Constructors Methods
java.util.concurrent

public Class ConcurrentSkipListMap<K, V>

extends AbstractMap<K, V>
implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable, java.lang.Cloneable, java.util.concurrent.ConcurrentNavigableMap, java.util.NavigableMap, java.util.SortedMap, java.util.SequencedMap, java.util.Map, java.util.concurrent.ConcurrentMap
Type Parameters
<K>
the type of keys maintained by this map
<V>
the type of mapped values
Imports
java.lang.invoke.MethodHandles, .VarHandle, java.io.Serializable, java.util.AbstractCollection, .AbstractMap, .AbstractSet, .ArrayList, .Collection, .Collections, .Comparator, .Iterator, .List, .Map, .NavigableSet, .NoSuchElementException, .Set, .SortedMap, .Spliterator, java.util.function.BiConsumer, .BiFunction, .Consumer, .Function, .Predicate, java.util.concurrent.atomic.LongAdder
A scalable concurrent ConcurrentNavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This class implements a concurrent variant of SkipLists providing expected average 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.

Iterators and spliterators are weakly consistent.

Ascending key ordered views and their iterators are faster than descending ones.

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put, putIfAbsent, or replace, depending on exactly which effect you need.)

Beware that bulk operations putAll, equals, toArray, containsValue, and clear are not guaranteed to be performed atomically. For example, an iterator operating concurrently with a putAll operation might view only some of the added elements.

This class and its views and iterators implement all of the optional methods of the Map and Iterator interfaces. Like most other concurrent collections, this class does not permit the use of null keys or values because some null return values cannot be reliably distinguished from the absence of elements.

This class is a member of the Java Collections Framework.

Author
Doug Lea
Since
1.6

Nested and Inner Type Summary

Modifier and TypeClass and Description
pack-priv abstract static class
ConcurrentSkipListMap.CSLMSpliterator<K, V>

Base class providing common structure for Spliterators.

pack-priv class
ConcurrentSkipListMap.EntryIterator

pack-priv static class
ConcurrentSkipListMap.EntrySet<K, V>

pack-priv static class
ConcurrentSkipListMap.EntrySpliterator<K, V>

pack-priv static class
ConcurrentSkipListMap.Index<K, V>

Index nodes represent the levels of the skip list.

pack-priv abstract class
ConcurrentSkipListMap.Iter<T>

Base of iterator classes

pack-priv class
ConcurrentSkipListMap.KeyIterator

pack-priv static class
ConcurrentSkipListMap.KeySet<K, V>

pack-priv static class
ConcurrentSkipListMap.KeySpliterator<K, V>

pack-priv static class
ConcurrentSkipListMap.Node<K, V>

Nodes hold keys and values, and are singly linked in sorted order, possibly with some intervening marker nodes.

pack-priv static class
ConcurrentSkipListMap.SubMap<K, V>

Submaps returned by ConcurrentSkipListMap submap operations represent a subrange of mappings of their underlying maps.

pack-priv class
ConcurrentSkipListMap.ValueIterator

pack-priv static class
ConcurrentSkipListMap.Values<K, V>

pack-priv static class
ConcurrentSkipListMap.ValueSpliterator<K, V>

Field Summary

Modifier and TypeField and Description
private transient LongAdder
adder

Lazily initialized element count

private static final VarHandle
ADDER

pack-priv final Comparator<? super K>
comparator

The comparator used to maintain order in this map, or null if using natural ordering.

private transient ConcurrentSkipListMap.SubMap<K, V>
descendingMap

Lazily initialized descending map

private transient ConcurrentSkipListMap.EntrySet<K, V>
entrySet

Lazily initialized entry set

private static final int
EQ

private static final int
GT

private transient ConcurrentSkipListMap.Index<K, V>
head

Lazily initialized topmost index of the skiplist.

private static final VarHandle
HEAD

private transient ConcurrentSkipListMap.KeySet<K, V>
keySet

Hides java.util.AbstractMap.keySet.

Lazily initialized key set
private static final int
LT

private static final VarHandle
NEXT

private static final VarHandle
RIGHT

private static final long
serialVersionUID

private static final VarHandle
VAL

private transient ConcurrentSkipListMap.Values<K, V>
values

Hides java.util.AbstractMap.values.

Lazily initialized values collection

Constructor Summary

AccessConstructor and Description
public
ConcurrentSkipListMap()

Constructs a new, empty map, sorted according to the natural ordering of the keys.

public
ConcurrentSkipListMap(Comparator<? super K>
the comparator that will be used to order this map. If null, the natural ordering of the keys will be used.
comparator)

Constructs a new, empty map, sorted according to the specified comparator.

public
ConcurrentSkipListMap(Map<? extends K, ? extends V>
the map whose mappings are to be placed in this map
m)

Constructs a new map containing the same mappings as the given map, sorted according to the natural ordering of the keys.

public
ConcurrentSkipListMap(SortedMap<K, ? extends V>
the sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map
m)

Constructs a new map containing the same mappings and using the same ordering as the specified sorted map.

Method Summary

Modifier and TypeMethod and Description
private void
addCount(long
count to add
c)

Adds to element count, initializing adder if necessary

pack-priv static <K, V> boolean
addIndices(ConcurrentSkipListMap.Index<K, V>
starting index for current level
q, int
levels to skip before inserting
skips, ConcurrentSkipListMap.Index<K, V>
index for this insertion
x, Comparator<? super K>
comparator
cmp)

Add indices after an insertion.

pack-priv final ConcurrentSkipListMap.Node<K, V>
baseHead()

Returns the header for base node list, or null if uninitialized

private void
buildFromSorted(SortedMap<K, ? extends V> map)

Streamlined bulk insertion to initialize from elements of given sorted map.

public Map.Entry<K, V>
ceilingEntry(K key)

Implements java.util.NavigableMap.ceilingEntry.

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such entry.

public K
ceilingKey(K key)

Implements java.util.NavigableMap.ceilingKey.

Returns the least key greater than or equal to the given key, or null if there is no such key.

public void
clear()

Overrides java.util.AbstractMap.clear.

Implements java.util.Map.clear.

Removes all of the mappings from this map.

public ConcurrentSkipListMap<K, V>

Returns:

a shallow copy of this map
clone()

Overrides java.util.AbstractMap.clone.

Returns a shallow copy of this ConcurrentSkipListMap instance.

public Comparator<? super K>
comparator()

Implements java.util.SortedMap.comparator.

Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.

public V

Returns:

the new value associated with the specified key, or null if none
compute(K
key with which the specified value is to be associated
key, BiFunction<? super K, ? super V, ? extends V>
the function to compute a value
remappingFunction)

Overrides default java.util.concurrent.ConcurrentMap.compute, java.util.Map.compute.

Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).

public V

Returns:

the current (existing or computed) value associated with the specified key, or null if the computed value is null
computeIfAbsent(K
key with which the specified value is to be associated
key, Function<? super K, ? extends V>
the function to compute a value
mappingFunction)

Overrides default java.util.concurrent.ConcurrentMap.computeIfAbsent, java.util.Map.computeIfAbsent.

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null.

public V

Returns:

the new value associated with the specified key, or null if none
computeIfPresent(K
key with which a value may be associated
key, BiFunction<? super K, ? super V, ? extends V>
the function to compute a value
remappingFunction)

Overrides default java.util.concurrent.ConcurrentMap.computeIfPresent, java.util.Map.computeIfPresent.

If the value for the specified key is present, attempts to compute a new mapping given the key and its current mapped value.

public boolean

Returns:

true if this map contains a mapping for the specified key
containsKey(Object
key whose presence in this map is to be tested
key)

Overrides java.util.AbstractMap.containsKey.

Implements java.util.Map.containsKey.

Returns true if this map contains a mapping for the specified key.

public boolean

Returns:

true if a mapping to value exists; false otherwise
containsValue(Object
value whose presence in this map is to be tested
value)

Overrides java.util.AbstractMap.containsValue.

Implements java.util.Map.containsValue.

Returns true if this map maps one or more keys to the specified value.

pack-priv static int
cpr(Comparator<T> c, Object x, Object y)

Compares using comparator or natural ordering if null.

public NavigableSet<K>
descendingKeySet()

Implements java.util.concurrent.ConcurrentNavigableMap.descendingKeySet.

Returns a reverse order NavigableSet view of the keys contained in this map.

public ConcurrentNavigableMap<K, V>
descendingMap()

Implements java.util.concurrent.ConcurrentNavigableMap.descendingMap.

Returns a reverse order view of the mappings contained in this map.

private V

Returns:

the value, or null if absent
doGet(Object
the key
key)

Gets value for key.

private V

Returns:

the old value, or null if newly inserted
doPut(K
the key
key, V
the value that must be associated with key
value, boolean
if should not insert if already present
onlyIfAbsent)

Main insertion method.

pack-priv final V

Returns:

the node, or null if not found
doRemove(Object
the key
key, Object
if non-null, the value that must be associated with key
value)

Main deletion method.

private AbstractMap.SimpleImmutableEntry<K, V>

Returns:

null if empty, else snapshot of first entry
doRemoveFirstEntry()

Removes first entry; returns its snapshot.

private Map.Entry<K, V>

Returns:

null if empty, else snapshot of last entry
doRemoveLastEntry()

Removes last entry; returns its snapshot.

public Set<Map.Entry<K, V>>

Returns:

a set view of the mappings contained in this map, sorted in ascending key order
entrySet()

Implements abstract java.util.AbstractMap.entrySet.

Implements java.util.Map.entrySet, java.util.SortedMap.entrySet.

Returns a Set view of the mappings contained in this map.

pack-priv final ConcurrentSkipListMap.EntrySpliterator<K, V>
entrySpliterator()

public boolean

Returns:

true if the specified object is equal to this map
equals(Object
object to be compared for equality with this map
o)

Overrides java.util.AbstractMap.equals.

Implements java.util.Map.equals.

Compares the specified object with this map for equality.

pack-priv final ConcurrentSkipListMap.Node<K, V>

Returns:

first node or null if empty
findFirst()

Gets first valid node, unlinking deleted nodes if encountered.

pack-priv final AbstractMap.SimpleImmutableEntry<K, V>
findFirstEntry()

Entry snapshot version of findFirst

pack-priv final ConcurrentSkipListMap.Node<K, V>

Returns:

last node or null if empty
findLast()

Specialized version of find to get last valid node.

pack-priv final AbstractMap.SimpleImmutableEntry<K, V>

Returns:

Entry for last node or null if empty
findLastEntry()

Entry version of findLast

pack-priv final ConcurrentSkipListMap.Node<K, V>

Returns:

nearest node fitting relation, or null if no such
findNear(K
the key
key, int
the relation -- OR'ed combination of EQ, LT, GT
rel, Comparator<? super K> cmp)

Utility for ceiling, floor, lower, higher methods.

pack-priv final AbstractMap.SimpleImmutableEntry<K, V>

Returns:

Entry fitting relation, or null if no such
findNearEntry(K
the key
key, int
the relation -- OR'ed combination of EQ, LT, GT
rel, Comparator<? super K> cmp)

Variant of findNear returning SimpleImmutableEntry

private ConcurrentSkipListMap.Node<K, V>

Returns:

node holding key, or null if no such
findNode(Object
the key
key)

Returns node holding key or null if no such, clearing out any deleted nodes seen along the way.

private ConcurrentSkipListMap.Node<K, V>

Returns:

a predecessor node of key, or null if uninitialized or null key
findPredecessor(Object
if nonnull the key
key, Comparator<? super K> cmp)

Returns an index node with key strictly less than given key.

public Map.Entry<K, V>
firstEntry()

Implements java.util.NavigableMap.firstEntry.

Returns a key-value mapping associated with the least key in this map, or null if the map is empty.

public K
firstKey()

Implements java.util.SortedMap.firstKey.

Returns the first (lowest) key currently in this map.

public Map.Entry<K, V>
floorEntry(K
the key
key)

Implements java.util.NavigableMap.floorEntry.

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

public K
floorKey(K
the key
key)

Implements java.util.NavigableMap.floorKey.

Returns the greatest key less than or equal to the given key, or null if there is no such key.

public void
forEach(BiConsumer<? super K, ? super V> action)

Overrides default java.util.concurrent.ConcurrentMap.forEach, java.util.Map.forEach.

Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.

public V
get(Object key)

Overrides java.util.AbstractMap.get.

Implements java.util.Map.get.

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

pack-priv final long
getAdderCount()

Returns element count, initializing adder if necessary.

public V

Returns:

the mapping for the key, if present; else the defaultValue
getOrDefault(Object
the key
key, V
the value to return if this map contains no mapping for the given key
defaultValue)

Overrides default java.util.concurrent.ConcurrentMap.getOrDefault, java.util.Map.getOrDefault.

Returns the value to which the specified key is mapped, or the given defaultValue if this map contains no mapping for the key.

public ConcurrentNavigableMap<K, V>
headMap(K toKey, boolean inclusive)

Implements java.util.concurrent.ConcurrentNavigableMap.headMap.

Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.

public ConcurrentNavigableMap<K, V>
headMap(K toKey)

Implements java.util.concurrent.ConcurrentNavigableMap.headMap.

Returns a view of the portion of this map whose keys are strictly less than toKey.

public Map.Entry<K, V>
higherEntry(K
the key
key)

Implements java.util.NavigableMap.higherEntry.

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

public K
higherKey(K
the key
key)

Implements java.util.NavigableMap.higherKey.

Returns the least key strictly greater than the given key, or null if there is no such key.

public boolean
isEmpty()

Overrides java.util.AbstractMap.isEmpty.

Implements java.util.Map.isEmpty.

Returns true if this map contains no key-value mappings.

public NavigableSet<K>

Returns:

a navigable set view of the keys in this map
keySet()

Overrides java.util.AbstractMap.keySet.

Implements java.util.concurrent.ConcurrentNavigableMap.keySet, java.util.Map.keySet.

Returns a NavigableSet view of the keys contained in this map.

pack-priv final ConcurrentSkipListMap.KeySpliterator<K, V>
keySpliterator()

public Map.Entry<K, V>
lastEntry()

Implements java.util.NavigableMap.lastEntry.

Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

public K
lastKey()

Implements java.util.SortedMap.lastKey.

Returns the last (highest) key currently in this map.

public Map.Entry<K, V>
lowerEntry(K key)

Implements java.util.NavigableMap.lowerEntry.

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

public K
lowerKey(K key)

Implements java.util.NavigableMap.lowerKey.

Returns the greatest key strictly less than the given key, or null if there is no such key.

public V

Returns:

the new value associated with the specified key, or null if none
merge(K
key with which the specified value is to be associated
key, V
the value to use if absent
value, BiFunction<? super V, ? super V, ? extends V>
the function to recompute a value if present
remappingFunction)

Overrides default java.util.concurrent.ConcurrentMap.merge, java.util.Map.merge.

If the specified key is not already associated with a value, associates it with the given value.

public Map.Entry<K, V>
pollFirstEntry()

Implements java.util.NavigableMap.pollFirstEntry.

Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.

public Map.Entry<K, V>
pollLastEntry()

Implements java.util.NavigableMap.pollLastEntry.

Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

public V

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key
put(K
key with which the specified value is to be associated
key, V
value to be associated with the specified key
value)

Overrides java.util.AbstractMap.put.

Implements java.util.Map.put.

Associates the specified value with the specified key in this map.

public V
putFirst(K k, V v)

Overrides default java.util.SortedMap.putFirst.

Throws UnsupportedOperationException.

public V

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key
putIfAbsent(K key, V value)

Overrides default java.util.Map.putIfAbsent.

Implements java.util.concurrent.ConcurrentMap.putIfAbsent.

If the specified key is not already associated with a value, associates it with the given value.

public V
putLast(K k, V v)

Overrides default java.util.SortedMap.putLast.

Throws UnsupportedOperationException.

private void
readObject(final ObjectInputStream
the stream
s)

Reconstitutes this map from a stream (that is, deserializes it).

public V

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key
remove(Object
key for which mapping should be removed
key)

Overrides java.util.AbstractMap.remove.

Implements java.util.Map.remove.

Removes the mapping for the specified key from this map if present.

public boolean
remove(Object key, Object value)

Overrides default java.util.Map.remove.

Implements java.util.concurrent.ConcurrentMap.remove.

Removes the entry for a key only if currently mapped to a given value.

pack-priv boolean
removeEntryIf(Predicate<? super Map.Entry<K, V>> function)

Helper method for EntrySet.removeIf.

pack-priv boolean
removeValueIf(Predicate<? super V> function)

Helper method for Values.removeIf.

public boolean
replace(K key, V oldValue, V newValue)

Overrides default java.util.Map.replace.

Implements java.util.concurrent.ConcurrentMap.replace.

Replaces the entry for a key only if currently mapped to a given value.

public V

Returns:

the previous value associated with the specified key, or null if there was no mapping for the key
replace(K key, V value)

Overrides default java.util.Map.replace.

Implements java.util.concurrent.ConcurrentMap.replace.

Replaces the entry for a key only if currently mapped to some value.

public void
replaceAll(BiFunction<? super K, ? super V, ? extends V> function)

Overrides default java.util.concurrent.ConcurrentMap.replaceAll, java.util.Map.replaceAll.

Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception (optional operation).

public int
size()

Overrides java.util.AbstractMap.size.

Implements java.util.Map.size.

Returns the number of key-value mappings in this map.

public ConcurrentNavigableMap<K, V>
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

Implements java.util.concurrent.ConcurrentNavigableMap.subMap.

Returns a view of the portion of this map whose keys range from fromKey to toKey.

public ConcurrentNavigableMap<K, V>
subMap(K fromKey, K toKey)

Implements java.util.concurrent.ConcurrentNavigableMap.subMap.

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

public ConcurrentNavigableMap<K, V>
tailMap(K fromKey, boolean inclusive)

Implements java.util.concurrent.ConcurrentNavigableMap.tailMap.

Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.

public ConcurrentNavigableMap<K, V>
tailMap(K fromKey)

Implements java.util.concurrent.ConcurrentNavigableMap.tailMap.

Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

pack-priv static final <E> List<E>
toList(Collection<E> c)

private void
tryReduceLevel()

Possibly reduce head level if it has no nodes.

pack-priv static <K, V> void
unlinkNode(ConcurrentSkipListMap.Node<K, V>
if nonnull, predecessor
b, ConcurrentSkipListMap.Node<K, V>
if nonnull, node known to be deleted
n)

Tries to unlink deleted node n from predecessor b (if both exist), by first splicing in a marker if not already present.

public Collection<V>
values()

Overrides java.util.AbstractMap.values.

Implements java.util.Map.values, java.util.SortedMap.values.

Returns a Collection view of the values contained in this map.

pack-priv final ConcurrentSkipListMap.ValueSpliterator<K, V>
valueSpliterator()

private void
writeObject(ObjectOutputStream
the stream
s)

Saves this map to a stream (that is, serializes it).

Inherited from java.util.AbstractMap:
hashCodeputAlltoString