LongShortOpenHashMap (HPPC v0.6.0 API Documentation (JavaDoc))

java.lang.Object
- com.carrotsearch.hppc.LongShortOpenHashMap

All Implemented Interfaces:

LongShortAssociativeContainer, LongShortMap, java.lang.Cloneable, java.lang.Iterable<LongShortCursor>
```
@Generated(date="2014-04-08T14:32:52+0200",
           value="HPPC generated from: LongShortOpenHashMap.java")
public class LongShortOpenHashMap
extends java.lang.Object
implements LongShortMap, java.lang.Cloneable
```
A hash map of long to short, 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.

See ObjectObjectOpenHashMap class for API similarities and differences against Java Collections.
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.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

class LongShortOpenHashMap.KeysContainer
A view of the keys inside this hash map.

Nested Classes
Modifier and Type	Class and Description
`class`	`LongShortOpenHashMap.KeysContainer` A view of the keys inside this hash map.

Field Summary

Fields
Modifier and Type	Field and Description
`boolean[]`	`allocated` Information if an entry (slot) in the `values` table is allocated or empty.
`int`	`assigned` Cached number of assigned slots in `allocated`.
`static int`	`DEFAULT_CAPACITY` Default capacity.
`static float`	`DEFAULT_LOAD_FACTOR` Default load factor.
`long[]`	`keys` Hash-indexed array holding all keys.
`protected int`	`lastSlot` The most recent slot accessed in `containsKey(long)` (required for `lget()`).
`float`	`loadFactor` The load factor for this map (fraction of allocated slots before the buffers must be rehashed or reallocated).
`static int`	`MIN_CAPACITY` Minimum capacity for the map.
`protected int`	`perturbation` We perturb hashed values with the array size to avoid problems with nearly-sorted-by-hash values on iterations.
`protected int`	`resizeAt` Resize buffers when `allocated` hits this value.
`short[]`	`values` Hash-indexed array holding all values associated to the keys stored in `keys`.

Constructor Summary

Constructors
Constructor and Description
`LongShortOpenHashMap()` Creates a hash map with the default capacity of 16, load factor of 0.75f.
`LongShortOpenHashMap(int initialCapacity)` Creates a hash map with the given initial capacity, default load factor of 0.75f.
`LongShortOpenHashMap(int initialCapacity, float loadFactor)` Creates a hash map with the given initial capacity, load factor.
`LongShortOpenHashMap(LongShortAssociativeContainer container)` Create a hash map from all key-value pairs of another container.

Method Summary

Methods
Modifier and Type	Method and Description
`short`	`addTo(long key, short additionValue)` An equivalent of calling
`void`	`clear()` Clear all keys and values in the container.
`LongShortOpenHashMap`	`clone()`
`protected int`	`computePerturbationValue(int capacity)` Compute the key perturbation value applied before hashing.
`boolean`	`containsKey(long key)` Returns `true` if this container has an association to a value for the given key.
`boolean`	`equals(java.lang.Object obj)` Compares the specified object with this set for equality.
`<T extends LongShortProcedure> T`	`forEach(T procedure)` Applies a given procedure to all keys-value pairs in this container.
`static LongShortOpenHashMap`	`from(long[] keys, short[] values)` Creates a hash map from two index-aligned arrays of key-value pairs.
`static LongShortOpenHashMap`	`from(LongShortAssociativeContainer container)` Create a hash map from another associative container.
`short`	`get(long key)`
`short`	`getOrDefault(long key, short defaultValue)`
`int`	`hashCode()`
`boolean`	`isEmpty()`
`java.util.Iterator<LongShortCursor>`	`iterator()` Returns a cursor over the entries (key-value pairs) in this map.
`LongShortOpenHashMap.KeysContainer`	`keys()` Returns a specialized view of the keys of this associated container.
`short`	`lget()` Returns the last value saved in a call to `containsKey(long)`.
`short`	`lset(short key)` Sets the value corresponding to the key saved in the last call to `containsKey(long)`, if and only if the key exists in the map already.
`int`	`lslot()`
`static LongShortOpenHashMap`	`newInstance()` Create a new hash map without providing the full generic signature (constructor shortcut).
`static LongShortOpenHashMap`	`newInstance(int initialCapacity, float loadFactor)` Create a new hash map without providing the full generic signature (constructor shortcut).
`static LongShortOpenHashMap`	`newInstanceWithExpectedSize(int expectedSize)` Create a new hash map without providing the full generic signature (constructor shortcut).
`static LongShortOpenHashMap`	`newInstanceWithExpectedSize(int expectedSize, float loadFactor)` Create a new hash map without providing the full generic signature (constructor shortcut).
`static LongShortOpenHashMap`	`newInstanceWithoutPerturbations()` Returns a new object with no key perturbations (see `computePerturbationValue(int)`).
`short`	`put(long key, short value)` Place a given key and value in the container.
`int`	`putAll(java.lang.Iterable<? extends LongShortCursor> iterable)` Puts all key/value pairs from a given iterable into this map.
`int`	`putAll(LongShortAssociativeContainer container)` Puts all keys from another container to this map, replacing the values of existing keys, if such keys are present.
`boolean`	`putIfAbsent(long key, short value)` Trove-inspired API method.
`short`	`putOrAdd(long key, short putValue, short additionValue)` Trove-inspired API method.
`short`	`remove(long key)` Remove all values at the given key.
`int`	`removeAll(LongContainer container)` Removes all keys (and associated values) present in a given container.
`int`	`removeAll(LongPredicate predicate)` Removes all keys (and associated values) for which the predicate returns `true`.
`protected void`	`shiftConflictingKeys(int slotCurr)` Shift all the slot-conflicting keys allocated to (and including) `slot`.
`int`	`size()`
`java.lang.String`	`toString()` Convert the contents of this map to a human-friendly string.
`ShortContainer`	`values()` Returns a container view of all values present in this container.

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

- Field Detail
  - MIN_CAPACITY
```
public static final int MIN_CAPACITY
```
    Minimum capacity for the map.
    
    See Also:
    Constant Field Values
  - DEFAULT_CAPACITY
```
public static final int DEFAULT_CAPACITY
```
    Default capacity.
    
    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 long[] keys
```
    Hash-indexed array holding all keys.
    
    See Also:
    values
  - values
```
public short[] 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.
  - lastSlot
```
protected int lastSlot
```
    The most recent slot accessed in containsKey(long) (required for lget()).
    
    See Also:
    containsKey(long), lget()
  - 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
  - LongShortOpenHashMap
```
public LongShortOpenHashMap()
```
    Creates a hash map with the default capacity of 16, load factor of 0.75f.
    See class notes about hash distribution importance.
  - LongShortOpenHashMap
```
public LongShortOpenHashMap(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).
  - LongShortOpenHashMap
```
public LongShortOpenHashMap(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).
  - LongShortOpenHashMap
```
public LongShortOpenHashMap(LongShortAssociativeContainer container)
```
    Create a hash map from all key-value pairs of another container.
- Method Detail
  - put
```
public short put(long key,
        short value)
```
    Place a given key and value in the container.
    
    Specified by:
    
    put in interface LongShortMap
    
    Returns:
    The value previously stored under the given key in the map is returned.
  - putAll
```
public int putAll(LongShortAssociativeContainer 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 LongShortMap
    
    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 LongShortCursor> iterable)
```
    Puts all key/value pairs from a given iterable into this map.
    
    Specified by:
    
    putAll in interface LongShortMap
    
    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(long key,
                  short value)
```
    Trove-inspired API method. An equivalent of the following code:
```
 if (!map.containsKey(key)) map.put(value);
 
```
    This method saves to lastSlot as a side effect of each call.
    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.
  - putOrAdd
```
public short putOrAdd(long key,
             short putValue,
             short additionValue)
```
    Trove-inspired API method. A logical equivalent of the following code (but does not update #lastSlot):
```
  if (containsKey(key))
  {
      short v = (short) (lget() + additionValue);
      lset(v);
      return v;
  }
  else
  {
     put(key, putValue);
     return putValue;
  }
 
```
    Specified by:
    
    putOrAdd in interface LongShortMap
    
    Parameters:
    key - The key of the value to adjust.
    putValue - The value to put if key does not exist.
    additionValue - The value to add to the existing value if key exists.
    
    Returns:
    Returns the current value associated with key (after changes).
  - addTo
```
public short addTo(long key,
          short additionValue)
```
    An equivalent of calling
```
  if (containsKey(key))
  {
      short v = (short) (lget() + additionValue);
      lset(v);
      return v;
  }
  else
  {
     put(key, additionValue);
     return additionValue;
  }
 
```
    Specified by:
    
    addTo in interface LongShortMap
    
    Parameters:
    key - The key of the value to adjust.
    additionValue - The value to put or add to the existing value if key exists.
    
    Returns:
    Returns the current value associated with key (after changes).
  - 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 short remove(long 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 LongShortMap
  - shiftConflictingKeys
```
protected void shiftConflictingKeys(int slotCurr)
```
    Shift all the slot-conflicting keys allocated to (and including) slot.
  - removeAll
```
public int removeAll(LongContainer 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 LongShortAssociativeContainer
    
    Returns:
    Returns the number of elements actually removed as a result of this call.
  - removeAll
```
public int removeAll(LongPredicate 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 LongShortAssociativeContainer
    
    Returns:
    Returns the number of elements actually removed as a result of this call.
  - get
```
public short get(long 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(); 
 
```
    The above code cannot be used by multiple concurrent threads because a call to #containsKey(Object) stores the temporary slot number in lastSlot. An alternative to the above conditional statement is to use #getOrDefault(Object, Object) and provide a custom default value sentinel (not present in the value set).
    Specified by:
    
    get in interface LongShortMap
    
    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).
  - getOrDefault
```
public short getOrDefault(long key,
                 short defaultValue)
```
    Specified by:
    
    getOrDefault in interface LongShortMap
    
    Returns:
    Returns the value associated with the given key or the provided default value if the key is not associated with any value.
  - lget
```
public short lget()
```
    Returns the last value saved in a call to containsKey(long).
    
    See Also:
    containsKey(long)
  - lset
```
public short lset(short key)
```
    Sets the value corresponding to the key saved in the last call to containsKey(long), if and only if the key exists in the map already.
    
    Returns:
    Returns the previous value stored under the given key.
    See Also:
    containsKey(long)
  - lslot
```
public int lslot()
```
    Returns:
    Returns the slot of the last key looked up in a call to containsKey(long) if it returned true.
    See Also:
    containsKey(long)
  - containsKey
```
public boolean containsKey(long 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(short).
```
 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);
 
```
    *
    Important: containsKey(long) and consecutive lget(), lset(short) or #lkey must not be used by concurrent threads because lastSlot is used to store state.
    Specified by:
    
    containsKey in interface LongShortAssociativeContainer
  - clear
```
public void clear()
```
    Clear all keys and values in the container.
    Does not release internal buffers.
    
    Specified by:
    
    clear in interface LongShortAssociativeContainer
  - size
```
public int size()
```
    Specified by:
    
    size in interface LongShortAssociativeContainer
    
    Returns:
    Returns the current size (number of assigned keys) in the container.
  - 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 LongShortAssociativeContainer
    
    Returns:
    Return true if this hash map contains no assigned keys.
  - hashCode
```
public int hashCode()
```
    Specified by:
    
    hashCode in interface LongShortMap
    
    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 LongShortMap and both objects contains exactly the same key-value pairs.
    
    Specified by:
    
    equals in interface LongShortMap
    
    Overrides:
    
    equals in class java.lang.Object
  - iterator
```
public java.util.Iterator<LongShortCursor> 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 LongShortAssociativeContainer
    
    Specified by:
    
    iterator in interface java.lang.Iterable<LongShortCursor>
  - forEach
```
public <T extends LongShortProcedure> T forEach(T procedure)
```
    Applies a given procedure to all keys-value pairs in this container. Returns the argument (any subclass of LongShortProcedure. This lets the caller to call methods of the argument by chaining the call (even if the argument is an anonymous type) to retrieve computed values, for example.
    
    Specified by:
    
    forEach in interface LongShortAssociativeContainer
  - keys
```
public LongShortOpenHashMap.KeysContainer keys()
```
    Returns a specialized view of the keys of this associated container. The view additionally implements ObjectLookupContainer.
    
    Specified by:
    
    keys in interface LongShortAssociativeContainer
  - values
```
public ShortContainer values()
```
    Description copied from interface: LongShortAssociativeContainer
    
    Returns a container view of all values present in this container. The returned collection is a view over the key set and any modifications (if allowed) introduced to the collection will propagate to the associative container immediately.
    
    Specified by:
    
    values in interface LongShortAssociativeContainer
    
    Returns:
    Returns a container with all values stored in this map.
  - clone
```
public LongShortOpenHashMap clone()
```
    Overrides:
    
    clone in class java.lang.Object
  - 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 LongShortOpenHashMap from(long[] keys,
                        short[] values)
```
    Creates a hash map from two index-aligned arrays of key-value pairs.
  - from
```
public static LongShortOpenHashMap from(LongShortAssociativeContainer container)
```
    Create a hash map from another associative container.
  - newInstance
```
public static LongShortOpenHashMap newInstance()
```
    Create a new hash map without providing the full generic signature (constructor shortcut).
  - newInstanceWithoutPerturbations
```
public static LongShortOpenHashMap 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 LongShortOpenHashMap newInstance(int initialCapacity,
                               float loadFactor)
```
    Create a new hash map without providing the full generic signature (constructor shortcut).
  - newInstanceWithExpectedSize
```
public static LongShortOpenHashMap newInstanceWithExpectedSize(int expectedSize)
```
    Create a new hash map without providing the full generic signature (constructor shortcut). The returned instance will have enough initial capacity to hold expectedSize elements without having to resize.
  - newInstanceWithExpectedSize
```
public static LongShortOpenHashMap newInstanceWithExpectedSize(int expectedSize,
                                               float loadFactor)
```
    Create a new hash map without providing the full generic signature (constructor shortcut). The returned instance will have enough initial capacity to hold expectedSize elements without having to resize.

Class LongShortOpenHashMap

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

MIN_CAPACITY

DEFAULT_CAPACITY

DEFAULT_LOAD_FACTOR

keys

values

allocated

assigned

loadFactor

resizeAt

lastSlot

perturbation

Constructor Detail

LongShortOpenHashMap

LongShortOpenHashMap

LongShortOpenHashMap

LongShortOpenHashMap

Method Detail

put

putAll

putAll

putIfAbsent

putOrAdd

addTo

computePerturbationValue

remove

shiftConflictingKeys

removeAll

removeAll

get

getOrDefault

lget

lset

lslot

containsKey

clear

size

isEmpty

hashCode

equals

iterator

forEach

keys

values

clone

toString

from

from

newInstance

newInstanceWithoutPerturbations

newInstance

newInstanceWithExpectedSize

newInstanceWithExpectedSize