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
java.util.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 Map.Entry ceilingEntry(Object 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
clear
public void clear()
Removes all of the mappings from this map.
clone
public Object clone()
Returns a shallow copy of this ConcurrentSkipListMap
instance. (The keys and values themselves are not cloned.)
- a shallow copy of this map
comparator
public Comparator comparator()
containsKey
public boolean containsKey(Object key)
Returns true if this map contains a mapping for the specified
key.
key
- key whose presence in this map is to be tested
- true if this map contains a mapping for the specified key
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.
value
- value whose presence in this map is to be tested
- true if a mapping to value exists;
false otherwise
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
java.util.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.
o
- object to be compared for equality with this map
- true if the specified object is equal to this map
firstEntry
public 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
firstKey
public Object firstKey()
floorEntry
public Map.Entry floorEntry(Object 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
get
public Object 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.)
higherEntry
public Map.Entry higherEntry(Object 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
isEmpty
public boolean isEmpty()
Returns true if this map contains no key-value mappings.
- true if this map contains no key-value mappings
keySet
public Set 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
java.util.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
- keySet in interface AbstractMap
- a navigable set view of the keys in this map
lastEntry
public 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
lastKey
public Object lastKey()
lowerEntry
public Map.Entry lowerEntry(Object 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
pollFirstEntry
public 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
pollLastEntry
public 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
put
public Object put(Object key,
Object 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.
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
putIfAbsent
public Object putIfAbsent(Object key,
Object value)
- putIfAbsent in interface ConcurrentMap
- the previous value associated with the specified key,
or null if there was no mapping for the key
remove
public Object remove(Object key)
Removes the mapping for the specified key from this map if present.
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 Object replace(Object key,
Object value)
- replace in interface ConcurrentMap
- the previous value associated with the specified key,
or null if there was no mapping for the key
replace
public boolean replace(Object key,
Object oldValue,
Object newValue)
- replace in interface ConcurrentMap
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.
- 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
java.util.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.