|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object com.carrotsearch.hppc.KTypeVTypeOpenHashMap<KType,VType>
public class KTypeVTypeOpenHashMap<KType,VType>
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.util.HashMap | ObjectObjectOpenHashMap |
---|---|
V put(K) | V put(K) |
V get(K) | V get(K) |
V remove(K) | V remove(K) |
size, clear, isEmpty | size, clear, isEmpty |
containsKey(K) | containsKey(K), lget() |
containsValue(K) | (no efficient equivalent) |
keySet, entrySet | iterator over map entries, keySet, pseudo-closures |
See ObjectObjectOpenHashMap
class for API similarities and differences against Java
Collections.
#end
#if ($TemplateOptions.KTypeGeneric)
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
.
Nested Class Summary | |
---|---|
class |
KTypeVTypeOpenHashMap.KeysContainer
A view of the keys inside this hash map. |
Field Summary | |
---|---|
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. |
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. |
VType[] |
values
Hash-indexed array holding all values associated to the keys stored in keys . |
Constructor Summary | |
---|---|
KTypeVTypeOpenHashMap()
Creates a hash map with the default capacity of 16, load factor of 0.75f. |
|
KTypeVTypeOpenHashMap(int initialCapacity)
Creates a hash map with the given initial capacity, default load factor of 0.75f. |
|
KTypeVTypeOpenHashMap(int initialCapacity,
float loadFactor)
Creates a hash map with the given initial capacity, load factor. |
|
KTypeVTypeOpenHashMap(KTypeVTypeAssociativeContainer<KType,VType> container)
Create a hash map from all key-value pairs of another container. |
Method Summary | ||
---|---|---|
void |
clear()
Clear all keys and values in the container. |
|
KTypeVTypeOpenHashMap<KType,VType> |
clone()
|
|
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. |
|
|
forEach(T procedure)
Applies a given procedure to all keys-value pairs in this container. |
|
static
|
from(KType[] keys,
VType[] values)
Creates a hash map from two index-aligned arrays of key-value pairs. |
|
static
|
from(KTypeVTypeAssociativeContainer<KType,VType> container)
Create a hash map from another associative container. |
|
VType |
get(KType key)
|
|
int |
hashCode()
|
|
boolean |
isEmpty()
|
|
java.util.Iterator<KTypeVTypeCursor<KType,VType>> |
iterator()
Returns a cursor over the entries (key-value pairs) in this map. |
|
KTypeVTypeOpenHashMap.KeysContainer |
keys()
Returns a specialized view of the keys of this associated container. |
|
VType |
lget()
Returns the last value saved in a call to containsKey(KType) . |
|
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. |
|
static
|
newInstance()
Create a new hash map without providing the full generic signature (constructor shortcut). |
|
static
|
newInstance(int initialCapacity,
float loadFactor)
Create a new hash map without providing the full generic signature (constructor shortcut). |
|
protected int |
nextCapacity(int current)
Return the next possible capacity, counting from the current buffers' size. |
|
VType |
put(KType key,
VType value)
Place a given key and value in the container. |
|
int |
putAll(java.lang.Iterable<? extends KTypeVTypeCursor<? extends KType,? extends VType>> iterable)
Puts all key/value pairs from a given iterable into this map. |
|
int |
putAll(KTypeVTypeAssociativeContainer<? 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. |
|
boolean |
putIfAbsent(KType key,
VType value)
Trove-inspired API method. |
|
VType |
remove(KType key)
Remove all values at the given key. |
|
int |
removeAll(KTypeContainer<? extends KType> container)
Removes all keys (and associated values) present in a given container. |
|
int |
removeAll(KTypePredicate<? super KType> predicate)
Removes all keys (and associated values) for which the predicate returns true . |
|
protected int |
roundCapacity(int requestedCapacity)
Round the capacity to the next allowed value. |
|
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. |
|
KTypeContainer<VType> |
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 |
---|
public static final int DEFAULT_CAPACITY
public static final int MIN_CAPACITY
public static final float DEFAULT_LOAD_FACTOR
public KType[] keys
values
public VType[] values
keys
.
keys
public boolean[] allocated
values
table is allocated
or empty.
assigned
public int assigned
allocated
.
public final float loadFactor
Constructor Detail |
---|
public KTypeVTypeOpenHashMap()
See class notes about hash distribution importance.
public KTypeVTypeOpenHashMap(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 KTypeVTypeOpenHashMap(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 KTypeVTypeOpenHashMap(KTypeVTypeAssociativeContainer<KType,VType> container)
Method Detail |
---|
public VType put(KType key, VType value)
put
in interface KTypeVTypeMap<KType,VType>
public final int putAll(KTypeVTypeAssociativeContainer<? extends KType,? extends VType> container)
putAll
in interface KTypeVTypeMap<KType,VType>
public final int putAll(java.lang.Iterable<? extends KTypeVTypeCursor<? extends KType,? extends VType>> iterable)
putAll
in interface KTypeVTypeMap<KType,VType>
public final boolean putIfAbsent(KType key, VType value)
if (!map.containsKey(key)) map.put(value);
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 VType remove(KType key)
remove
in interface KTypeVTypeMap<KType,VType>
protected final void shiftConflictingKeys(int slotCurr)
slot
.
public final int removeAll(KTypeContainer<? extends KType> container)
keys().removeAll(container)but with no additional overhead.
removeAll
in interface KTypeVTypeAssociativeContainer<KType,VType>
public final int removeAll(KTypePredicate<? super KType> predicate)
true
.
An alias to:
keys().removeAll(container)but with no additional overhead.
removeAll
in interface KTypeVTypeAssociativeContainer<KType,VType>
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();
get
in interface KTypeVTypeMap<KType,VType>
public VType lget()
containsKey(KType)
.
containsKey(KType)
public VType lset(VType key)
containsKey(KType)
, if and only if the key exists
in the map already.
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(VType)
.
if (map.containsKey(key)) value = map.lget();or, for example to modify the value at the given key without looking up its slot twice:
if (map.containsKey(key)) map.lset(map.lget() + 1);
containsKey
in interface KTypeVTypeAssociativeContainer<KType,VType>
protected int roundCapacity(int requestedCapacity)
protected int nextCapacity(int current)
public void clear()
Does not release internal buffers.
clear
in interface KTypeVTypeAssociativeContainer<KType,VType>
public int size()
size
in interface KTypeVTypeAssociativeContainer<KType,VType>
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 KTypeVTypeAssociativeContainer<KType,VType>
true
if this hash map contains no assigned keys.public int hashCode()
hashCode
in interface KTypeVTypeMap<KType,VType>
hashCode
in class java.lang.Object
public boolean equals(java.lang.Object obj)
KTypeVTypeMap
and both objects contains exactly the same key-value pairs.
equals
in interface KTypeVTypeMap<KType,VType>
equals
in class java.lang.Object
public java.util.Iterator<KTypeVTypeCursor<KType,VType>> 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 KTypeVTypeAssociativeContainer<KType,VType>
iterator
in interface java.lang.Iterable<KTypeVTypeCursor<KType,VType>>
public <T extends KTypeVTypeProcedure<? super KType,? super VType>> T forEach(T procedure)
KTypeVTypeProcedure
. 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 KTypeVTypeAssociativeContainer<KType,VType>
public KTypeVTypeOpenHashMap.KeysContainer keys()
ObjectLookupContainer
.
keys
in interface KTypeVTypeAssociativeContainer<KType,VType>
public KTypeContainer<VType> values()
KTypeVTypeAssociativeContainer
values
in interface KTypeVTypeAssociativeContainer<KType,VType>
public KTypeVTypeOpenHashMap<KType,VType> clone()
clone
in class java.lang.Object
public java.lang.String toString()
toString
in class java.lang.Object
public static <KType,VType> KTypeVTypeOpenHashMap<KType,VType> from(KType[] keys, VType[] values)
public static <KType,VType> KTypeVTypeOpenHashMap<KType,VType> from(KTypeVTypeAssociativeContainer<KType,VType> container)
public static <KType,VType> KTypeVTypeOpenHashMap<KType,VType> newInstance()
public static <KType,VType> KTypeVTypeOpenHashMap<KType,VType> newInstance(int initialCapacity, float loadFactor)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |