Class NonBlockingHashMapLong<TypeV>
- java.lang.Object
-
- java.util.AbstractMap<java.lang.Long,TypeV>
-
- org.jctools.maps.NonBlockingHashMapLong<TypeV>
-
- Type Parameters:
TypeV- the type of mapped values
- All Implemented Interfaces:
java.io.Serializable,java.lang.Cloneable,java.util.concurrent.ConcurrentMap<java.lang.Long,TypeV>,java.util.Map<java.lang.Long,TypeV>
public class NonBlockingHashMapLong<TypeV> extends java.util.AbstractMap<java.lang.Long,TypeV> implements java.util.concurrent.ConcurrentMap<java.lang.Long,TypeV>, java.lang.Cloneable, java.io.SerializableA lock-free alternate implementation ofConcurrentHashMapwith primitive long keys, better scaling properties and generally lower costs. The use oflongkeys allows for faster compares and lower memory costs. The Map provides identical correctness properties as ConcurrentHashMap. All operations are non-blocking and multi-thread safe, including all update operations.NonBlockingHashMapLongscales substatially better thanConcurrentHashMapfor 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.The main benefit of this class over using plain
NonBlockingHashMapwithLongkeys is that it avoids the auto-boxing and unboxing costs. Since auto-boxing is automatic, it is easy to accidentally cause auto-boxing and negate the space and speed benefits.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
MapandIteratorinterfaces.Like
Hashtablebut unlikeHashMap, this class does not allow null to be used as a value.- Since:
- 1.5
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static classNonBlockingHashMapLong.CHMclassNonBlockingHashMapLong.IteratorLongA class which implements theIteratorandEnumerationinterfaces, generified to theLongclass and supporting a non-auto-boxingNonBlockingHashMapLong.IteratorLong.nextLong()function.private classNonBlockingHashMapLong.NBHMLEntryprivate static classNonBlockingHashMapLong.Primeprivate classNonBlockingHashMapLong.SnapshotEprivate classNonBlockingHashMapLong.SnapshotV
-
Field Summary
Fields Modifier and Type Field Description private NonBlockingHashMapLong.CHM_chmprivate static long_chm_offsetprivate long_last_resize_milliprivate static int_Lbaseprivate static int_Lscaleprivate static int_Obaseprivate boolean_opt_for_spaceprivate static int_Oscaleprivate ConcurrentAutoTable_reprobesprivate java.lang.Object_val_1private static long_val_1_offsetprivate static java.lang.ObjectMATCH_ANYprivate static intMIN_SIZEprivate static intMIN_SIZE_LOGprivate static longNO_KEYprivate static java.lang.ObjectNO_MATCH_OLDprivate static intREPROBE_LIMITprivate static longserialVersionUIDprivate static NonBlockingHashMapLong.PrimeTOMBPRIMEprivate static java.lang.ObjectTOMBSTONE
-
Constructor Summary
Constructors Constructor Description NonBlockingHashMapLong()Create a new NonBlockingHashMapLong with default minimum size (currently set to 8 K/V pairs or roughly 84 bytes on a standard 32-bit JVM).NonBlockingHashMapLong(boolean opt_for_space)Create a new NonBlockingHashMapLong, setting the space-for-speed tradeoff.NonBlockingHashMapLong(int initial_sz)Create a new NonBlockingHashMapLong with initial room for the given number of elements, thus avoiding internal resizing operations to reach an appropriate size.NonBlockingHashMapLong(int initial_sz, boolean opt_for_space)Create a new NonBlockingHashMapLong, setting both the initial size and the space-for-speed tradeoff.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private booleanCAS(long offset, java.lang.Object old, java.lang.Object nnn)voidclear()Removes all of the mappings from this map.voidclear(boolean large)NonBlockingHashMapLong<TypeV>clone()Creates a shallow copy of this hashtable.booleancontains(java.lang.Object val)Legacy method testing if some key maps into the specified value in this table.booleancontainsKey(long key)Tests if the key in the table.booleancontainsKey(java.lang.Object key)Auto-boxing version ofcontainsKey(long).booleancontainsValue(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<java.lang.Long,TypeV>>entrySet()Returns aSetview of the mappings contained in this map.TypeVget(long key)Returns the value to which the specified key is mapped, ornullif this map contains no mapping for the key.TypeVget(java.lang.Object key)Auto-boxing version ofget(long).private static inthash(long h)private voidhelp_copy()private voidinitialize(int initial_sz)java.util.Enumeration<java.lang.Long>keys()Returns an enumeration of the auto-boxed keys in this table.java.util.Set<java.lang.Long>keySet()Returns aSetview of the keys contained in this map; with care the keys may be iterated over without auto-boxing.long[]keySetLong()Keys as a long array.voidprint()Verbose printout of table internals, useful for debugging.private static voidprint_impl(int i, long K, java.lang.Object V)private voidprint2()private static voidprint2_impl(int i, long K, java.lang.Object V)TypeVput(long key, TypeV val)Maps the specified key to the specified value in the table.TypeVput(java.lang.Long key, TypeV val)Auto-boxing version ofput(long, TypeV).TypeVputIfAbsent(long key, TypeV val)Atomically, do aput(long, TypeV)if-and-only-if the key is not mapped.TypeVputIfAbsent(java.lang.Long key, TypeV val)Auto-boxing version ofputIfAbsent(long, TypeV).private TypeVputIfMatch(long key, java.lang.Object newVal, java.lang.Object oldVal)private static longrawIndex(long[] ary, int idx)private static longrawIndex(java.lang.Object[] ary, int idx)private voidreadObject(java.io.ObjectInputStream s)TypeVremove(long key)Removes the key (and its corresponding value) from this map.booleanremove(long key, java.lang.Object val)Atomically do aremove(long)if-and-only-if the key is mapped to a value which isequalsto the given value.TypeVremove(java.lang.Object key)Auto-boxing version ofremove(long).booleanremove(java.lang.Object key, java.lang.Object Val)Auto-boxing version ofremove(long,Object).TypeVreplace(long key, TypeV val)Atomically do aput(key,val)if-and-only-if the key is mapped to some value already.booleanreplace(long key, TypeV oldValue, TypeV newValue)Atomically do aput(key,newValue)if-and-only-if the key is mapped a value which isequalstooldValue.TypeVreplace(java.lang.Long key, TypeV Val)Auto-boxing version ofreplace(long, TypeV).booleanreplace(java.lang.Long key, TypeV oldValue, TypeV newValue)Auto-boxing version ofreplace(long, TypeV).private static intreprobe_limit(int len)longreprobes()Get and clear the current count of reprobes.intsize()Returns the number of key-value mappings in this map.java.util.Collection<TypeV>values()Returns aCollectionview of the values contained in this map.private voidwriteObject(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
-
_Lbase
private static final int _Lbase
-
_Lscale
private static final int _Lscale
-
_chm_offset
private static final long _chm_offset
-
_val_1_offset
private static final long _val_1_offset
-
_chm
private transient NonBlockingHashMapLong.CHM _chm
-
_val_1
private transient java.lang.Object _val_1
-
_last_resize_milli
private transient long _last_resize_milli
-
_opt_for_space
private final boolean _opt_for_space
-
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
private static final java.lang.Object TOMBSTONE
-
TOMBPRIME
private static final NonBlockingHashMapLong.Prime TOMBPRIME
-
NO_KEY
private static final long NO_KEY
- See Also:
- Constant Field Values
-
_reprobes
private transient ConcurrentAutoTable _reprobes
-
-
Constructor Detail
-
NonBlockingHashMapLong
public NonBlockingHashMapLong()
Create a new NonBlockingHashMapLong with default minimum size (currently set to 8 K/V pairs or roughly 84 bytes on a standard 32-bit JVM).
-
NonBlockingHashMapLong
public NonBlockingHashMapLong(int initial_sz)
Create a new NonBlockingHashMapLong 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.
-
NonBlockingHashMapLong
public NonBlockingHashMapLong(boolean opt_for_space)
Create a new NonBlockingHashMapLong, setting the space-for-speed tradeoff.trueoptimizes for space and is the default.falseoptimizes for speed and doubles space costs for roughly a 10% speed improvement.
-
NonBlockingHashMapLong
public NonBlockingHashMapLong(int initial_sz, boolean opt_for_space)Create a new NonBlockingHashMapLong, setting both the initial size and the space-for-speed tradeoff.trueoptimizes for space and is the default.falseoptimizes for speed and doubles space costs for roughly a 10% speed improvement.
-
-
Method Detail
-
rawIndex
private static long rawIndex(java.lang.Object[] ary, int idx)
-
rawIndex
private static long rawIndex(long[] ary, int idx)
-
CAS
private final boolean CAS(long offset, java.lang.Object old, java.lang.Object nnn)
-
print
public final void print()
Verbose printout of table internals, useful for debugging.
-
print_impl
private static void print_impl(int i, long K, java.lang.Object V)
-
print2
private void print2()
-
print2_impl
private static void print2_impl(int i, long K, java.lang.Object V)
-
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 void initialize(int initial_sz)
-
size
public int size()
Returns the number of key-value mappings in this map.
-
containsKey
public boolean containsKey(long key)
Tests if the key in the table.- Returns:
- true if the key is in the table
-
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(long key, TypeV val)
Maps the specified key to the specified value in the table. The value cannot be null.The value can be retrieved by calling
get(long)with a key that is equal to the original key.- 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 value is null
-
putIfAbsent
public TypeV putIfAbsent(long key, TypeV val)
Atomically, do aput(long, 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.- 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 is value is null
-
remove
public TypeV remove(long key)
Removes the key (and its corresponding value) from this map. This method does nothing if the key is not in the map.- Returns:
- the previous value associated with key, or null if there was no mapping for key
-
remove
public boolean remove(long key, java.lang.Object val)Atomically do aremove(long)if-and-only-if the key is mapped to a value which isequalsto the given value.- Throws:
java.lang.NullPointerException- if the specified value is null
-
replace
public TypeV replace(long key, TypeV val)
Atomically do aput(key,val)if-and-only-if the key is mapped to some value already.- Throws:
java.lang.NullPointerException- if the specified value is null
-
replace
public boolean replace(long key, TypeV oldValue, TypeV newValue)Atomically do aput(key,newValue)if-and-only-if the key is mapped a value which isequalstooldValue.- Throws:
java.lang.NullPointerException- if the specified value is null
-
putIfMatch
private TypeV putIfMatch(long key, java.lang.Object newVal, java.lang.Object oldVal)
-
clear
public void clear()
Removes all of the mappings from this map.
-
clear
public void clear(boolean large)
-
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(long).- Specified by:
containsValuein interfacejava.util.Map<java.lang.Long,TypeV>- Overrides:
containsValuein classjava.util.AbstractMap<java.lang.Long,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
-
get
public final TypeV get(long key)
Returns the value to which the specified key is mapped, ornullif this map contains no mapping for the key.More formally, if this map contains a mapping from a key
kto a valuevsuch thatkey==k, then this method returnsv; otherwise it returnsnull. (There can be at most one such mapping.)- Throws:
java.lang.NullPointerException- if the specified key is null
-
remove
public TypeV remove(java.lang.Object key)
Auto-boxing version ofremove(long).
-
remove
public boolean remove(java.lang.Object key, java.lang.Object Val)Auto-boxing version ofremove(long,Object).
-
containsKey
public boolean containsKey(java.lang.Object key)
Auto-boxing version ofcontainsKey(long).
-
putIfAbsent
public TypeV putIfAbsent(java.lang.Long key, TypeV val)
Auto-boxing version ofputIfAbsent(long, TypeV).
-
replace
public TypeV replace(java.lang.Long key, TypeV Val)
Auto-boxing version ofreplace(long, TypeV).
-
put
public TypeV put(java.lang.Long key, TypeV val)
Auto-boxing version ofput(long, TypeV).
-
replace
public boolean replace(java.lang.Long key, TypeV oldValue, TypeV newValue)Auto-boxing version ofreplace(long, TypeV).
-
help_copy
private void help_copy()
-
hash
private static final int hash(long h)
-
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 aCollectionview 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<java.lang.Long> keys()
Returns an enumeration of the auto-boxed keys in this table. Warning: this version will auto-box all returned keys.- Returns:
- an enumeration of the auto-boxed keys in this table
- See Also:
keySet()
-
keySet
public java.util.Set<java.lang.Long> keySet()
Returns aSetview of the keys contained in this map; with care the keys may be iterated over without auto-boxing. 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.
-
keySetLong
public long[] keySetLong()
Keys as a long array. Array may be zero-padded if keys are concurrently deleted.
-
entrySet
public java.util.Set<java.util.Map.Entry<java.lang.Long,TypeV>> entrySet()
Returns aSetview 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.Entryobjects with each iteration. TheNonBlockingHashMapdoes not normally create or usingMap.Entryobjects so they will be created soley to support this iteration. Iterating usingMap.keySet()orMap.values()will be more efficient. In addition, this version requires auto-boxing the keys.
-
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.IOExceptionjava.lang.ClassNotFoundException
-
clone
public NonBlockingHashMapLong<TypeV> 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.- Overrides:
clonein classjava.util.AbstractMap<java.lang.Long,TypeV>- Returns:
- a clone of the hashtable.
-
-