V
- The value type stored in the map.public class IntObjectHashMap<V> extends java.lang.Object implements IntObjectMap<V>, java.lang.Iterable<IntObjectMap.Entry<V>>
IntObjectMap
that uses open addressing for keys.
To minimize the memory footprint, this class uses open addressing rather than chaining.
Collisions are resolved using linear probing. Deletions implement compaction, so cost of
remove can approach O(N) for full maps, which makes a small loadFactor recommended.Modifier and Type | Class and Description |
---|---|
private class |
IntObjectHashMap.IteratorImpl
Iterator for traversing the entries in this map.
|
IntObjectMap.Entry<V>
Modifier and Type | Field and Description |
---|---|
private static int |
DEFAULT_CAPACITY
Default initial capacity.
|
private static float |
DEFAULT_LOAD_FACTOR
Default load factor.
|
private int[] |
keys |
private float |
loadFactor
The load factor for the map.
|
private int |
maxSize
The maximum number of elements allowed without allocating more space.
|
private static java.lang.Object |
NULL_VALUE
Placeholder for null values, so we can use the actual null to mean available.
|
private int |
size |
private java.util.Collection<V> |
valueCollection |
private V[] |
values |
Constructor and Description |
---|
IntObjectHashMap() |
IntObjectHashMap(int initialCapacity) |
IntObjectHashMap(int initialCapacity,
float loadFactor) |
Modifier and Type | Method and Description |
---|---|
private static int |
adjustCapacity(int capacity)
Adjusts the given capacity value to ensure that it's odd.
|
private int |
calcMaxSize(int capacity)
Calculates the maximum size allowed before rehashing.
|
void |
clear()
Clears all entries from this map.
|
boolean |
containsKey(int key)
Indicates whether or not this map contains a value for the specified key.
|
boolean |
containsValue(V value)
Indicates whether or not the map contains the specified value.
|
java.lang.Iterable<IntObjectMap.Entry<V>> |
entries()
Gets an iterable collection of the entries contained in this map.
|
boolean |
equals(java.lang.Object obj) |
V |
get(int key)
Gets the value in the map with the specified key.
|
private void |
growSize()
Grows the map size after an insertion.
|
int |
hashCode() |
private int |
hashIndex(int key)
Returns the hashed index for the given key.
|
private int |
indexOf(int key)
Locates the index for the given key.
|
boolean |
isEmpty()
Indicates whether or not this map is empty (i.e
IntObjectMap.size() == {@code 0]). |
java.util.Iterator<IntObjectMap.Entry<V>> |
iterator() |
int[] |
keys()
Gets the keys contained in this map.
|
protected java.lang.String |
keyToString(int key)
Helper method called by
toString() in order to convert a single map key into a string. |
private int |
probeNext(int index) |
V |
put(int key,
V value)
Puts the given entry into the map.
|
void |
putAll(IntObjectMap<V> sourceMap)
Puts all of the entries from the given map into this map.
|
private void |
rehash(int newCapacity)
Rehashes the map for the given capacity.
|
V |
remove(int key)
Removes the entry with the specified key.
|
private void |
removeAt(int index)
Removes entry at the given index position.
|
int |
size()
Returns the number of entries contained in this map.
|
private static <T> T |
toExternal(T value) |
private static <T> T |
toInternal(T value) |
java.lang.String |
toString() |
java.util.Collection<V> |
values()
Gets the values contatins in this map as a
Collection . |
V[] |
values(java.lang.Class<V> clazz)
Gets the values contained in this map.
|
private static final int DEFAULT_CAPACITY
private static final float DEFAULT_LOAD_FACTOR
private static final java.lang.Object NULL_VALUE
private int maxSize
private final float loadFactor
maxSize
.private int[] keys
private V[] values
private java.util.Collection<V> valueCollection
private int size
public IntObjectHashMap()
public IntObjectHashMap(int initialCapacity)
public IntObjectHashMap(int initialCapacity, float loadFactor)
private static <T> T toExternal(T value)
private static <T> T toInternal(T value)
public V get(int key)
IntObjectMap
get
in interface IntObjectMap<V>
key
- the key whose associated value is to be returned.null
if the key was not found in the map.public V put(int key, V value)
IntObjectMap
put
in interface IntObjectMap<V>
key
- the key of the entry.value
- the value of the entry.null
if there was no previous mapping.private int probeNext(int index)
public void putAll(IntObjectMap<V> sourceMap)
IntObjectMap
putAll
in interface IntObjectMap<V>
public V remove(int key)
IntObjectMap
remove
in interface IntObjectMap<V>
key
- the key for the entry to be removed from this map.null
if there was no mapping.public int size()
IntObjectMap
size
in interface IntObjectMap<V>
public boolean isEmpty()
IntObjectMap
IntObjectMap.size()
== {@code 0]).isEmpty
in interface IntObjectMap<V>
public void clear()
IntObjectMap
clear
in interface IntObjectMap<V>
public boolean containsKey(int key)
IntObjectMap
containsKey
in interface IntObjectMap<V>
public boolean containsValue(V value)
IntObjectMap
containsValue
in interface IntObjectMap<V>
public java.lang.Iterable<IntObjectMap.Entry<V>> entries()
IntObjectMap
entries
in interface IntObjectMap<V>
public java.util.Iterator<IntObjectMap.Entry<V>> iterator()
iterator
in interface java.lang.Iterable<IntObjectMap.Entry<V>>
public int[] keys()
IntObjectMap
keys
in interface IntObjectMap<V>
public V[] values(java.lang.Class<V> clazz)
IntObjectMap
values
in interface IntObjectMap<V>
public java.util.Collection<V> values()
IntObjectMap
Collection
.values
in interface IntObjectMap<V>
public int hashCode()
hashCode
in class java.lang.Object
public boolean equals(java.lang.Object obj)
equals
in class java.lang.Object
private int indexOf(int key)
key
- the key for an entry in the map.-1
if no entry is found for that key.private int hashIndex(int key)
private void growSize()
private static int adjustCapacity(int capacity)
private void removeAt(int index)
index
- the index position of the element to remove.private int calcMaxSize(int capacity)
private void rehash(int newCapacity)
newCapacity
- the new capacity for the map.public java.lang.String toString()
toString
in class java.lang.Object
protected java.lang.String keyToString(int key)
toString()
in order to convert a single map key into a string.