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 substantially 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 Niagara 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 re-probe 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 | Class and Description |
---|---|
private static class |
NonBlockingHashMap.CHM<TypeK,TypeV> |
private class |
NonBlockingHashMap.NBHMEntry |
private static class |
NonBlockingHashMap.Prime |
private class |
NonBlockingHashMap.SnapshotE |
private class |
NonBlockingHashMap.SnapshotK |
private class |
NonBlockingHashMap.SnapshotV |
Modifier and Type | Field and Description |
---|---|
private java.lang.Object[] |
_kvs |
private static long |
_kvs_offset |
private long |
_last_resize_milli |
private static int |
_Obase |
private static int |
_Olog |
private static int |
_Oscale |
private ConcurrentAutoTable |
_reprobes |
(package private) static int |
DUMMY_VOLATILE |
private static java.lang.Object |
MATCH_ANY |
private static int |
MIN_SIZE |
private static int |
MIN_SIZE_LOG |
private static java.lang.Object |
NO_MATCH_OLD |
private static int |
REPROBE_LIMIT |
private static long |
serialVersionUID |
private static NonBlockingHashMap.Prime |
TOMBPRIME |
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 |
---|---|
private static boolean |
CAS_key(java.lang.Object[] kvs,
int idx,
java.lang.Object old,
java.lang.Object key) |
private boolean |
CAS_kvs(java.lang.Object[] oldkvs,
java.lang.Object[] newkvs) |
private static boolean |
CAS_val(java.lang.Object[] kvs,
int idx,
java.lang.Object old,
java.lang.Object val) |
private static NonBlockingHashMap.CHM |
chm(java.lang.Object[] kvs) |
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. |
private static java.lang.Object |
get_impl(NonBlockingHashMap topmap,
java.lang.Object[] kvs,
java.lang.Object key) |
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. |
private static java.lang.Object |
getk_impl(NonBlockingHashMap topmap,
java.lang.Object[] kvs,
java.lang.Object 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. |
private static int |
hash(java.lang.Object key) |
private static int[] |
hashes(java.lang.Object[] kvs) |
private java.lang.Object[] |
help_copy(java.lang.Object[] helper) |
protected void |
initialize() |
private void |
initialize(int initial_sz) |
boolean |
isEmpty()
Returns size() == 0.
|
private static java.lang.Object |
key(java.lang.Object[] kvs,
int idx) |
private static boolean |
keyeq(java.lang.Object K,
java.lang.Object key,
int[] hashes,
int hash,
int fullhash) |
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. |
private static int |
len(java.lang.Object[] kvs) |
void |
print()
Verbose printout of table internals, useful for debugging.
|
private void |
print(java.lang.Object[] kvs) |
private void |
print2(java.lang.Object[] kvs) |
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. |
private static java.lang.Object |
putIfMatch(NonBlockingHashMap topmap,
java.lang.Object[] kvs,
java.lang.Object key,
java.lang.Object putval,
java.lang.Object expVal) |
TypeV |
putIfMatch(java.lang.Object key,
java.lang.Object newVal,
java.lang.Object oldVal)
Atomically replace newVal for oldVal, returning the value that existed
there before.
|
TypeV |
putIfMatchAllowNull(java.lang.Object key,
java.lang.Object newVal,
java.lang.Object oldVal) |
java.lang.Object[] |
raw_array() |
private static long |
rawIndex(java.lang.Object[] ary,
int idx) |
private void |
readObject(java.io.ObjectInputStream s) |
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 . |
private static int |
reprobe_limit(int len) |
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.
|
private static java.lang.Object |
val(java.lang.Object[] kvs,
int idx) |
java.util.Collection<TypeV> |
values()
Returns a
Collection view of the values contained in this map. |
private void |
writeObject(java.io.ObjectOutputStream s) |
finalize, getClass, notify, notifyAll, wait, wait, wait
private static final long serialVersionUID
private static final int REPROBE_LIMIT
private static final int _Obase
private static final int _Oscale
private static final int _Olog
private static final long _kvs_offset
private transient java.lang.Object[] _kvs
private transient long _last_resize_milli
private static final int MIN_SIZE_LOG
private static final int MIN_SIZE
private static final java.lang.Object NO_MATCH_OLD
private static final java.lang.Object MATCH_ANY
public static final java.lang.Object TOMBSTONE
private static final NonBlockingHashMap.Prime TOMBPRIME
private transient ConcurrentAutoTable _reprobes
static volatile int DUMMY_VOLATILE
public NonBlockingHashMap()
public NonBlockingHashMap(int initial_sz)
private static long rawIndex(java.lang.Object[] ary, int idx)
private final boolean CAS_kvs(java.lang.Object[] oldkvs, java.lang.Object[] newkvs)
private static final int hash(java.lang.Object key)
private static final NonBlockingHashMap.CHM chm(java.lang.Object[] kvs)
private static final int[] hashes(java.lang.Object[] kvs)
private static final int len(java.lang.Object[] kvs)
private static final java.lang.Object key(java.lang.Object[] kvs, int idx)
private static final java.lang.Object val(java.lang.Object[] kvs, int idx)
private static final boolean CAS_key(java.lang.Object[] kvs, int idx, java.lang.Object old, java.lang.Object key)
private static final boolean CAS_val(java.lang.Object[] kvs, int idx, java.lang.Object old, java.lang.Object val)
public final void print()
private final void print(java.lang.Object[] kvs)
private final void print2(java.lang.Object[] kvs)
public long reprobes()
reprobes()
or since the table was created.private static int reprobe_limit(int len)
private final void initialize(int initial_sz)
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.putIfAbsent
in interface java.util.concurrent.ConcurrentMap<TypeK,TypeV>
putIfAbsent
in interface java.util.Map<TypeK,TypeV>
java.lang.NullPointerException
- if the specified key or value is nullpublic 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 putIfMatchAllowNull(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)
java.lang.NullPointerException
- if the key or either value is nullpublic 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)
.private static boolean keyeq(java.lang.Object K, java.lang.Object key, int[] hashes, int hash, int fullhash)
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.)
private static final java.lang.Object get_impl(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key)
public TypeK getk(TypeK key)
null
if this map contains no mapping for the key.java.lang.NullPointerException
- if the specified key is nullprivate static final java.lang.Object getk_impl(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key)
private static final java.lang.Object putIfMatch(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key, java.lang.Object putval, java.lang.Object expVal)
private final java.lang.Object[] help_copy(java.lang.Object[] helper)
public 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.
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
java.io.IOException
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, java.lang.ClassNotFoundException
java.io.IOException
java.lang.ClassNotFoundException