APIdia Launch Partner
Top Description Inners Fields Constructors Methods
com.badlogic.gdx.utils

public Class LongMap<V>

extends Object
implements Iterable<LongMap.Entry<V>>
Class Inheritance
All Implemented Interfaces
java.lang.Iterable
Imports
java.util.Arrays, .Iterator, .NoSuchElementException

An unordered map where the keys are unboxed longs and values are objects. No allocation is done except when growing the table size.

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.

Authors
Nathan Sweet, Tommy Ettinger

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static class
public static class
public static class
private static class
public static class

Field Summary

Modifier and TypeField and Description
private transient LongMap.Entries<V>
private transient LongMap.Entries<V>
pack-priv boolean
private transient LongMap.Keys
private transient LongMap.Keys
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 place(long) to bit shift the upper bits of a long into a usable range (>= 0 and <= mask).

public int
private int
private transient LongMap.Values<V>
private transient LongMap.Values<V>
pack-priv V[]
pack-priv V

Constructor Summary

AccessConstructor and Description
public
LongMap()

Creates a new map with an initial capacity of 51 and a load factor of 0.8.

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
LongMap(LongMap<? extends V> map)

Creates a new map identical to the specified map.

Method Summary

Modifier and TypeMethod 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
containsKey(long key)

public boolean
containsValue(Object value, boolean
If true, uses == to compare the specified value with values in the map. If false, uses equals(Object).
identity
)

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.Entries<V>
entries()

Returns an iterator for the entries in the map.

public boolean
equals(Object obj)

Overrides java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

public boolean
equalsIdentity(Object obj)

Uses == for comparison of each value.

public long
findKey(Object value, boolean
If true, uses == to compare the specified value with values in the map. If false, uses equals(Object).
identity
,
long notFound)

Returns the key for the specified value, or notFound if it is not in the map.

public V
get(long key)

public V
get(long key, V defaultValue)

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this object.

public boolean
isEmpty()

Returns true if the map is empty.

public Iterator<LongMap.Entry<V>>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public LongMap.Keys
keys()

Returns an iterator for the keys in the map.

private int
locateKey(long key)

Returns the index of the key if already present, else -(index + 1) for the next empty index.

public boolean
notEmpty()

Returns true if the map has one or more items.

protected int
place(long item)

Returns an index >= 0 and <= mask for the specified item.

public V
put(long key, V value)

public void
putAll(LongMap<? extends V> map)

public V
putMissing(long key, V value)

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
remove(long key)

Returns the value for the removed key, or null if the key is not in the map.

private void
resize(int newSize)

public void
shrink(int maximumCapacity)

Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

public LongMap.Values<V>
values()

Returns an iterator for the values in the map.

Inherited from java.lang.Object:
clonefinalizegetClassnotifynotifyAllwaitwaitwait

Field Detail

entries1back to summary
private transient LongMap.Entries<V> entries1
entries2back to summary
private transient LongMap.Entries<V> entries2
hasZeroValueback to summary
pack-priv boolean hasZeroValue
keys1back to summary
private transient LongMap.Keys keys1
keys2back to summary
private transient LongMap.Keys keys2
keyTableback to summary
pack-priv long[] keyTable
loadFactorback to summary
private final float loadFactor
maskback 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 place(long) is overridden, this can be used instead of shift to isolate usable bits of a hash.

shiftback to summary
protected int shift

Used by place(long) to bit shift the upper bits of a long into a usable range (>= 0 and <= mask). The shift can be negative, which is convenient to match the number of bits in mask: if mask is a 7-bit number, a shift of -7 shifts the upper 7 bits into the lowest 7 positions. This class sets the shift > 32 and < 64, which if used with an int will still move the upper bits of an int to the lower bits due to Java's implicit modulus on shifts.

mask can also be used to mask the low bits of a number, which may be faster for some hashcodes, if place(long) is overridden.

sizeback to summary
public int size
thresholdback to summary
private int threshold
values1back to summary
private transient LongMap.Values<V> values1
values2back to summary
private transient LongMap.Values<V> values2
valueTableback to summary
pack-priv V[] valueTable
zeroValueback to summary
pack-priv V zeroValue

Constructor Detail

LongMapback to summary
public LongMap()

Creates a new map with an initial capacity of 51 and a load factor of 0.8.

LongMapback to summary
public LongMap(int initialCapacity)

Creates a new map with a load factor of 0.8.

Parameters
initialCapacity:int

The backing array size is initialCapacity / loadFactor, increased to the next power of two.

LongMapback 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.

Parameters
initialCapacity:int

The backing array size is initialCapacity / loadFactor, increased to the next power of two.

LongMapback to summary
public LongMap(LongMap<? extends V> map)

Creates a new map identical to the specified map.

Method Detail

clearback 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.

clearback to summary
public void clear()
containsKeyback to summary
public boolean containsKey(long key)
containsValueback 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.

Parameters
identity:boolean

If true, uses == to compare the specified value with values in the map. If false, uses equals(Object).

ensureCapacityback 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.

entriesback to summary
public LongMap.Entries<V> entries()

Returns an iterator for the entries in the map. Remove is supported.

If Collections#allocateIterators is false, the same iterator instance is returned each time this method is called. Use the Entries constructor for nested or multithreaded iteration.

equalsback to summary
public boolean equals(Object obj)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

  • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
  • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
  • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
  • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
  • For any non-null reference value x, x.equals(null) should return false.

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.

equalsIdentityback to summary
public boolean equalsIdentity(Object obj)

Uses == for comparison of each value.

findKeyback 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.

Parameters
identity:boolean

If true, uses == to compare the specified value with values in the map. If false, uses equals(Object).

getback to summary
public V get(long key)
Annotations
@Null
getback to summary
public V get(long key, V defaultValue)
hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
isEmptyback to summary
public boolean isEmpty()

Returns true if the map is empty.

iteratorback to summary
public Iterator<LongMap.Entry<V>> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

keysback to summary
public LongMap.Keys keys()

Returns an iterator for the keys in the map. Remove is supported.

If Collections#allocateIterators is false, the same iterator instance is returned each time this method is called. Use the Entries constructor for nested or multithreaded iteration.

locateKeyback to summary
private int locateKey(long key)

Returns the index of the key if already present, else -(index + 1) for the next empty index.

notEmptyback to summary
public boolean notEmpty()

Returns true if the map has one or more items.

placeback to summary
protected int place(long item)

Returns an index >= 0 and <= mask for the specified item.

The default implementation uses Fibonacci hashing on the item's Object#hashCode(): the hashcode is multiplied by a long constant (2 to the 64th, divided by the golden ratio) then the uppermost bits are shifted into the lowest positions to obtain an index in the desired range. Multiplication by a long may be slower than int (eg on GWT) but greatly improves rehashing, allowing even very poor hashcodes, such as those that only differ in their upper bits, to be used without high collision rates. Fibonacci hashing has increased collision rates when all or most hashcodes are multiples of larger Fibonacci numbers (see Malte Skarupke's blog post).

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.

putback to summary
public V put(long key, V value)
Annotations
@Null
putAllback to summary
public void putAll(LongMap<? extends V> map)
putMissingback to summary
public V putMissing(long key, V value)
Annotations
@Null
putResizeback 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.

removeback to summary
public V remove(long key)

Returns the value for the removed key, or null if the key is not in the map.

Annotations
@Null
resizeback to summary
private void resize(int newSize)
shrinkback 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.

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

valuesback to summary
public LongMap.Values<V> values()

Returns an iterator for the values in the map. Remove is supported.

If Collections#allocateIterators is false, the same iterator instance is returned each time this method is called. Use the Entries constructor for nested or multithreaded iteration.

com.badlogic.gdx.utils back to summary

public Class LongMap.Entries<V>

extends LongMap.MapIterator<V>
implements Iterable<LongMap.Entry<V>>, Iterator<LongMap.Entry<V>>
Class Inheritance
All Implemented Interfaces
java.util.Iterator, java.lang.Iterable

Field Summary

Modifier and TypeField and Description
private final LongMap.Entry<V>
Inherited from com.badlogic.gdx.utils.LongMap.MapIterator:
currentIndexhasNextINDEX_ZEROmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public
Entries(LongMap<V> map)

Method Summary

Modifier and TypeMethod and Description
public boolean
hasNext()

Implements java.util.Iterator.hasNext.

Returns true if the iteration has more elements.

public Iterator<LongMap.Entry<V>>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public LongMap.Entry<V>
next()

Implements java.util.Iterator.next.

Note the same entry instance is returned each time this method is called.

Inherited from com.badlogic.gdx.utils.LongMap.MapIterator:
findNextIndexremovereset

Field Detail

entryback to summary
private final LongMap.Entry<V> entry

Constructor Detail

Entriesback to summary
public Entries(LongMap<V> map)

Method Detail

hasNextback to summary
public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

iteratorback to summary
public Iterator<LongMap.Entry<V>> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

nextback to summary
public LongMap.Entry<V> next()

Implements java.util.Iterator.next.

Note the same entry instance is returned each time this method is called.

com.badlogic.gdx.utils back to summary

public Class LongMap.Entry<V>

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
public long
public V

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

keyback to summary
public long key
valueback to summary
public V value
Annotations
@Null

Constructor Detail

Entryback to summary
public Entry()

Method Detail

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

com.badlogic.gdx.utils back to summary

public Class LongMap.Keys

extends MapIterator
Class Inheritance

Field Summary

Inherited from com.badlogic.gdx.utils.LongMap.MapIterator:
currentIndexhasNextINDEX_ZEROmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public
Keys(LongMap<V> map)

Method Summary

Modifier and TypeMethod and Description
public long
next()

public LongArray
toArray()

Returns a new array containing the remaining keys.

public LongArray
toArray(LongArray array)

Adds the remaining values to the specified array.

Inherited from com.badlogic.gdx.utils.LongMap.MapIterator:
findNextIndexremovereset

Constructor Detail

Keysback to summary
public Keys(LongMap<V> map)

Method Detail

nextback to summary
public long next()
toArrayback to summary
public LongArray toArray()

Returns a new array containing the remaining keys.

toArrayback to summary
public LongArray toArray(LongArray array)

Adds the remaining values to the specified array.

com.badlogic.gdx.utils back to summary

private Class LongMap.MapIterator<V>

extends Object
Class Inheritance
Known Direct Subclasses
com.badlogic.gdx.utils.LongMap.Entries, com.badlogic.gdx.utils.LongMap.Values, com.badlogic.gdx.utils.LongMap.Keys

Field Summary

Modifier and TypeField and Description
pack-priv int
public boolean
private static final int
pack-priv static final int
pack-priv final LongMap<V>
pack-priv int
pack-priv boolean

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
pack-priv void
public void
public void
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

currentIndexback to summary
pack-priv int currentIndex
hasNextback to summary
public boolean hasNext
INDEX_ILLEGALback to summary
private static final int INDEX_ILLEGAL
INDEX_ZEROback to summary
pack-priv static final int INDEX_ZERO
mapback to summary
pack-priv final LongMap<V> map
nextIndexback to summary
pack-priv int nextIndex
validback to summary
pack-priv boolean valid

Constructor Detail

MapIteratorback to summary
public MapIterator(LongMap<V> map)

Method Detail

findNextIndexback to summary
pack-priv void findNextIndex()
removeback to summary
public void remove()
resetback to summary
public void reset()
com.badlogic.gdx.utils back to summary

public Class LongMap.Values<V>

extends LongMap.MapIterator<V>
implements Iterable<V>, Iterator<V>
Class Inheritance
All Implemented Interfaces
java.util.Iterator, java.lang.Iterable

Field Summary

Inherited from com.badlogic.gdx.utils.LongMap.MapIterator:
currentIndexhasNextINDEX_ZEROmapnextIndexvalid

Constructor Summary

AccessConstructor and Description
public
Values(LongMap<V> map)

Method Summary

Modifier and TypeMethod and Description
public boolean
hasNext()

Implements java.util.Iterator.hasNext.

Returns true if the iteration has more elements.

public Iterator<V>
iterator()

Implements java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

public V
next()

Implements java.util.Iterator.next.

Returns the next element in the iteration.

public Array<V>
toArray()

Returns a new array containing the remaining values.

Inherited from com.badlogic.gdx.utils.LongMap.MapIterator:
findNextIndexremovereset

Constructor Detail

Valuesback to summary
public Values(LongMap<V> map)

Method Detail

hasNextback to summary
public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

iteratorback to summary
public Iterator<V> iterator()

Implements java.lang.Iterable.iterator.

Doc from java.lang.Iterable.iterator.

Returns an iterator over elements of type T.

nextback to summary
public V next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Annotations
@Null
toArrayback to summary
public Array<V> toArray()

Returns a new array containing the remaining values.