TypeK - the type of keys maintained by this mapTypeV - the type of mapped valuespublic class NonBlockingHashMap<TypeK,TypeV>
extends java.util.AbstractMap<TypeK,TypeV>
implements java.util.concurrent.ConcurrentMap<TypeK,TypeV>, java.lang.Cloneable, java.io.Serializable
ConcurrentHashMap
with better scaling properties and generally lower costs to mutate the Map.
It provides identical correctness properties as ConcurrentHashMap. All
operations are non-blocking and multi-thread safe, including all update
operations. NonBlockingHashMap scales substatially better than
ConcurrentHashMap for high update rates, even with a
large concurrency factor. Scaling is linear up to 768 CPUs on a 768-CPU
Azul box, even with 100% updates or 100% reads or any fraction in-between.
Linear scaling up to all cpus has been observed on a 32-way Sun US2 box,
32-way Sun Niagra box, 8-way Intel box and a 4-way Power box.
This class obeys the same functional specification as Hashtable, and includes versions of methods corresponding to
each method of Hashtable. However, even though all operations are
thread-safe, operations do not entail locking and there is
not any support for locking the entire table in a way that
prevents all access. This class is fully interoperable with
Hashtable in programs that rely on its thread safety but not on
its synchronization details.
Operations (including put) generally do not block, so may
overlap with other update operations (including other puts and
removes). Retrievals reflect the results of the most recently
completed update operations holding upon their onset. For
aggregate operations such as putAll, concurrent retrievals may
reflect insertion or removal of only some entries. Similarly, Iterators
and Enumerations return elements reflecting the state of the hash table at
some point at or since the creation of the iterator/enumeration. They do
not throw ConcurrentModificationException. However,
iterators are designed to be used by only one thread at a time.
Very full tables, or tables with high reprobe rates may trigger an internal resize operation to move into a larger table. Resizing is not terribly expensive, but it is not free either; during resize operations table throughput may drop somewhat. All threads that visit the table during a resize will 'help' the resizing but will still be allowed to complete their operation before the resize is finished (i.e., a simple 'get' operation on a million-entry table undergoing resizing will not need to block until the entire million entries are copied).
This class and its views and iterators implement all of the
optional methods of the Map and Iterator
interfaces.
Like Hashtable but unlike HashMap, this class
does not allow null to be used as a key or value.
| Modifier and Type | Field and Description |
|---|---|
static java.lang.Object[] |
READONLY |
static java.lang.Object |
TOMBSTONE |
| Constructor and Description |
|---|
NonBlockingHashMap()
Create a new NonBlockingHashMap with default minimum size (currently set
to 8 K/V pairs or roughly 84 bytes on a standard 32-bit JVM).
|
NonBlockingHashMap(int initial_sz)
Create a new NonBlockingHashMap with initial room for the given number of
elements, thus avoiding internal resizing operations to reach an
appropriate size.
|
| Modifier and Type | Method and Description |
|---|---|
void |
clear()
Removes all of the mappings from this map.
|
java.lang.Object |
clone()
Creates a shallow copy of this hashtable.
|
boolean |
contains(java.lang.Object val)
Legacy method testing if some key maps into the specified value in this
table.
|
boolean |
containsKey(java.lang.Object key)
Tests if the key in the table using the equals method.
|
boolean |
containsValue(java.lang.Object val)
Returns true if this Map maps one or more keys to the specified
value.
|
java.util.Enumeration<TypeV> |
elements()
Returns an enumeration of the values in this table.
|
java.util.Set<java.util.Map.Entry<TypeK,TypeV>> |
entrySet()
Returns a
Set view of the mappings contained in this map. |
TypeV |
get(java.lang.Object key)
Returns the value to which the specified key is mapped, or
null
if this map contains no mapping for the key. |
TypeK |
getk(TypeK key)
Returns the Key to which the specified key is mapped, or
null
if this map contains no mapping for the key. |
protected void |
initialize() |
boolean |
isEmpty()
Returns size() == 0.
|
java.util.Enumeration<TypeK> |
keys()
Returns an enumeration of the keys in this table.
|
java.util.Set<TypeK> |
keySet()
Returns a
Set view of the keys contained in this map. |
java.lang.Object[] |
kvs() |
void |
print()
Verbose printout of table internals, useful for debugging.
|
TypeV |
put(TypeK key,
TypeV val)
Maps the specified key to the specified value in the table.
|
void |
putAll(java.util.Map<? extends TypeK,? extends TypeV> m)
Copies all of the mappings from the specified map to this one, replacing
any existing mappings.
|
TypeV |
putIfAbsent(TypeK key,
TypeV val)
Atomically, do a
put(TypeK, TypeV) if-and-only-if the key is not mapped. |
TypeV |
putIfMatch(java.lang.Object key,
java.lang.Object newVal,
java.lang.Object oldVal) |
TypeV |
putIfMatchUnlocked(java.lang.Object key,
java.lang.Object newVal,
java.lang.Object oldVal) |
java.lang.Object[] |
raw_array() |
void |
readOnly()
Atomically make the set immutable.
|
protected void |
rehash() |
TypeV |
remove(java.lang.Object key)
Removes the key (and its corresponding value) from this map.
|
boolean |
remove(java.lang.Object key,
java.lang.Object val)
Atomically do a
remove(Object) if-and-only-if the key is mapped
to a value which is equals to the given value. |
TypeV |
replace(TypeK key,
TypeV val)
Atomically do a
put(key,val) if-and-only-if the key is
mapped to some value already. |
boolean |
replace(TypeK key,
TypeV oldValue,
TypeV newValue)
Atomically do a
put(key,newValue) if-and-only-if the key is
mapped a value which is equals to oldValue. |
long |
reprobes()
Get and clear the current count of reprobes.
|
int |
size()
Returns the number of key-value mappings in this map.
|
java.lang.String |
toString()
Returns a string representation of this map.
|
java.util.Collection<TypeV> |
values()
Returns a
Collection view of the values contained in this map. |
public static final java.lang.Object TOMBSTONE
public static final java.lang.Object[] READONLY
public NonBlockingHashMap()
public NonBlockingHashMap(int initial_sz)
public java.lang.Object[] kvs()
public final void print()
public long reprobes()
reprobes()
or since the table was created.protected final void initialize()
public int size()
public boolean isEmpty()
public boolean containsKey(java.lang.Object key)
public boolean contains(java.lang.Object val)
containsValue(java.lang.Object), and exists solely to ensure full compatibility with
class Hashtable, which supported this method prior to
introduction of the Java Collections framework.val - a value to search forjava.lang.NullPointerException - if the specified value is nullpublic TypeV put(TypeK key, TypeV val)
The value can be retrieved by calling get(java.lang.Object) with a key that is
equal to the original key.
put in interface java.util.Map<TypeK,TypeV>put in class java.util.AbstractMap<TypeK,TypeV>key - key with which the specified value is to be associatedval - value to be associated with the specified keyjava.lang.NullPointerException - if the specified key or value is nullpublic TypeV putIfAbsent(TypeK key, TypeV val)
put(TypeK, TypeV) if-and-only-if the key is not mapped.
Useful to ensure that only a single mapping for the key exists, even if
many threads are trying to create the mapping in parallel.public TypeV remove(java.lang.Object key)
public boolean remove(java.lang.Object key,
java.lang.Object val)
remove(Object) if-and-only-if the key is mapped
to a value which is equals to the given value.public TypeV replace(TypeK key, TypeV val)
put(key,val) if-and-only-if the key is
mapped to some value already.public boolean replace(TypeK key, TypeV oldValue, TypeV newValue)
put(key,newValue) if-and-only-if the key is
mapped a value which is equals to oldValue.public final TypeV putIfMatchUnlocked(java.lang.Object key, java.lang.Object newVal, java.lang.Object oldVal)
public final TypeV putIfMatch(java.lang.Object key, java.lang.Object newVal, java.lang.Object oldVal)
public void putAll(java.util.Map<? extends TypeK,? extends TypeV> m)
public void clear()
public boolean containsValue(java.lang.Object val)
containsKey(java.lang.Object).containsValue in interface java.util.Map<TypeK,TypeV>containsValue in class java.util.AbstractMap<TypeK,TypeV>val - value whose presence in this map is to be testedjava.lang.NullPointerException - if the specified value is nullprotected void rehash()
public java.lang.Object clone()
public java.lang.String toString()
String.valueOf(Object).public TypeV get(java.lang.Object key)
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.equals(k), then this method
returns v; otherwise it returns null. (There can be at
most one such mapping.)
public TypeK getk(TypeK key)
null
if this map contains no mapping for the key.java.lang.NullPointerException - if the specified key is nullpublic java.lang.Object[] raw_array()
public java.util.Enumeration<TypeV> elements()
values()public java.util.Collection<TypeV> values()
Collection view of the values contained in this map.
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 this 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.
public java.util.Enumeration<TypeK> keys()
keySet()public java.util.Set<TypeK> keySet()
Set view of the keys contained in this map. 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 this 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.
public java.util.Set<java.util.Map.Entry<TypeK,TypeV>> entrySet()
Set view of the mappings contained in this map. 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.
Warning: the iterator associated with this Set
requires the creation of Map.Entry objects with each
iteration. The NonBlockingHashMap does not normally create or
using Map.Entry objects so they will be created soley
to support this iteration. Iterating using keySet() or values() will be more efficient.
public void readOnly()
readOnly() call returns.
This call can be called concurrently (and indeed until the operation
completes, all calls on the Set from any thread either complete normally
or end up calling readOnly() internally).
This call is useful in debugging multi-threaded programs where the
Set is constructed in parallel, but construction completes after some
time; and after construction the Set is only read. Making the Set
read-only will cause updates arriving after construction is supposedly
complete to throw an IllegalStateException.