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 LongMap. | |
| private transient LongMap. | |
| pack-priv boolean | |
| private transient LongMap. | |
| private transient LongMap. | |
| pack-priv long[] | |
| 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 LongMap. | |
| private transient LongMap. | |
| pack-priv V[] | |
| pack-priv V |
| Access | Constructor and Description |
|---|---|
| public | |
| public | LongMap(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 | LongMap(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 | containsValue(Object value, boolean
If true, uses == to compare the specified value with values in the map. If false, uses
identity)equals(Object).Returns true if the specified value is in the map. |
| public void | ensureCapacity(int additionalCapacity)
Increases the size of the backing array to accommodate the specified number of additional items / loadFactor. |
| public LongMap. | |
| public boolean | equals(Object obj)
Overrides java. Indicates whether some other object is "equal to" this one. |
| public boolean | |
| public long | findKey(Object value, boolean
If true, uses == to compare the specified value with values in the map. If false, uses
identity, long notFound)equals(Object).Returns the key for the specified value, or notFound if it is not in the map. |
| public V | |
| public V | |
| public int | |
| public boolean | |
| public Iterator | |
| public LongMap. | |
| private int | locateKey(long key)
Returns the index of the key if already present, else -(index + 1) for the next empty index. |
| public boolean | |
| protected int | |
| public V | |
| public void | |
| public V | |
| private void | putResize(long key, V value)
Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0. |
| public V | |
| 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 LongMap. |
| entries1 | back to summary |
|---|---|
| private transient LongMap. | |
| entries2 | back to summary |
|---|---|
| private transient LongMap. | |
| hasZeroValue | back to summary |
|---|---|
| pack-priv boolean hasZeroValue | |
| keys1 | back to summary |
|---|---|
| private transient LongMap. | |
| keys2 | back to summary |
|---|---|
| private transient LongMap. | |
| keyTable | back to summary |
|---|---|
| pack-priv long[] 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 LongMap. | |
| values2 | back to summary |
|---|---|
| private transient LongMap. | |
| valueTable | back to summary |
|---|---|
| pack-priv V[] valueTable | |
| zeroValue | back to summary |
|---|---|
| pack-priv V zeroValue | |
| LongMap | back to summary |
|---|---|
| public LongMap() Creates a new map with an initial capacity of 51 and a load factor of 0.8. | |
| LongMap | back to summary |
|---|---|
| public LongMap(int initialCapacity) Creates a new map with a load factor of 0.8.
| |
| LongMap | back to summary |
|---|---|
| public LongMap(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.
| |
| LongMap | back to summary |
|---|---|
| public LongMap(LongMap<? extends V> 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(long key) | |
| containsValue | back to summary |
|---|---|
| public boolean containsValue(Object value, boolean identity) 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 LongMap. 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. | |
| equalsIdentity | back to summary |
|---|---|
| public boolean equalsIdentity(Object obj) Uses == for comparison of each value. | |
| findKey | back to summary |
|---|---|
| public long findKey(Object value, boolean identity, long 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 V get(long key)
| |
| get | back to summary |
|---|---|
| public V get(long key, V defaultValue) | |
| 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 LongMap. Returns an iterator for the keys in the map. Remove is supported.
If | |
| locateKey | back to summary |
|---|---|
| private int locateKey(long 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(long 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 V put(long key, V value)
| |
| putAll | back to summary |
|---|---|
| public void putAll(LongMap<? extends V> map) | |
| putMissing | back to summary |
|---|---|
public V putMissing(long key, V value)
| |
| putResize | back to summary |
|---|---|
| private void putResize(long key, V value) Skips checks for existing keys, doesn't increment size, doesn't need to handle key 0. | |
| remove | back to summary |
|---|---|
| public V remove(long key) Returns the value for the removed key, or null 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 LongMap. Returns an iterator for the values in the map. Remove is supported.
If | |
| Modifier and Type | Method and Description |
|---|---|
| public boolean | |
| public Iterator | |
| public LongMap. | next()
Implements java. Note the same entry instance is returned each time this method is called. |
| entry | back to summary |
|---|---|
| private final LongMap. | |
| Entries | back to summary |
|---|---|
| public Entries(LongMap<V> 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 LongMap. Implements java. Note the same entry instance is returned each time this method is called. | |
| 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- | |
| Modifier and Type | Method and Description |
|---|---|
| public long | |
| public LongArray | |
| public LongArray |
| Keys | back to summary |
|---|---|
| public Keys(LongMap<V> map) | |
| next | back to summary |
|---|---|
| public long next() | |
| toArray | back to summary |
|---|---|
| public LongArray toArray() Returns a new array containing the remaining keys. | |
| toArray | back to summary |
|---|---|
| public LongArray toArray(LongArray 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 LongMap | |
| 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 LongMap<V> map | |
| nextIndex | back to summary |
|---|---|
| pack-priv int nextIndex | |
| valid | back to summary |
|---|---|
| pack-priv boolean valid | |
| MapIterator | back to summary |
|---|---|
| public MapIterator(LongMap<V> map) | |
| findNextIndex | back to summary |
|---|---|
| pack-priv void findNextIndex() | |
| remove | back to summary |
|---|---|
| public void remove() | |
| reset | back to summary |
|---|---|
| public void reset() | |
| Modifier and Type | Method and Description |
|---|---|
| public boolean | |
| public Iterator | |
| public V | |
| public Array |
| Values | back to summary |
|---|---|
| public Values(LongMap<V> 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 V next() Implements java. Doc from java. Returns the next element in the iteration.
| |
| toArray | back to summary |
|---|---|
| public Array Returns a new array containing the remaining values. | |