com.carrotsearch.hppc

Class ObjectObjectOpenHashMap<KType,VType>

  • java.lang.Object
    • com.carrotsearch.hppc.ObjectObjectOpenHashMap<KType,VType>
  • All Implemented Interfaces:
    ObjectObjectAssociativeContainer<KType,VType>, ObjectObjectMap<KType,VType>, java.lang.Cloneable, java.lang.Iterable<ObjectObjectCursor<KType,VType>>


    @Generated(date="2013-07-09T09:54:21+0200",           value="HPPC generated from: ObjectObjectOpenHashMap.java")public class ObjectObjectOpenHashMap<KType,VType>extends java.lang.Objectimplements ObjectObjectMap<KType,VType>, java.lang.Cloneable
    A hash map of KType to VType, implemented using open addressing with linear probing for collision resolution.

    The internal buffers of this implementation (keys, values, allocated) are always allocated to the nearest size that is a power of two. When the capacity exceeds the given load factor, the buffer size is doubled.

    A brief comparison of the API against the Java Collections framework:

    Java Collections HashMap and HPPC ObjectObjectOpenHashMap, related methods.
    java.util.HashMap ObjectObjectOpenHashMap
    V put(K) V put(K)
    V get(K) V get(K)
    V remove(K) V remove(K)
    size, clear, isEmptysize, clear, isEmpty
    containsKey(K) containsKey(K), lget()
    containsValue(K) (no efficient equivalent)
    keySet, entrySet iterator over map entries, keySet, pseudo-closures

    This implementation supports null keys.

    This implementation supports null values.

    Important node. The implementation uses power-of-two tables and linear probing, which may cause poor performance (many collisions) if hash values are not properly distributed. This implementation uses rehashing using MurmurHash3.

    Author:
    This code is inspired by the collaboration and implementation in the fastutil project.
    • Field Detail

      • MIN_CAPACITY

        public static final int MIN_CAPACITY
        Minimum capacity for the map.
        See Also:
        Constant Field Values
      • DEFAULT_LOAD_FACTOR

        public static final float DEFAULT_LOAD_FACTOR
        Default load factor.
        See Also:
        Constant Field Values
      • keys

        public KType[] keys
        Hash-indexed array holding all keys.
        See Also:
        values
      • values

        public VType[] values
        Hash-indexed array holding all values associated to the keys stored in keys.
        See Also:
        keys
      • allocated

        public boolean[] allocated
        Information if an entry (slot) in the values table is allocated or empty.
        See Also:
        assigned
      • assigned

        public int assigned
        Cached number of assigned slots in allocated.
      • loadFactor

        public final float loadFactor
        The load factor for this map (fraction of allocated slots before the buffers must be rehashed or reallocated).
      • resizeAt

        protected int resizeAt
        Resize buffers when allocated hits this value.
      • perturbation

        protected int perturbation
        We perturb hashed values with the array size to avoid problems with nearly-sorted-by-hash values on iterations.
        See Also:
        "http://issues.carrot2.org/browse/HPPC-80"
    • Constructor Detail

      • ObjectObjectOpenHashMap

        public ObjectObjectOpenHashMap()
        Creates a hash map with the default capacity of 16, load factor of 0.75f.

        See class notes about hash distribution importance.

      • ObjectObjectOpenHashMap

        public ObjectObjectOpenHashMap(int initialCapacity)
        Creates a hash map with the given initial capacity, default load factor of 0.75f.

        See class notes about hash distribution importance.

        Parameters:
        initialCapacity - Initial capacity (greater than zero and automatically rounded to the next power of two).
      • ObjectObjectOpenHashMap

        public ObjectObjectOpenHashMap(int initialCapacity,                       float loadFactor)
        Creates a hash map with the given initial capacity, load factor.

        See class notes about hash distribution importance.

        Parameters:
        initialCapacity - Initial capacity (greater than zero and automatically rounded to the next power of two).
        loadFactor - The load factor (greater than zero and smaller than 1).
    • Method Detail

      • put

        public VType put(KType key,        VType value)
        Place a given key and value in the container.
        Specified by:
        put in interface ObjectObjectMap<KType,VType>
        Returns:
        The value previously stored under the given key in the map is returned.
      • putAll

        public int putAll(ObjectObjectAssociativeContainer<? extends KType,? extends VType> container)
        Puts all keys from another container to this map, replacing the values of existing keys, if such keys are present.
        Specified by:
        putAll in interface ObjectObjectMap<KType,VType>
        Returns:
        Returns the number of keys added to the map as a result of this call (not previously present in the map). Values of existing keys are overwritten.
      • putAll

        public int putAll(java.lang.Iterable<? extends ObjectObjectCursor<? extends KType,? extends VType>> iterable)
        Puts all key/value pairs from a given iterable into this map.
        Specified by:
        putAll in interface ObjectObjectMap<KType,VType>
        Returns:
        Returns the number of keys added to the map as a result of this call (not previously present in the map). Values of existing keys are overwritten.
      • putIfAbsent

        public boolean putIfAbsent(KType key,                  VType value)
        Trove-inspired API method. An equivalent of the following code:
         if (!map.containsKey(key)) map.put(value); 
        Parameters:
        key - The key of the value to check.
        value - The value to put if key does not exist.
        Returns:
        true if key did not exist and value was placed in the map.
      • computePerturbationValue

        protected int computePerturbationValue(int capacity)

        Compute the key perturbation value applied before hashing. The returned value should be non-zero and ideally different for each capacity. This matters because keys are nearly-ordered by their hashed values so when adding one container's values to the other, the number of collisions can skyrocket into the worst case possible.

        If it is known that hash containers will not be added to each other (will be used for counting only, for example) then some speed can be gained by not perturbing keys before hashing and returning a value of zero for all possible capacities. The speed gain is a result of faster rehash operation (keys are mostly in order).

      • remove

        public VType remove(KType key)
        Remove all values at the given key. The default value for the key type is returned if the value does not exist in the map.
        Specified by:
        remove in interface ObjectObjectMap<KType,VType>
      • shiftConflictingKeys

        protected void shiftConflictingKeys(int slotCurr)
        Shift all the slot-conflicting keys allocated to (and including) slot.
      • removeAll

        public int removeAll(ObjectContainer<? extends KType> container)
        Removes all keys (and associated values) present in a given container. An alias to:
         keys().removeAll(container) 
        but with no additional overhead.
        Specified by:
        removeAll in interface ObjectObjectAssociativeContainer<KType,VType>
        Returns:
        Returns the number of elements actually removed as a result of this call.
      • removeAll

        public int removeAll(ObjectPredicate<? super KType> predicate)
        Removes all keys (and associated values) for which the predicate returns true. An alias to:
         keys().removeAll(container) 
        but with no additional overhead.
        Specified by:
        removeAll in interface ObjectObjectAssociativeContainer<KType,VType>
        Returns:
        Returns the number of elements actually removed as a result of this call.
      • get

        public VType get(KType key)

        Use the following snippet of code to check for key existence first and then retrieve the value if it exists.

         if (map.containsKey(key))   value = map.lget();  
        Specified by:
        get in interface ObjectObjectMap<KType,VType>
        Returns:
        Returns the value associated with the given key or the default value for the key type, if the key is not associated with any value. Important note: For primitive type values, the value returned for a non-existing key may not be the default value of the primitive type (it may be any value previously assigned to that slot).
      • lkey

        public KType lkey()
        Returns the last key stored in this has map for the corresponding most recent call to containsKey(KType).

        Use the following snippet of code to check for key existence first and then retrieve the key value if it exists.

         if (map.containsKey(key))   value = map.lkey();  

        This is equivalent to calling:

         if (map.containsKey(key))   key = map.keys[map.lslot()]; 
      • lset

        public VType lset(VType key)
        Sets the value corresponding to the key saved in the last call to containsKey(KType), if and only if the key exists in the map already.
        Returns:
        Returns the previous value stored under the given key.
        See Also:
        containsKey(KType)
      • containsKey

        public boolean containsKey(KType key)
        Returns true if this container has an association to a value for the given key.

        Saves the associated value for fast access using lget() or lset(VType).

         if (map.containsKey(key))   value = map.lget(); 
        or, to modify the value at the given key without looking up its slot twice:
         if (map.containsKey(key))   map.lset(map.lget() + 1); 
        or, to retrieve the key-equivalent object from the map:
         if (map.containsKey(key))   map.lkey(); 
        Specified by:
        containsKey in interface ObjectObjectAssociativeContainer<KType,VType>
      • isEmpty

        public boolean isEmpty()

        Note that an empty container may still contain many deleted keys (that occupy buffer space). Adding even a single element to such a container may cause rehashing.

        Specified by:
        isEmpty in interface ObjectObjectAssociativeContainer<KType,VType>
        Returns:
        Return true if this hash map contains no assigned keys.
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface ObjectObjectMap<KType,VType>
        Overrides:
        hashCode in class java.lang.Object
        Returns:
        A hash code of elements stored in the map. The hash code is defined as a sum of hash codes of keys and values stored within the set). Because sum is commutative, this ensures that different order of elements in a set does not affect the hash code.
      • equals

        public boolean equals(java.lang.Object obj)
        Compares the specified object with this set for equality. Returns true if and only if the specified object is also a ObjectObjectMap and both objects contains exactly the same key-value pairs.
        Specified by:
        equals in interface ObjectObjectMap<KType,VType>
        Overrides:
        equals in class java.lang.Object
      • iterator

        public java.util.Iterator<ObjectObjectCursor<KType,VType>> iterator()
        Returns a cursor over the entries (key-value pairs) in this map. The iterator is implemented as a cursor and it returns the same cursor instance on every call to Iterator.next(). To read the current key and value use the cursor's public fields. An example is shown below.
         for (IntShortCursor c : intShortMap) {     System.out.println("index=" + c.index        + " key=" + c.key       + " value=" + c.value); } 

        The index field inside the cursor gives the internal index inside the container's implementation. The interpretation of this index depends on to the container.

        Specified by:
        iterator in interface ObjectObjectAssociativeContainer<KType,VType>
        Specified by:
        iterator in interface java.lang.Iterable<ObjectObjectCursor<KType,VType>>
      • toString

        public java.lang.String toString()
        Convert the contents of this map to a human-friendly string.
        Overrides:
        toString in class java.lang.Object
      • from

        public static <KType,VType> ObjectObjectOpenHashMap<KType,VType> from(KType[] keys,                                                      VType[] values)
        Creates a hash map from two index-aligned arrays of key-value pairs.
      • newInstance

        public static <KType,VType> ObjectObjectOpenHashMap<KType,VType> newInstance()
        Create a new hash map without providing the full generic signature (constructor shortcut).
      • newInstanceWithoutPerturbations

        public static <KType,VType> ObjectObjectOpenHashMap<KType,VType> newInstanceWithoutPerturbations()
        Returns a new object with no key perturbations (see computePerturbationValue(int)). Only use when sure the container will not be used for direct copying of keys to another hash container.
      • newInstance

        public static <KType,VType> ObjectObjectOpenHashMap<KType,VType> newInstance(int initialCapacity,                                                             float loadFactor)
        Create a new hash map without providing the full generic signature (constructor shortcut).

Copyright © 2013 Carrot Search s.c.. All Rights Reserved.



NOTHING
NOTHING
Add the Maven Dependecy to your project: maven dependecy for com.amazonaws : aws-java-sdk : 1.3.14