Class NonBlockingHashMapLong<TypeV>

  • Type Parameters:
    TypeV - the type of mapped values
    All Implemented Interfaces:
    java.io.Serializable, 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.io.Serializable
    A lock-free alternate implementation of ConcurrentHashMap with primitive long keys, better scaling properties and generally lower costs. The use of long keys 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. NonBlockingHashMapLong 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.

    The main benefit of this class over using plain NonBlockingHashMap with Long keys 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 Map and Iterator interfaces.

    Like Hashtable but unlike HashMap, this class does not allow null to be used as a value.

    Since:
    1.5
    See Also:
    Serialized Form
    • 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 boolean CAS​(long offset, java.lang.Object old, java.lang.Object nnn)  
      void clear()
      Removes all of the mappings from this map.
      boolean contains​(java.lang.Object val)
      Legacy method testing if some key maps into the specified value in this table.
      boolean containsKey​(long key)
      Tests if the key in the table.
      boolean containsKey​(java.lang.Object key)
      Auto-boxing version of containsKey(long).
      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<java.lang.Long,​TypeV>> entrySet()
      Returns a Set view of the mappings contained in this map.
      TypeV get​(long key)
      Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
      TypeV get​(java.lang.Object key)
      Auto-boxing version of get(long).
      private void help_copy()  
      private void initialize​(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 a Set view 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.
      void print()
      Verbose printout of table internals, useful for debugging.
      private static void print_impl​(int i, long K, java.lang.Object V)  
      private void print2()  
      private static void print2_impl​(int i, long K, java.lang.Object V)  
      TypeV put​(long key, TypeV val)
      Maps the specified key to the specified value in the table.
      TypeV put​(java.lang.Long key, TypeV val)
      Auto-boxing version of put(long, TypeV).
      TypeV putIfAbsent​(long key, TypeV val)
      Atomically, do a put(long, TypeV) if-and-only-if the key is not mapped.
      TypeV putIfAbsent​(java.lang.Long key, TypeV val)
      Auto-boxing version of putIfAbsent(long, TypeV).
      private TypeV putIfMatch​(long key, java.lang.Object newVal, java.lang.Object oldVal)  
      private static long rawIndex​(long[] ary, int idx)  
      private static long rawIndex​(java.lang.Object[] ary, int idx)  
      private void readObject​(java.io.ObjectInputStream s)  
      TypeV remove​(long key)
      Removes the key (and its corresponding value) from this map.
      boolean remove​(long key, java.lang.Object val)
      Atomically do a remove(long) if-and-only-if the key is mapped to a value which is equals to the given value.
      TypeV remove​(java.lang.Object key)
      Auto-boxing version of remove(long).
      boolean remove​(java.lang.Object key, java.lang.Object Val)
      Auto-boxing version of remove(long,Object).
      TypeV replace​(long key, TypeV val)
      Atomically do a put(key,val) if-and-only-if the key is mapped to some value already.
      boolean replace​(long 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.
      TypeV replace​(java.lang.Long key, TypeV Val)
      Auto-boxing version of replace(long, TypeV).
      boolean replace​(java.lang.Long key, TypeV oldValue, TypeV newValue)
      Auto-boxing version of replace(long, TypeV).
      private static int reprobe_limit​(int len)  
      int size()
      Returns the number of key-value mappings in this map.
      java.util.Collection<TypeV> values()
      Returns a Collection view of the values contained in this map.
      private void writeObject​(java.io.ObjectOutputStream s)  
      • Methods inherited from class java.util.AbstractMap

        clone, equals, hashCode, isEmpty, putAll, toString
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.concurrent.ConcurrentMap

        compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll
      • Methods inherited from interface java.util.Map

        equals, hashCode, isEmpty, putAll
    • Field Detail

      • _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
      • _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
      • 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
    • 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. true optimizes for space and is the default. false optimizes 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. true optimizes for space and is the default. false optimizes 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)
      • 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.
        Specified by:
        size in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        size in class java.util.AbstractMap<java.lang.Long,​TypeV>
        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 to 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.
        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 associated
        val - 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 a put(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 a remove(long) if-and-only-if the key is mapped to a value which is equals to the given value.
        Throws:
        java.lang.NullPointerException - if the specified value is null
      • replace

        public TypeV replace​(long key,
                             TypeV val)
        Atomically do a put(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 a put(key,newValue) if-and-only-if the key is mapped a value which is equals to oldValue.
        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.
        Specified by:
        clear in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        clear in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • 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 than containsKey(long).
        Specified by:
        containsValue in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        containsValue in class java.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, or 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==k, then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

        Throws:
        java.lang.NullPointerException - if the specified key is null
      • get

        public TypeV get​(java.lang.Object key)
        Auto-boxing version of get(long).
        Specified by:
        get in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        get in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • remove

        public TypeV remove​(java.lang.Object key)
        Auto-boxing version of remove(long).
        Specified by:
        remove in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        remove in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • remove

        public boolean remove​(java.lang.Object key,
                              java.lang.Object Val)
        Auto-boxing version of remove(long,Object).
        Specified by:
        remove in interface java.util.concurrent.ConcurrentMap<java.lang.Long,​TypeV>
        Specified by:
        remove in interface java.util.Map<java.lang.Long,​TypeV>
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Auto-boxing version of containsKey(long).
        Specified by:
        containsKey in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        containsKey in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • putIfAbsent

        public TypeV putIfAbsent​(java.lang.Long key,
                                 TypeV val)
        Auto-boxing version of putIfAbsent(long, TypeV).
        Specified by:
        putIfAbsent in interface java.util.concurrent.ConcurrentMap<java.lang.Long,​TypeV>
        Specified by:
        putIfAbsent in interface java.util.Map<java.lang.Long,​TypeV>
      • replace

        public TypeV replace​(java.lang.Long key,
                             TypeV Val)
        Auto-boxing version of replace(long, TypeV).
        Specified by:
        replace in interface java.util.concurrent.ConcurrentMap<java.lang.Long,​TypeV>
        Specified by:
        replace in interface java.util.Map<java.lang.Long,​TypeV>
      • put

        public TypeV put​(java.lang.Long key,
                         TypeV val)
        Auto-boxing version of put(long, TypeV).
        Specified by:
        put in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        put in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • replace

        public boolean replace​(java.lang.Long key,
                               TypeV oldValue,
                               TypeV newValue)
        Auto-boxing version of replace(long, TypeV).
        Specified by:
        replace in interface java.util.concurrent.ConcurrentMap<java.lang.Long,​TypeV>
        Specified by:
        replace in interface java.util.Map<java.lang.Long,​TypeV>
      • help_copy

        private void help_copy()
      • 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 a 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.

        Specified by:
        values in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        values in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • 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 a Set view 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.

        Specified by:
        keySet in interface java.util.Map<java.lang.Long,​TypeV>
        Overrides:
        keySet in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • 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 a 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 Map.keySet() or Map.values() will be more efficient. In addition, this version requires auto-boxing the keys.

        Specified by:
        entrySet in interface java.util.Map<java.lang.Long,​TypeV>
        Specified by:
        entrySet in class java.util.AbstractMap<java.lang.Long,​TypeV>
      • 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