Class NonBlockingHashMap<TypeK,TypeV>
- java.lang.Object
-
- java.util.AbstractMap<TypeK,TypeV>
-
- org.jctools.maps.NonBlockingHashMap<TypeK,TypeV>
-
- Type Parameters:
TypeK
- the type of keys maintained by this mapTypeV
- the type of mapped values
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
,java.util.concurrent.ConcurrentMap<TypeK,TypeV>
,java.util.Map<TypeK,TypeV>
public class NonBlockingHashMap<TypeK,TypeV> extends java.util.AbstractMap<TypeK,TypeV> implements java.util.concurrent.ConcurrentMap<TypeK,TypeV>, java.lang.Cloneable, java.io.Serializable
A lock-free alternate implementation ofConcurrentHashMap
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 thanConcurrentHashMap
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 asHashtable
, 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
andIterator
interfaces.Like
Hashtable
but unlikeHashMap
, this class does not allow null to be used as a key or value.- Since:
- 1.5
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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
-
Field Summary
Fields Modifier and Type Field 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 Summary
Constructors Constructor 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.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 aSet
view of the mappings contained in this map.TypeV
get(java.lang.Object key)
Returns the value to which the specified key is mapped, ornull
if this map contains no mapping for the key.private static java.lang.Object
get_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, ornull
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)
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 aSet
view of the keys contained in this map.private static int
len(java.lang.Object[] kvs)
private static boolean
objectsEquals(java.lang.Object a, java.lang.Object b)
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 aput(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)
Atomically replace newVal for oldVal, returning the value that existed there before.private static java.lang.Object
putIfMatch0(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key, java.lang.Object putval, java.lang.Object expVal)
Put, Remove, PutIfAbsent, etc.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 aremove(Object)
if-and-only-if the key is mapped to a value which isequals
to the given value.TypeV
replace(TypeK key, TypeV val)
Atomically do aput(key,val)
if-and-only-if the key is mapped to some value already.boolean
replace(TypeK key, TypeV oldValue, TypeV newValue)
Atomically do aput(key,newValue)
if-and-only-if the key is mapped a value which isequals
tooldValue
.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 aCollection
view of the values contained in this map.private void
writeObject(java.io.ObjectOutputStream s)
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
REPROBE_LIMIT
private static final int REPROBE_LIMIT
- See Also:
- Constant Field Values
-
_Obase
private static final int _Obase
-
_Oscale
private static final int _Oscale
-
_Olog
private static final int _Olog
-
_kvs_offset
private static final long _kvs_offset
-
_kvs
private transient java.lang.Object[] _kvs
-
_last_resize_milli
private transient long _last_resize_milli
-
MIN_SIZE_LOG
private static final int MIN_SIZE_LOG
- See Also:
- Constant Field Values
-
MIN_SIZE
private static final int MIN_SIZE
- See Also:
- Constant Field Values
-
NO_MATCH_OLD
private static final java.lang.Object NO_MATCH_OLD
-
MATCH_ANY
private static final java.lang.Object MATCH_ANY
-
TOMBSTONE
public static final java.lang.Object TOMBSTONE
-
TOMBPRIME
private static final NonBlockingHashMap.Prime TOMBPRIME
-
_reprobes
private transient ConcurrentAutoTable _reprobes
-
DUMMY_VOLATILE
static volatile int DUMMY_VOLATILE
-
-
Constructor Detail
-
NonBlockingHashMap
public 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
public 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. Large numbers here when used with a small count of elements will sacrifice space for a small amount of time gained. The initial size will be rounded up internally to the next larger power of 2.
-
-
Method Detail
-
rawIndex
private static long rawIndex(java.lang.Object[] ary, int idx)
-
CAS_kvs
private final boolean CAS_kvs(java.lang.Object[] oldkvs, java.lang.Object[] newkvs)
-
hash
private static final int hash(java.lang.Object key)
-
chm
private static final NonBlockingHashMap.CHM chm(java.lang.Object[] kvs)
-
hashes
private static final int[] hashes(java.lang.Object[] kvs)
-
len
private static final int len(java.lang.Object[] kvs)
-
key
private static final java.lang.Object key(java.lang.Object[] kvs, int idx)
-
val
private static final java.lang.Object val(java.lang.Object[] kvs, int idx)
-
CAS_key
private static final boolean CAS_key(java.lang.Object[] kvs, int idx, java.lang.Object old, java.lang.Object key)
-
CAS_val
private static final boolean CAS_val(java.lang.Object[] kvs, int idx, java.lang.Object old, java.lang.Object val)
-
print
public final void print()
Verbose printout of table internals, useful for debugging.
-
print
private final void print(java.lang.Object[] kvs)
-
print2
private final void print2(java.lang.Object[] kvs)
-
reprobes
public long reprobes()
Get and clear the current count of reprobes. Reprobes happen on key collisions, and a high reprobe rate may indicate a poor hash function or weaknesses in the table resizing function.- Returns:
- the count of reprobes since the last call to
reprobes()
or since the table was created.
-
reprobe_limit
private static int reprobe_limit(int len)
-
initialize
private final void initialize(int initial_sz)
-
initialize
protected final void initialize()
-
size
public int size()
Returns the number of key-value mappings in this map.
-
isEmpty
public boolean isEmpty()
Returns size() == 0.
-
containsKey
public boolean containsKey(java.lang.Object key)
Tests if the key in the table using the equals method.
-
contains
public boolean contains(java.lang.Object val)
Legacy method testing if some key maps into the specified value in this table. This method is identical in functionality tocontainsValue(java.lang.Object)
, and exists solely to ensure full compatibility with classHashtable
, which supported this method prior to introduction of the Java Collections framework.- Parameters:
val
- a value to search for- Returns:
- true if this map maps one or more keys to the specified value
- Throws:
java.lang.NullPointerException
- if the specified value is null
-
put
public TypeV put(TypeK key, TypeV val)
Maps the specified key to the specified value in the table. Neither key nor value can be null.The value can be retrieved by calling
get(java.lang.Object)
with a key that is equal to the original key.- Specified by:
put
in interfacejava.util.Map<TypeK,TypeV>
- Overrides:
put
in classjava.util.AbstractMap<TypeK,TypeV>
- Parameters:
key
- key with which the specified value is to be associatedval
- value to be associated with the specified key- Returns:
- the previous value associated with key, or null if there was no mapping for key
- Throws:
java.lang.NullPointerException
- if the specified key or value is null
-
putIfAbsent
public TypeV putIfAbsent(TypeK key, TypeV val)
Atomically, do aput(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.- Specified by:
putIfAbsent
in interfacejava.util.concurrent.ConcurrentMap<TypeK,TypeV>
- Specified by:
putIfAbsent
in interfacejava.util.Map<TypeK,TypeV>
- Returns:
- the previous value associated with the specified key, or null if there was no mapping for the key
- Throws:
java.lang.NullPointerException
- if the specified key or value is null
-
remove
public TypeV remove(java.lang.Object key)
Removes the key (and its corresponding value) from this map. This method does nothing if the key is not in the map.
-
remove
public boolean remove(java.lang.Object key, java.lang.Object val)
Atomically do aremove(Object)
if-and-only-if the key is mapped to a value which isequals
to the given value.
-
replace
public TypeV replace(TypeK key, TypeV val)
Atomically do aput(key,val)
if-and-only-if the key is mapped to some value already.
-
replace
public boolean replace(TypeK key, TypeV oldValue, TypeV newValue)
Atomically do aput(key,newValue)
if-and-only-if the key is mapped a value which isequals
tooldValue
.
-
objectsEquals
private static boolean objectsEquals(java.lang.Object a, java.lang.Object b)
-
putIfMatchAllowNull
public final TypeV putIfMatchAllowNull(java.lang.Object key, java.lang.Object newVal, java.lang.Object oldVal)
-
putIfMatch
public final 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. If the oldVal matches the returned value, then newVal was inserted, otherwise not.- Returns:
- the previous value associated with the specified key, or null if there was no mapping for the key
- Throws:
java.lang.NullPointerException
- if the key or either value is null
-
putAll
public 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.
-
clear
public void clear()
Removes all of the mappings from this map.
-
containsValue
public boolean containsValue(java.lang.Object val)
Returns true if this Map maps one or more keys to the specified value. Note: This method requires a full internal traversal of the hash table and is much slower thancontainsKey(java.lang.Object)
.- Specified by:
containsValue
in interfacejava.util.Map<TypeK,TypeV>
- Overrides:
containsValue
in classjava.util.AbstractMap<TypeK,TypeV>
- Parameters:
val
- value whose presence in this map is to be tested- Returns:
- true if this map maps one or more keys to the specified value
- Throws:
java.lang.NullPointerException
- if the specified value is null
-
rehash
protected void rehash()
-
clone
public java.lang.Object clone()
Creates a shallow copy of this hashtable. All the structure of the hashtable itself is copied, but the keys and values are not cloned. This is a relatively expensive operation.
-
toString
public java.lang.String toString()
Returns a string representation of this map. The string representation consists of a list of key-value mappings in the order returned by the map's entrySet view's iterator, enclosed in braces ("{}"). Adjacent mappings are separated by the characters ", " (comma and space). Each key-value mapping is rendered as the key followed by an equals sign ("=") followed by the associated value. Keys and values are converted to strings as byString.valueOf(Object)
.
-
keyeq
private static boolean keyeq(java.lang.Object K, java.lang.Object key, int[] hashes, int hash, int fullhash)
-
get
public TypeV get(java.lang.Object key)
Returns the value to which the specified key is mapped, ornull
if this map contains no mapping for the key.More formally, if this map contains a mapping from a key
k
to a valuev
such thatkey.equals(k)
, then this method returnsv
; otherwise it returnsnull
. (There can be at most one such mapping.)
-
get_impl
private static final java.lang.Object get_impl(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key)
-
getk
public TypeK getk(TypeK key)
Returns the Key to which the specified key is mapped, ornull
if this map contains no mapping for the key.- Throws:
java.lang.NullPointerException
- if the specified key is null
-
getk_impl
private static final java.lang.Object getk_impl(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key)
-
putIfMatch0
private static final java.lang.Object putIfMatch0(NonBlockingHashMap topmap, java.lang.Object[] kvs, java.lang.Object key, java.lang.Object putval, java.lang.Object expVal)
Put, Remove, PutIfAbsent, etc. Return the old value. If the returned value is equal to expVal (or expVal isNO_MATCH_OLD
) then the put can be assumed to work (although might have been immediately overwritten). Only the path through copy_slot passes in an expected value of null, and putIfMatch only returns a null if passed in an expected null.- Parameters:
topmap
- the map to act onkvs
- the KV table snapshot we act onkey
- not null (will result inNullPointerException
)putval
- the new value to use. Not null.TOMBSTONE
will result in deleting the entry.expVal
- expected old value. Can be null.NO_MATCH_OLD
for an unconditional put/remove.TOMBSTONE
if we expect old entry to not exist(null/TOMBSTONE
value).MATCH_ANY
will ignore the current value, but only if an entry exists. A null expVal is used internally to perform a strict insert-if-never-been-seen-before operation.- Returns:
TOMBSTONE
if key does not exist or match has failed. null if expVal is null AND old value was null. Otherwise the old entry value (not null).
-
help_copy
private final java.lang.Object[] help_copy(java.lang.Object[] helper)
-
raw_array
public java.lang.Object[] raw_array()
-
elements
public java.util.Enumeration<TypeV> elements()
Returns an enumeration of the values in this table.- Returns:
- an enumeration of the values in this table
- See Also:
values()
-
values
public java.util.Collection<TypeV> values()
Returns aCollection
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.
-
keys
public java.util.Enumeration<TypeK> keys()
Returns an enumeration of the keys in this table.- Returns:
- an enumeration of the keys in this table
- See Also:
keySet()
-
keySet
public java.util.Set<TypeK> keySet()
Returns aSet
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.
-
entrySet
public java.util.Set<java.util.Map.Entry<TypeK,TypeV>> entrySet()
Returns aSet
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. TheNonBlockingHashMap
does not normally create or usingMap.Entry
objects so they will be created soley to support this iteration. Iterating usingkeySet()
orvalues()
will be more efficient.
-
writeObject
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
- Throws:
java.io.IOException
-
readObject
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, java.lang.ClassNotFoundException
- Throws:
java.io.IOException
java.lang.ClassNotFoundException
-
-