This class performs fast contains and remove (typically O(1), worst case O(n) but that is rare in practice). Add may be slightly slower, depending on hash collisions. Hashcodes are rehashed to reduce collisions and the need to resize. Load factors greater than 0.91 greatly increase the chances to resize to the next higher POT size.
Unordered sets and maps are not designed to provide especially fast iteration. Iteration is faster with OrderedSet and OrderedMap.
This implementation uses linear probing with the backward shift algorithm for removal. Hashcodes are rehashed using Fibonacci hashing, instead of the more common power-of-two mask, to better distribute poor hashCodes (see Malte Skarupke's blog post). Linear probing continues to work even when all hashCodes collide, just more slowly.
| Modifier and Type | Class and Description |
|---|---|
| public static class | |
| public static class | |
| public static class | |
| private static class | |
| public static class |
| Modifier and Type | Field and Description |
|---|---|
| private transient IntFloatMap. | |
| private transient IntFloatMap. | |
| pack-priv boolean | |
| private transient IntFloatMap. | |
| private transient IntFloatMap. | |
| pack-priv int[] | |
| private final float | |
| protected int | mask
A bitmask used to confine hashcodes to the size of the table. |
| protected int | shift
Used by |
| public int | |
| private int | |
| private transient IntFloatMap. | |
| private transient IntFloatMap. | |
| pack-priv float[] | |
| pack-priv float |
| Access | Constructor and Description |
|---|---|
| public | |
| public | IntFloatMap(int
The backing array size is initialCapacity / loadFactor, increased to the next power of two. initialCapacity)Creates a new map with a load factor of 0.8. |
| public | IntFloatMap(int
The backing array size is initialCapacity / loadFactor, increased to the next power of two. initialCapacity, float loadFactor)Creates a new map with the specified initial capacity and load factor. |
| public |
| Modifier and Type | Method and Description |
|---|---|
| public void | clear(int maximumCapacity)
Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger. |
| public void | |
| public boolean | |
| public boolean | |
| public boolean | |
| public void | ensureCapacity(int additionalCapacity)
Increases the size of the backing array to accommodate the specified number of additional items / loadFactor. |
| public IntFloatMap. | |
| public boolean | equals(Object obj)
Overrides java. Indicates whether some other object is "equal to" this one. |
| public int | findKey(float value, int notFound)
Returns the key for the specified value, or notFound if it is not in the map. |
| public int | findKey(float value, float epsilon, int notFound)
Returns the key for the specified value, or notFound if it is not in the map. |
| public float | |
| public float | getAndIncrement(int key, float defaultValue, float increment)
Returns the key's current value and increments the stored value. |
| public int | |
| public boolean | |
| public Iterator | |
| public IntFloatMap. | |
| private int | locateKey(int key)
Returns the index of the key if already present, else -(index + 1) for the next empty index. |
| public boolean | |
| protected int | |
| public void | |
| public float | |
| public void | |
| public void | |
| public float | |
| private void | putResize(int key, float value)
Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0. |
| public float | |
| private void | |
| public void | shrink(int maximumCapacity)
Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less. |
| public String | |
| public IntFloatMap. |
| entries1 | back to summary |
|---|---|
| private transient IntFloatMap. | |
| entries2 | back to summary |
|---|---|
| private transient IntFloatMap. | |
| hasZeroValue | back to summary |
|---|---|
| pack-priv boolean hasZeroValue | |
| keys1 | back to summary |
|---|---|
| private transient IntFloatMap. | |
| keys2 | back to summary |
|---|---|
| private transient IntFloatMap. | |
| keyTable | back to summary |
|---|---|
| pack-priv int[] keyTable | |
| loadFactor | back to summary |
|---|---|
| private final float loadFactor | |
| mask | back to summary |
|---|---|
| protected int mask A bitmask used to confine hashcodes to the size of the table. Must be all 1 bits in its low positions, ie a power of two
minus 1. If | |
| shift | back to summary |
|---|---|
| protected int shift Used by
| |
| size | back to summary |
|---|---|
| public int size | |
| threshold | back to summary |
|---|---|
| private int threshold | |
| values1 | back to summary |
|---|---|
| private transient IntFloatMap. | |
| values2 | back to summary |
|---|---|
| private transient IntFloatMap. | |
| valueTable | back to summary |
|---|---|
| pack-priv float[] valueTable | |
| zeroValue | back to summary |
|---|---|
| pack-priv float zeroValue | |
| IntFloatMap | back to summary |
|---|---|
| public IntFloatMap() Creates a new map with an initial capacity of 51 and a load factor of 0.8. | |
| IntFloatMap | back to summary |
|---|---|
| public IntFloatMap(int initialCapacity) Creates a new map with a load factor of 0.8.
| |
| IntFloatMap | back to summary |
|---|---|
| public IntFloatMap(int initialCapacity, float loadFactor) Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity items before growing the backing table.
| |
| IntFloatMap | back to summary |
|---|---|
| public IntFloatMap(IntFloatMap map) Creates a new map identical to the specified map. | |
| clear | back to summary |
|---|---|
| public void clear(int maximumCapacity) Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger. | |
| clear | back to summary |
|---|---|
| public void clear() | |
| containsKey | back to summary |
|---|---|
| public boolean containsKey(int key) | |
| containsValue | back to summary |
|---|---|
| public boolean containsValue(float value) Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be an expensive operation. | |
| containsValue | back to summary |
|---|---|
| public boolean containsValue(float value, float epsilon) Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be an expensive operation. | |
| ensureCapacity | back to summary |
|---|---|
| public void ensureCapacity(int additionalCapacity) Increases the size of the backing array to accommodate the specified number of additional items / loadFactor. Useful before adding many items to avoid multiple backing array resizes. | |
| entries | back to summary |
|---|---|
| public IntFloatMap. Returns an iterator for the entries in the map. Remove is supported.
If | |
| equals | back to summary |
|---|---|
| public boolean equals(Object obj) Overrides java. Doc from java. Indicates whether some other object is "equal to" this one.
The
An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes. | |
| findKey | back to summary |
|---|---|
| public int findKey(float value, int notFound) Returns the key for the specified value, or notFound if it is not in the map. Note this traverses the entire map and compares every value, which may be an expensive operation. | |
| findKey | back to summary |
|---|---|
| public int findKey(float value, float epsilon, int notFound) Returns the key for the specified value, or notFound if it is not in the map. Note this traverses the entire map and compares every value, which may be an expensive operation. | |
| get | back to summary |
|---|---|
public float get(int key, float defaultValue)
| |
| getAndIncrement | back to summary |
|---|---|
| public float getAndIncrement(int key, float defaultValue, float increment) Returns the key's current value and increments the stored value. If the key is not in the map, defaultValue + increment is put into the map and defaultValue is returned. | |
| hashCode | back to summary |
|---|---|
| public int hashCode() Overrides java. Doc from java. Returns a hash code value for this object. This method is
supported for the benefit of hash tables such as those provided by
The general contract of
| |
| isEmpty | back to summary |
|---|---|
| public boolean isEmpty() Returns true if the map is empty. | |
| iterator | back to summary |
|---|---|
| public Iterator Implements java. Doc from java. Returns an iterator over elements of type | |
| keys | back to summary |
|---|---|
| public IntFloatMap. Returns an iterator for the keys in the map. Remove is supported.
If | |
| locateKey | back to summary |
|---|---|
| private int locateKey(int key) Returns the index of the key if already present, else -(index + 1) for the next empty index. | |
| notEmpty | back to summary |
|---|---|
| public boolean notEmpty() Returns true if the map has one or more items. | |
| place | back to summary |
|---|---|
| protected int place(int item) Returns an index >= 0 and <=
The default implementation uses Fibonacci hashing on the item's This method can be overridden to customizing hashing. This may be useful eg in the unlikely event that most hashcodes are Fibonacci numbers, if keys provide poor or incorrect hashcodes, or to simplify hashing if keys provide high quality hashcodes and don't need Fibonacci hashing. | |
| put | back to summary |
|---|---|
| public void put(int key, float value) | |
| put | back to summary |
|---|---|
| public float put(int key, float value, float defaultValue) Returns the old value associated with the specified key, or the specified default value.
| |
| putAll | back to summary |
|---|---|
| public void putAll(IntFloatMap map) | |
| putMissing | back to summary |
|---|---|
| public void putMissing(int key, float value) | |
| putMissing | back to summary |
|---|---|
| public float putMissing(int key, float value, float defaultValue) | |
| putResize | back to summary |
|---|---|
| private void putResize(int key, float value) Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0. | |
| remove | back to summary |
|---|---|
| public float remove(int key, float defaultValue) Returns the value for the removed key, or the default value if the key is not in the map.
| |
| resize | back to summary |
|---|---|
| private void resize(int newSize) | |
| shrink | back to summary |
|---|---|
| public void shrink(int maximumCapacity) Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less. If the capacity is already less, nothing is done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead. | |
| toString | back to summary |
|---|---|
| public String toString() Overrides java. Doc from java. Returns a string representation of the object.
Satisfying this method's contract implies a non- | |
| values | back to summary |
|---|---|
| public IntFloatMap. Returns an iterator for the values in the map. Remove is supported.
If | |
| Modifier and Type | Field and Description |
|---|---|
| private final IntFloatMap. |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public boolean | |
| public Iterator | |
| public IntFloatMap. | next()
Implements java. Note the same entry instance is returned each time this method is called. |
| public void | remove()
Overrides com. Overrides default java. Removes from the underlying collection the last element returned by this iterator (optional operation). |
| entry | back to summary |
|---|---|
| private final IntFloatMap. | |
| Entries | back to summary |
|---|---|
| public Entries(IntFloatMap map) | |
| hasNext | back to summary |
|---|---|
| public boolean hasNext() Implements java. Doc from java. Returns | |
| iterator | back to summary |
|---|---|
| public Iterator Implements java. Doc from java. Returns an iterator over elements of type | |
| next | back to summary |
|---|---|
| public IntFloatMap. Implements java. Note the same entry instance is returned each time this method is called. | |
| remove | back to summary |
|---|---|
| public void remove() Overrides com. Overrides default java. Doc from java. Removes from the underlying collection the last element returned
by this iterator (optional operation). This method can be called
only once per call to The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.
The behavior of an iterator is unspecified if this method is called
after a call to the | |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public String |
| Entry | back to summary |
|---|---|
| public Entry() | |
| toString | back to summary |
|---|---|
| public String toString() Overrides java. Doc from java. Returns a string representation of the object.
Satisfying this method's contract implies a non- | |
| Access | Constructor and Description |
|---|---|
| public |
| Keys | back to summary |
|---|---|
| public Keys(IntFloatMap map) | |
| next | back to summary |
|---|---|
| public int next() | |
| toArray | back to summary |
|---|---|
| public IntArray toArray() Returns a new array containing the remaining keys. | |
| toArray | back to summary |
|---|---|
| public IntArray toArray(IntArray array) Adds the remaining values to the specified array. | |
| Modifier and Type | Field and Description |
|---|---|
| pack-priv int | |
| public boolean | |
| private static final int | |
| pack-priv static final int | |
| pack-priv final IntFloatMap | |
| pack-priv int | |
| pack-priv boolean |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| pack-priv void | |
| public void | |
| public void |
| currentIndex | back to summary |
|---|---|
| pack-priv int currentIndex | |
| hasNext | back to summary |
|---|---|
| public boolean hasNext | |
| INDEX_ILLEGAL | back to summary |
|---|---|
| private static final int INDEX_ILLEGAL | |
| INDEX_ZERO | back to summary |
|---|---|
| pack-priv static final int INDEX_ZERO | |
| map | back to summary |
|---|---|
| pack-priv final IntFloatMap map | |
| nextIndex | back to summary |
|---|---|
| pack-priv int nextIndex | |
| valid | back to summary |
|---|---|
| pack-priv boolean valid | |
| MapIterator | back to summary |
|---|---|
| public MapIterator(IntFloatMap map) | |
| findNextIndex | back to summary |
|---|---|
| pack-priv void findNextIndex() | |
| remove | back to summary |
|---|---|
| public void remove() | |
| reset | back to summary |
|---|---|
| public void reset() | |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public boolean | |
| public IntFloatMap. | |
| public float | |
| public FloatArray | |
| public FloatArray |
| Values | back to summary |
|---|---|
| public Values(IntFloatMap map) | |
| hasNext | back to summary |
|---|---|
| public boolean hasNext() | |
| iterator | back to summary |
|---|---|
| public IntFloatMap. | |
| next | back to summary |
|---|---|
| public float next() | |
| toArray | back to summary |
|---|---|
| public FloatArray toArray() Returns a new array containing the remaining values. | |
| toArray | back to summary |
|---|---|
| public FloatArray toArray(FloatArray array) Adds the remaining values to the specified array. | |