Class NonBlockingIdentityHashMap<TypeK,TypeV>
- Type Parameters:
TypeK
- the type of keys maintained by this mapTypeV
- the type of mapped values
- All Implemented Interfaces:
Serializable
,Cloneable
,ConcurrentMap<TypeK,
,TypeV> Map<TypeK,
TypeV>
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.
- Since:
- 1.5
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K extends Object,
V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object, V extends Object> -
Constructor Summary
ConstructorDescriptionCreate a new NonBlockingHashMap with default minimum size (currently set to 8 K/V pairs or roughly 84 bytes on a standard 32-bit JVM).NonBlockingIdentityHashMap
(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
Modifier and TypeMethodDescriptionvoid
clear()
Removes all of the mappings from this map.clone()
Creates a shallow copy of this hashtable.boolean
Legacy method testing if some key maps into the specified value in this table.boolean
containsKey
(Object key) Tests if the key in the table using the equals method.boolean
containsValue
(Object val) Returns true if this Map maps one or more keys to the specified value.elements()
Returns an enumeration of the values in this table.entrySet()
Returns aSet
view of the mappings contained in this map.Returns the value to which the specified key is mapped, ornull
if this map contains no mapping for the key.boolean
isEmpty()
Returns size() == 0.keys()
Returns an enumeration of the keys in this table.keySet()
Returns aSet
view of the keys contained in this map.final void
print()
Verbose printout of table internals, useful for debugging.Maps the specified key to the specified value in the table.void
Copies all of the mappings from the specified map to this one, replacing any existing mappings.putIfAbsent
(TypeK key, TypeV val) Atomically, do aput(TypeK, TypeV)
if-and-only-if the key is not mapped.Removes the key (and its corresponding value) from this map.boolean
Atomically do aremove(Object)
if-and-only-if the key is mapped to a value which isequals
to the given value.Atomically do aput(key,val)
if-and-only-if the key is mapped to some value already.boolean
Atomically do aput(key,newValue)
if-and-only-if the key is mapped a value which isequals
tooldValue
.long
reprobes()
Get and clear the current count of reprobes.int
size()
Returns the number of key-value mappings in this map.toString()
Returns a string representation of this map.values()
Returns aCollection
view of the values contained in this map.Methods inherited from class java.util.AbstractMap
equals, hashCode
Methods inherited from interface java.util.concurrent.ConcurrentMap
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll
-
Constructor Details
-
NonBlockingIdentityHashMap
public NonBlockingIdentityHashMap()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). -
NonBlockingIdentityHashMap
public NonBlockingIdentityHashMap(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 Details
-
print
public final void print()Verbose printout of table internals, useful for debugging. -
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.
-
size
public int size()Returns the number of key-value mappings in this map. -
isEmpty
public boolean isEmpty()Returns size() == 0. -
containsKey
Tests if the key in the table using the equals method.- Specified by:
containsKey
in interfaceMap<TypeK,
TypeV> - Overrides:
containsKey
in classAbstractMap<TypeK,
TypeV> - Returns:
- true if the key is in the table using the equals method
- Throws:
NullPointerException
- if the specified key is null
-
contains
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:
NullPointerException
- if the specified value is null
-
put
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 interfaceMap<TypeK,
TypeV> - Overrides:
put
in classAbstractMap<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:
NullPointerException
- if the specified key or value is null
-
putIfAbsent
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 interfaceConcurrentMap<TypeK,
TypeV> - Specified by:
putIfAbsent
in interfaceMap<TypeK,
TypeV> - Returns:
- the previous value associated with the specified key, or null if there was no mapping for the key
- Throws:
NullPointerException
- if the specified key or value is null
-
remove
Removes the key (and its corresponding value) from this map. This method does nothing if the key is not in the map.- Specified by:
remove
in interfaceMap<TypeK,
TypeV> - Overrides:
remove
in classAbstractMap<TypeK,
TypeV> - Returns:
- the previous value associated with key, or null if there was no mapping for key
- Throws:
NullPointerException
- if the specified key is null
-
remove
Atomically do aremove(Object)
if-and-only-if the key is mapped to a value which isequals
to the given value.- Specified by:
remove
in interfaceConcurrentMap<TypeK,
TypeV> - Specified by:
remove
in interfaceMap<TypeK,
TypeV> - Throws:
NullPointerException
- if the specified key or value is null
-
replace
Atomically do aput(key,val)
if-and-only-if the key is mapped to some value already.- Specified by:
replace
in interfaceConcurrentMap<TypeK,
TypeV> - Specified by:
replace
in interfaceMap<TypeK,
TypeV> - Throws:
NullPointerException
- if the specified key or value is null
-
replace
Atomically do aput(key,newValue)
if-and-only-if the key is mapped a value which isequals
tooldValue
.- Specified by:
replace
in interfaceConcurrentMap<TypeK,
TypeV> - Specified by:
replace
in interfaceMap<TypeK,
TypeV> - Throws:
NullPointerException
- if the specified key or value is null
-
putAll
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
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 interfaceMap<TypeK,
TypeV> - Overrides:
containsValue
in classAbstractMap<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:
NullPointerException
- if the specified value is null
-
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.- Returns:
- a clone of the hashtable.
-
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)
.- Overrides:
toString
in classAbstractMap<TypeK,
TypeV> - Returns:
- a string representation of this map
-
get
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.)- Specified by:
get
in interfaceMap<TypeK,
TypeV> - Overrides:
get
in classAbstractMap<TypeK,
TypeV> - Throws:
NullPointerException
- if the specified key is null
-
elements
Returns an enumeration of the values in this table.- Returns:
- an enumeration of the values in this table
- See Also:
-
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
Returns an enumeration of the keys in this table.- Returns:
- an enumeration of the keys in this table
- See Also:
-
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
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. TheNonBlockingIdentityHashMap
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.
-