| java.util.concurrent.ConcurrentSkipListMap
| ConcurrentSkipListMap | | public class ConcurrentSkipListMap extends AbstractMap implements ConcurrentNavigableMap<K, V>,Cloneable,java.io.Serializable(Code) | | A scalable concurrent
ConcurrentNavigableMap implementation.
The map is sorted according to the
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
Java Collections Framework.
author:
Doug Lea<
Parameters:
K - > the type of keys maintained by this map<
Parameters:
V - > the type of mapped values
since:
1.6 |
| Inner Class :final static class Node | |
| Inner Class :static class Index | |
| Inner Class :final static class HeadIndex extends Index | |
| Inner Class :final static class ComparableUsingComparator implements Comparable<K> | |
| Inner Class :abstract class Iter implements Iterator<T> | |
| Inner Class :final class ValueIterator extends Iter | |
| Inner Class :final class KeyIterator extends Iter | |
| Inner Class :final class EntryIterator extends Iter> | |
| Inner Class :final static class KeySet extends AbstractSet implements NavigableSet<E> | |
| Inner Class :final static class Values extends AbstractCollection | |
| Inner Class :final static class EntrySet extends AbstractSet> | |
| Constructor Summary | |
| public | ConcurrentSkipListMap()
Constructs a new, empty map, sorted according to the
of the keys. | | public | ConcurrentSkipListMap(Comparator<? super K> comparator)
Constructs a new, empty map, sorted according to the specified
comparator. | | public | ConcurrentSkipListMap(Map<? extends K, ? extends V> m)
Constructs a new map containing the same mappings as the given map,
sorted according to the
of
the keys. | | public | ConcurrentSkipListMap(SortedMap<K, ? extends V> m)
Constructs a new map containing the same mappings and using the
same ordering as the specified sorted map. |
| Method Summary | |
| public Map.Entry<K, V> | 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. | | public K | ceilingKey(K key)
| | public void | clear()
Removes all of the mappings from this map. | | public ConcurrentSkipListMap<K, V> | clone()
Returns a shallow copy of this ConcurrentSkipListMap
instance. | | public Comparator<? super K> | comparator()
| | int | compare(K k1, K k2)
Compares using comparator or natural ordering. | | public boolean | containsKey(Object key)
Returns true if this map contains a mapping for the specified
key. | | public boolean | containsValue(Object value)
Returns true if this map maps one or more keys to the
specified value. | | public NavigableSet<K> | descendingKeySet()
| | public ConcurrentNavigableMap<K, V> | descendingMap()
| | final V | doRemove(Object okey, Object value)
Main deletion method. | | Map.Entry<K, V> | doRemoveFirstEntry()
Removes first entry; returns its snapshot. | | Map.Entry<K, V> | doRemoveLastEntry()
Removes last entry; returns its snapshot. | | Iterator<Map.Entry<K, V>> | entryIterator()
| | public Set<Map.Entry<K, V>> | 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. | | 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. | | Node<K, V> | findFirst()
Specialized variant of findNode to get first valid node. | | Node<K, V> | findLast()
Specialized version of find to get last valid node. | | Node<K, V> | findNear(K kkey, int rel)
Utility for ceiling, floor, lower, higher methods. | | public Map.Entry<K, V> | firstEntry()
Returns a key-value mapping associated with the least
key in this map, or null if the map is empty. | | public K | firstKey()
| | public Map.Entry<K, V> | 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. | | public K | floorKey(K key)
| | 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. | | AbstractMap.SimpleImmutableEntry<K, V> | getNear(K key, int rel)
Returns SimpleImmutableEntry for results of findNear. | | public ConcurrentNavigableMap<K, V> | headMap(K toKey, boolean inclusive)
| | public ConcurrentNavigableMap<K, V> | headMap(K toKey)
| | public Map.Entry<K, V> | 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. | | public K | higherKey(K key)
| | boolean | inHalfOpenRange(K key, K least, K fence)
Returns true if given key greater than or equal to least and
strictly less than fence, bypassing either test if least or
fence are null. | | boolean | inOpenRange(K key, K least, K fence)
Returns true if given key greater than or equal to least and less
or equal to fence. | | final void | initialize()
Initializes or resets state. | | public boolean | isEmpty()
Returns true if this map contains no key-value mappings. | | Iterator<K> | keyIterator()
| | public NavigableSet<K> | 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. | | public Map.Entry<K, V> | lastEntry()
Returns a key-value mapping associated with the greatest
key in this map, or null if the map is empty. | | public K | lastKey()
| | public Map.Entry<K, V> | 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. | | public K | lowerKey(K key)
| | public NavigableSet<K> | navigableKeySet()
| | public Map.Entry<K, V> | 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()
Removes and returns a key-value mapping associated with
the greatest key in this map, or null if the map is empty. | | public V | put(K key, V value)
Associates the specified value with the specified key in this map. | | public V | putIfAbsent(K key, V value)
| | public V | remove(Object key)
Removes the mapping for the specified key from this map if present. | | public boolean | remove(Object key, Object value)
| | public boolean | replace(K key, V oldValue, V newValue)
| | public V | replace(K key, V value)
| | public int | size()
Returns the number of key-value mappings in this map. | | public ConcurrentNavigableMap<K, V> | subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
| | public ConcurrentNavigableMap<K, V> | subMap(K fromKey, K toKey)
| | public ConcurrentNavigableMap<K, V> | tailMap(K fromKey, boolean inclusive)
| | public ConcurrentNavigableMap<K, V> | tailMap(K fromKey)
| | final static List<E> | toList(Collection<E> c)
| | Iterator<V> | valueIterator()
| | public Collection<V> | 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. |
| ConcurrentSkipListMap | | public ConcurrentSkipListMap()(Code) | | Constructs a new, empty map, sorted according to the
of the keys.
|
| ConcurrentSkipListMap | | public ConcurrentSkipListMap(Comparator<? super K> comparator)(Code) | | Constructs a new, empty map, sorted according to the specified
comparator.
Parameters:
comparator - the comparator that will be used to order this map.If null, the of the keys will be used. |
| ConcurrentSkipListMap | | public ConcurrentSkipListMap(Map<? extends K, ? extends V> m)(Code) | | Constructs a new map containing the same mappings as the given map,
sorted according to the
of
the keys.
Parameters:
m - the map whose mappings are to be placed in this map
throws:
ClassCastException - if the keys in m are notComparable, or are not mutually comparable
throws:
NullPointerException - if the specified map or any of its keysor values are null |
| ConcurrentSkipListMap | | public ConcurrentSkipListMap(SortedMap<K, ? extends V> m)(Code) | | Constructs a new map containing the same mappings and using the
same ordering as the specified sorted map.
Parameters:
m - the sorted map whose mappings are to be placed in thismap, and whose comparator is to be used to sort this map
throws:
NullPointerException - if the specified sorted map or any ofits keys or values are null |
| ceilingEntry | | public Map.Entry<K, V> ceilingEntry(K key)(Code) | | 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.
throws:
ClassCastException -
throws:
NullPointerException - if the specified key is null |
| clear | | public void clear()(Code) | | Removes all of the mappings from this map.
|
| clone | | public ConcurrentSkipListMap<K, V> clone()(Code) | | Returns a shallow copy of this ConcurrentSkipListMap
instance. (The keys and values themselves are not cloned.)
a shallow copy of this map |
| compare | | int compare(K k1, K k2) throws ClassCastException(Code) | | Compares using comparator or natural ordering. Used when the
ComparableUsingComparator approach doesn't apply.
|
| containsKey | | public boolean containsKey(Object key)(Code) | | Returns true if this map contains a mapping for the specified
key.
Parameters:
key - key whose presence in this map is to be tested true if this map contains a mapping for the specified key
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if the specified key is null |
| containsValue | | public boolean containsValue(Object value)(Code) | | Returns true if this map maps one or more keys to the
specified value. This operation requires time linear in the
map size.
Parameters:
value - value whose presence in this map is to be tested true if a mapping to value exists;false otherwise
throws:
NullPointerException - if the specified value is null |
| doRemove | | final V doRemove(Object okey, Object value)(Code) | | Main deletion method. Locates node, nulls value, appends a
deletion marker, unlinks predecessor, removes associated index
nodes, and possibly reduces head index level.
Index nodes are cleared out simply by calling findPredecessor.
which unlinks indexes to deleted nodes found along path to key,
which will include the indexes to this node. This is done
unconditionally. We can't check beforehand whether there are
index nodes because it might be the case that some or all
indexes hadn't been inserted yet for this node during initial
search for it, and we'd like to ensure lack of garbage
retention, so must call to be sure.
Parameters:
okey - the key
Parameters:
value - if non-null, the value that must beassociated with key the node, or null if not found |
| doRemoveFirstEntry | | Map.Entry<K, V> doRemoveFirstEntry()(Code) | | Removes first entry; returns its snapshot.
null if empty, else snapshot of first entry |
| doRemoveLastEntry | | Map.Entry<K, V> doRemoveLastEntry()(Code) | | Removes last entry; returns its snapshot.
Specialized variant of doRemove.
null if empty, else snapshot of last entry |
| entrySet | | public Set<Map.Entry<K, V>> entrySet()(Code) | | 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)(Code) | | 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.
Parameters:
o - object to be compared for equality with this map true if the specified object is equal to this map |
| findFirst | | Node<K, V> findFirst()(Code) | | Specialized variant of findNode to get first valid node.
first node or null if empty |
| findLast | | Node<K, V> findLast()(Code) | | Specialized version of find to get last valid node.
last node or null if empty |
| findNear | | Node<K, V> findNear(K kkey, int rel)(Code) | | Utility for ceiling, floor, lower, higher methods.
Parameters:
kkey - the key
Parameters:
rel - the relation -- OR'ed combination of EQ, LT, GT nearest node fitting relation, or null if no such |
| firstEntry | | public Map.Entry<K, V> firstEntry()(Code) | | 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.
|
| floorEntry | | public Map.Entry<K, V> floorEntry(K key)(Code) | | 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.
Parameters:
key - the key
throws:
ClassCastException -
throws:
NullPointerException - if the specified key is null |
| get | | public V get(Object key)(Code) | | 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.)
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if the specified key is null |
| getNear | | AbstractMap.SimpleImmutableEntry<K, V> getNear(K key, int rel)(Code) | | Returns SimpleImmutableEntry for results of findNear.
Parameters:
key - the key
Parameters:
rel - the relation -- OR'ed combination of EQ, LT, GT Entry fitting relation, or null if no such |
| higherEntry | | public Map.Entry<K, V> higherEntry(K key)(Code) | | 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.
Parameters:
key - the key
throws:
ClassCastException -
throws:
NullPointerException - if the specified key is null |
| inHalfOpenRange | | boolean inHalfOpenRange(K key, K least, K fence)(Code) | | Returns true if given key greater than or equal to least and
strictly less than fence, bypassing either test if least or
fence are null. Needed mainly in submap operations.
|
| inOpenRange | | boolean inOpenRange(K key, K least, K fence)(Code) | | Returns true if given key greater than or equal to least and less
or equal to fence. Needed mainly in submap operations.
|
| initialize | | final void initialize()(Code) | | Initializes or resets state. Needed by constructors, clone,
clear, readObject. and ConcurrentSkipListSet.clone.
(Note that comparator must be separately initialized.)
|
| isEmpty | | public boolean isEmpty()(Code) | | Returns true if this map contains no key-value mappings.
true if this map contains no key-value mappings |
| keySet | | public NavigableSet<K> keySet()(Code) | | 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 .
a navigable set view of the keys in this map |
| lastEntry | | public Map.Entry<K, V> lastEntry()(Code) | | 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.
|
| lowerEntry | | public Map.Entry<K, V> lowerEntry(K key)(Code) | | 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.
throws:
ClassCastException -
throws:
NullPointerException - if the specified key is null |
| pollFirstEntry | | public Map.Entry<K, V> pollFirstEntry()(Code) | | 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.
|
| pollLastEntry | | public Map.Entry<K, V> pollLastEntry()(Code) | | 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.
|
| put | | public V put(K key, V value)(Code) | | 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.
Parameters:
key - key with which the specified value is to be associated
Parameters:
value - value to be associated with the specified key the previous value associated with the specified key, ornull if there was no mapping for the key
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if the specified key or value is null |
| putIfAbsent | | public V putIfAbsent(K key, V value)(Code) | | the previous value associated with the specified key,or null if there was no mapping for the key
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if the specified key or value is null |
| remove | | public V remove(Object key)(Code) | | Removes the mapping for the specified key from this map if present.
Parameters:
key - key for which mapping should be removed the previous value associated with the specified key, ornull if there was no mapping for the key
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if the specified key is null |
| replace | | public boolean replace(K key, V oldValue, V newValue)(Code) | |
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if any of the arguments are null |
| replace | | public V replace(K key, V value)(Code) | | the previous value associated with the specified key,or null if there was no mapping for the key
throws:
ClassCastException - if the specified key cannot be comparedwith the keys currently in the map
throws:
NullPointerException - if the specified key or value is null |
| size | | public int size()(Code) | | 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<V> values()(Code) | | 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.
|
|
|