@Generated(date="2015-06-17T12:23:41+0000", value="HPPC generated from: ObjectLongOpenHashMap.java") public class ObjectLongOpenHashMap<KType> extends java.lang.Object implements ObjectLongMap<KType>, java.lang.Cloneable
KType
to long
, 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.
This implementation supports null
keys.
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
.
Modifier and Type | Class and Description |
---|---|
class |
ObjectLongOpenHashMap.KeysContainer
A view of the keys inside this hash map.
|
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.
|
KType[] |
keys
Hash-indexed array holding all keys.
|
protected int |
lastSlot
The most recent slot accessed in
containsKey(KType) (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. |
long[] |
values
Hash-indexed array holding all values associated to the keys
stored in
keys . |
Constructor and Description |
---|
ObjectLongOpenHashMap()
|
ObjectLongOpenHashMap(int initialCapacity)
Creates a hash map with the given initial capacity, default load factor of
0.75f.
|
ObjectLongOpenHashMap(int initialCapacity,
float loadFactor)
Creates a hash map with the given initial capacity,
load factor.
|
ObjectLongOpenHashMap(ObjectLongAssociativeContainer<KType> container)
Create a hash map from all key-value pairs of another container.
|
Modifier and Type | Method and Description |
---|---|
long |
addTo(KType key,
long additionValue)
An equivalent of calling
|
void |
clear()
Clear all keys and values in the container.
|
ObjectLongOpenHashMap<KType> |
clone() |
protected int |
computePerturbationValue(int capacity)
Compute the key perturbation value applied before hashing.
|
boolean |
containsKey(KType 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 ObjectLongProcedure<? super KType>> |
forEach(T procedure)
Applies a given procedure to all keys-value pairs in this container.
|
static <KType> ObjectLongOpenHashMap<KType> |
from(KType[] keys,
long[] values)
Creates a hash map from two index-aligned arrays of key-value pairs.
|
static <KType> ObjectLongOpenHashMap<KType> |
from(ObjectLongAssociativeContainer<KType> container)
Create a hash map from another associative container.
|
long |
get(KType key) |
long |
getOrDefault(KType key,
long defaultValue) |
int |
hashCode() |
boolean |
isEmpty() |
java.util.Iterator<ObjectLongCursor<KType>> |
iterator()
Returns a cursor over the entries (key-value pairs) in this map.
|
ObjectLongOpenHashMap.KeysContainer |
keys()
Returns a specialized view of the keys of this associated container.
|
long |
lget()
Returns the last value saved in a call to
containsKey(KType) . |
KType |
lkey()
Returns the last key stored in this has map for the corresponding
most recent call to
containsKey(KType) . |
long |
lset(long 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. |
int |
lslot() |
static <KType> ObjectLongOpenHashMap<KType> |
newInstance()
Create a new hash map without providing the full generic signature (constructor
shortcut).
|
static <KType> ObjectLongOpenHashMap<KType> |
newInstance(int initialCapacity,
float loadFactor)
Create a new hash map without providing the full generic signature (constructor
shortcut).
|
static <KType> ObjectLongOpenHashMap<KType> |
newInstanceWithExpectedSize(int expectedSize)
Create a new hash map without providing the full generic signature (constructor
shortcut).
|
static <KType> ObjectLongOpenHashMap<KType> |
newInstanceWithExpectedSize(int expectedSize,
float loadFactor)
Create a new hash map without providing the full generic signature (constructor
shortcut).
|
static <KType> ObjectLongOpenHashMap<KType> |
newInstanceWithoutPerturbations()
Returns a new object with no key perturbations (see
computePerturbationValue(int) ). |
long |
put(KType key,
long value)
Place a given key and value in the container.
|
int |
putAll(java.lang.Iterable<? extends ObjectLongCursor<? extends KType>> iterable)
Puts all key/value pairs from a given iterable into this map.
|
int |
putAll(ObjectLongAssociativeContainer<? extends KType> container)
Puts all keys from another container to this map, replacing the values
of existing keys, if such keys are present.
|
boolean |
putIfAbsent(KType key,
long value)
Trove-inspired API method.
|
long |
putOrAdd(KType key,
long putValue,
long additionValue)
Trove-inspired API method.
|
long |
remove(KType key)
Remove all values at the given key.
|
int |
removeAll(ObjectContainer<? extends KType> container)
Removes all keys (and associated values) present in a given container.
|
int |
removeAll(ObjectPredicate<? super KType> 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.
|
LongContainer |
values()
Returns a container view of all values present in this container.
|
public static final int MIN_CAPACITY
public static final int DEFAULT_CAPACITY
public static final float DEFAULT_LOAD_FACTOR
public KType[] keys
Important!
The actual value in this field is always an instance of Object[]
.
Be warned that javac
emits additional casts when keys
are directly accessed; these casts
may result in exceptions at runtime. A workaround is to cast directly to
Object[]
before accessing the buffer's elements (although it is highly
recommended to use a iterator()
instead.
values
public long[] values
keys
.
Important!
The actual value in this field is always an instance of Object[]
.
Be warned that javac
emits additional casts when values
are directly accessed; these casts
may result in exceptions at runtime. A workaround is to cast directly to
Object[]
before accessing the buffer's elements (although it is highly
recommended to use a iterator()
instead.
keys
public boolean[] allocated
values
table is allocated
or empty.assigned
public int assigned
allocated
.public final float loadFactor
protected int resizeAt
allocated
hits this value.protected int lastSlot
containsKey(KType)
(required for
lget()
).containsKey(KType)
,
lget()
protected int perturbation
public ObjectLongOpenHashMap()
public ObjectLongOpenHashMap(int initialCapacity)
See class notes about hash distribution importance.
initialCapacity
- Initial capacity (greater than zero and automatically
rounded to the next power of two).public ObjectLongOpenHashMap(int initialCapacity, float loadFactor)
See class notes about hash distribution importance.
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).public ObjectLongOpenHashMap(ObjectLongAssociativeContainer<KType> container)
public long put(KType key, long value)
put
in interface ObjectLongMap<KType>
public int putAll(ObjectLongAssociativeContainer<? extends KType> container)
putAll
in interface ObjectLongMap<KType>
public int putAll(java.lang.Iterable<? extends ObjectLongCursor<? extends KType>> iterable)
putAll
in interface ObjectLongMap<KType>
public boolean putIfAbsent(KType key, long value)
if (!map.containsKey(key)) map.put(value);
This method saves to lastSlot
as a side effect of each call.
key
- The key of the value to check.value
- The value to put if key
does not exist.true
if key
did not exist and value
was placed in the map.public long putOrAdd(KType key, long putValue, long additionValue)
lastSlot
):
if (containsKey(key)) { long v = (long) (lget() + additionValue); lset(v); return v; } else { put(key, putValue); return putValue; }
putOrAdd
in interface ObjectLongMap<KType>
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.key
(after changes).public long addTo(KType key, long additionValue)
if (containsKey(key)) { long v = (long) (lget() + additionValue); lset(v); return v; } else { put(key, additionValue); return additionValue; }
addTo
in interface ObjectLongMap<KType>
key
- The key of the value to adjust.additionValue
- The value to put or add to the existing value if key
exists.key
(after changes).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).
public long remove(KType key)
remove
in interface ObjectLongMap<KType>
protected void shiftConflictingKeys(int slotCurr)
slot
.public int removeAll(ObjectContainer<? extends KType> container)
keys().removeAll(container)but with no additional overhead.
removeAll
in interface ObjectLongAssociativeContainer<KType>
public int removeAll(ObjectPredicate<? super KType> predicate)
true
.
An alias to:
keys().removeAll(container)but with no additional overhead.
removeAll
in interface ObjectLongAssociativeContainer<KType>
public long 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();
The above code cannot be used by multiple concurrent
threads because a call to containsKey(KType)
stores
the temporary slot number in lastSlot
. An alternative to the above
conditional statement is to use getOrDefault(KType, long)
and
provide a custom default value sentinel (not present in the value set).
get
in interface ObjectLongMap<KType>
public long getOrDefault(KType key, long defaultValue)
getOrDefault
in interface ObjectLongMap<KType>
public KType lkey()
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()];
public long lget()
containsKey(KType)
.containsKey(KType)
public long lset(long key)
containsKey(KType)
, if and only if the key exists
in the map already.containsKey(KType)
public int lslot()
containsKey(KType)
if
it returned true
.containsKey(KType)
public boolean containsKey(KType key)
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(long)
.
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();* *
Important: containsKey(KType)
and consecutive lget()
, lset(long)
or lkey()
must not be used by concurrent threads because lastSlot
is
used to store state.
containsKey
in interface ObjectLongAssociativeContainer<KType>
public void clear()
Does not release internal buffers.
clear
in interface ObjectLongAssociativeContainer<KType>
public int size()
size
in interface ObjectLongAssociativeContainer<KType>
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.
isEmpty
in interface ObjectLongAssociativeContainer<KType>
true
if this hash map contains no assigned keys.public int hashCode()
hashCode
in interface ObjectLongMap<KType>
hashCode
in class java.lang.Object
public boolean equals(java.lang.Object obj)
ObjectLongMap
and both objects contains exactly the same key-value pairs.equals
in interface ObjectLongMap<KType>
equals
in class java.lang.Object
public java.util.Iterator<ObjectLongCursor<KType>> iterator()
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.
iterator
in interface ObjectLongAssociativeContainer<KType>
iterator
in interface java.lang.Iterable<ObjectLongCursor<KType>>
public <T extends ObjectLongProcedure<? super KType>> T forEach(T procedure)
ObjectLongProcedure
. 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.forEach
in interface ObjectLongAssociativeContainer<KType>
public ObjectLongOpenHashMap.KeysContainer keys()
ObjectLookupContainer
.keys
in interface ObjectLongAssociativeContainer<KType>
public LongContainer values()
ObjectLongAssociativeContainer
values
in interface ObjectLongAssociativeContainer<KType>
public ObjectLongOpenHashMap<KType> clone()
clone
in class java.lang.Object
public java.lang.String toString()
toString
in class java.lang.Object
public static <KType> ObjectLongOpenHashMap<KType> from(KType[] keys, long[] values)
public static <KType> ObjectLongOpenHashMap<KType> from(ObjectLongAssociativeContainer<KType> container)
public static <KType> ObjectLongOpenHashMap<KType> newInstance()
public static <KType> ObjectLongOpenHashMap<KType> newInstanceWithoutPerturbations()
computePerturbationValue(int)
). Only use when sure the container will not
be used for direct copying of keys to another hash container.public static <KType> ObjectLongOpenHashMap<KType> newInstance(int initialCapacity, float loadFactor)
public static <KType> ObjectLongOpenHashMap<KType> newInstanceWithExpectedSize(int expectedSize)
expectedSize
elements without having to resize.public static <KType> ObjectLongOpenHashMap<KType> newInstanceWithExpectedSize(int expectedSize, float loadFactor)
expectedSize
elements without having to resize.Copyright © 2015 Carrot Search s.c.. All rights reserved.