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 are
weakly consistent, returning
elements reflecting the state of the map at some point at or since
the creation of the iterator. They do
not throw
ConcurrentModificationException
, and may proceed concurrently with
other operations. 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, unlike in most collections, the
size
method is
not a constant-time operation. Because of the
asynchronous nature of these maps, determining the current number
of elements requires a traversal of the elements. Additionally,
the bulk operations
putAll,
equals, 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
../../../../technotes/guides/collections/index.html">
Java Collections Framework.
ceilingEntry
public java.util.Map.Entry ceilingEntry(K key)
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. The returned entry does not
support the Entry.setValue method.
- ceilingEntry in interface NavigableMap<K,V>
clone
public ConcurrentSkipListMap clone()
Returns a shallow copy of this ConcurrentSkipListMap
instance. (The keys and values themselves are not cloned.)
- clone in interface AbstractMap<K,V>
- a shallow copy of this map
containsValue
public boolean containsValue(Object value)
Returns true if this map maps one or more keys to the
specified value. This operation requires time linear in the
map size.
- containsValue in interface Map<K,V>
- containsValue in interface AbstractMap<K,V>
value
- value whose presence in this map is to be tested
- true if a mapping to value exists;
false otherwise
descendingKeySet
public NavigableSet descendingKeySet()
Returns a reverse order
NavigableSet
view of the keys contained in this map.
The set's iterator returns the keys in descending order.
The set is backed by the map, so changes to the map are
reflected in the set, and vice-versa. The set supports element
removal, which removes the corresponding mapping from the map,
via the
Iterator.remove
,
Set.remove
,
removeAll
,
retainAll
, and
clear
operations. It does not support the
add
or
addAll
operations.
The view's
iterator
is a "weakly consistent" iterator
that will never throw
ConcurrentModificationException
,
and guarantees to traverse elements as they existed upon
construction of the iterator, and may (but is not guaranteed to)
reflect any modifications subsequent to construction.
- descendingKeySet in interface ConcurrentNavigableMap<K,V>
- descendingKeySet in interface NavigableMap<K,V>
- a reverse order navigable set view of the keys in this map
descendingMap
public ConcurrentNavigableMap descendingMap()
Returns a reverse order view of the mappings contained in this map.
The descending map is backed by this map, so changes to the map are
reflected in the descending map, and vice-versa.
The returned map has an ordering equivalent to
Collections.reverseOrder
(comparator()).
The expression
m.descendingMap().descendingMap()
returns a
view of
m
essentially equivalent to
m
.
- descendingMap in interface ConcurrentNavigableMap<K,V>
- descendingMap in interface NavigableMap<K,V>
- a reverse order view of this map
entrySet
public Set> entrySet()
Returns a
Set
view of the mappings contained in this map.
The set's iterator returns the entries in ascending key order.
The set is backed by the map, so changes to the map are
reflected in the set, and vice-versa. The set supports element
removal, which removes the corresponding mapping from the map,
via the
Iterator.remove,
Set.remove,
removeAll,
retainAll and
clear
operations. It does not support the
add or
addAll operations.
The view's
iterator is a "weakly consistent" iterator
that will never throw
ConcurrentModificationException
,
and guarantees to traverse elements as they existed upon
construction of the iterator, and may (but is not guaranteed to)
reflect any modifications subsequent to construction.
The
Map.Entry elements returned by
iterator.next() do
not support the
setValue operation.
- a set view of the mappings contained in this map,
sorted in ascending key order
equals
public boolean equals(Object o)
Compares the specified object with this map for equality.
Returns true if the given object is also a map and the
two maps represent the same mappings. More formally, two maps
m1 and m2 represent the same mappings if
m1.entrySet().equals(m2.entrySet()). This
operation may return misleading results if either map is
concurrently modified during execution of this method.
- equals in interface Map<K,V>
- equals in interface AbstractMap<K,V>
o
- object to be compared for equality with this map
- true if the specified object is equal to this map
firstEntry
public java.util.Map.Entry firstEntry()
Returns a key-value mapping associated with the least
key in this map, or null if the map is empty.
The returned entry does not support
the Entry.setValue method.
- firstEntry in interface NavigableMap<K,V>
floorEntry
public java.util.Map.Entry floorEntry(K key)
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. The returned entry does not support
the Entry.setValue method.
- floorEntry in interface NavigableMap<K,V>
get
public V get(Object key)
Returns the value to which the specified key is mapped,
or
null
if this map contains no mapping for the key.
More formally, if this map contains a mapping from a key
k
to a value
v
such that
key
compares
equal to
k
according to the map's ordering, then this
method returns
v
; otherwise it returns
null
.
(There can be at most one such mapping.)
- get in interface Map<K,V>
- get in interface AbstractMap<K,V>
higherEntry
public java.util.Map.Entry higherEntry(K key)
Returns a key-value mapping associated with the least key
strictly greater than the given key, or null if there
is no such key. The returned entry does not support
the Entry.setValue method.
- higherEntry in interface NavigableMap<K,V>
keySet
public NavigableSet keySet()
Returns a
NavigableSet
view of the keys contained in this map.
The set's iterator returns the keys in ascending order.
The set is backed by the map, so changes to the map are
reflected in the set, and vice-versa. The set supports element
removal, which removes the corresponding mapping from the map,
via the
Iterator.remove
,
Set.remove
,
removeAll
,
retainAll
, and
clear
operations. It does not support the
add
or
addAll
operations.
The view's
iterator
is a "weakly consistent" iterator
that will never throw
ConcurrentModificationException
,
and guarantees to traverse elements as they existed upon
construction of the iterator, and may (but is not guaranteed to)
reflect any modifications subsequent to construction.
This method is equivalent to method
navigableKeySet
.
- keySet in interface ConcurrentNavigableMap<K,V>
- keySet in interface Map<K,V>
- keySet in interface AbstractMap<K,V>
- a navigable set view of the keys in this map
lastEntry
public java.util.Map.Entry lastEntry()
Returns a key-value mapping associated with the greatest
key in this map, or null if the map is empty.
The returned entry does not support
the Entry.setValue method.
- lastEntry in interface NavigableMap<K,V>
lowerEntry
public java.util.Map.Entry lowerEntry(K key)
Returns a key-value mapping associated with the greatest key
strictly less than the given key, or null if there is
no such key. The returned entry does not support the
Entry.setValue method.
- lowerEntry in interface NavigableMap<K,V>
navigableKeySet
public NavigableSet navigableKeySet()
Returns a
NavigableSet
view of the keys contained in this map.
The set's iterator returns the keys in ascending order.
The set is backed by the map, so changes to the map are
reflected in the set, and vice-versa. The set supports element
removal, which removes the corresponding mapping from the map,
via the
Iterator.remove
,
Set.remove
,
removeAll
,
retainAll
, and
clear
operations. It does not support the
add
or
addAll
operations.
The view's
iterator
is a "weakly consistent" iterator
that will never throw
ConcurrentModificationException
,
and guarantees to traverse elements as they existed upon
construction of the iterator, and may (but is not guaranteed to)
reflect any modifications subsequent to construction.
- navigableKeySet in interface ConcurrentNavigableMap<K,V>
- navigableKeySet in interface NavigableMap<K,V>
- a navigable set view of the keys in this map
pollFirstEntry
public java.util.Map.Entry pollFirstEntry()
Removes and returns a key-value mapping associated with
the least key in this map, or null if the map is empty.
The returned entry does not support
the Entry.setValue method.
- pollFirstEntry in interface NavigableMap<K,V>
pollLastEntry
public java.util.Map.Entry pollLastEntry()
Removes and returns a key-value mapping associated with
the greatest key in this map, or null if the map is empty.
The returned entry does not support
the Entry.setValue method.
- pollLastEntry in interface NavigableMap<K,V>
put
public V put(K key,
V value)
Associates the specified value with the specified key in this map.
If the map previously contained a mapping for the key, the old
value is replaced.
- put in interface Map<K,V>
- put in interface AbstractMap<K,V>
key
- key with which the specified value is to be associatedvalue
- value to be associated with the specified key
- the previous value associated with the specified key, or
null if there was no mapping for the key
remove
public V remove(Object key)
Removes the mapping for the specified key from this map if present.
- remove in interface Map<K,V>
- remove in interface AbstractMap<K,V>
key
- key for which mapping should be removed
- the previous value associated with the specified key, or
null if there was no mapping for the key
replace
public V replace(K key,
V value)
- replace in interface ConcurrentMap<K,V>
- the previous value associated with the specified key,
or null if there was no mapping for the key
size
public int size()
Returns the number of key-value mappings in this map. If this map
contains more than
Integer.MAX_VALUE elements, it
returns
Integer.MAX_VALUE.
Beware that, unlike in most collections, this method is
NOT a constant-time operation. Because of the
asynchronous nature of these maps, determining the current
number of elements requires traversing them all to count them.
Additionally, it is possible for the size to change during
execution of this method, in which case the returned result
will be inaccurate. Thus, this method is typically not very
useful in concurrent applications.
- size in interface Map<K,V>
- size in interface AbstractMap<K,V>
- the number of elements in this map
values
public Collection values()
Returns a
Collection
view of the values contained in this map.
The collection's iterator returns the values in ascending order
of the corresponding keys.
The collection is backed by the map, so changes to the map are
reflected in the collection, and vice-versa. The collection
supports element removal, which removes the corresponding
mapping from the map, via the
Iterator.remove,
Collection.remove,
removeAll,
retainAll and
clear operations. It does not
support the
add or
addAll operations.
The view's
iterator is a "weakly consistent" iterator
that will never throw
ConcurrentModificationException
,
and guarantees to traverse elements as they existed upon
construction of the iterator, and may (but is not guaranteed to)
reflect any modifications subsequent to construction.
- values in interface Map<K,V>
- values in interface AbstractMap<K,V>