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

public Class IdentityMap<K, V>

extends ObjectMap<K, V>
Class Inheritance
An unordered map that uses identity comparison for the object keys. Null keys are not allowed. 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. Linear probing continues to work even when all hashCodes collide, just more slowly.

Authors
Tommy Ettinger, Nathan Sweet

Field Summary

Inherited from com.badlogic.gdx.utils.ObjectMap:
dummyentries1entries2keys1keys2keyTableloadFactormaskshiftsizethresholdvalues1values2valueTable

Constructor Summary

AccessConstructor and Description
public
IdentityMap()

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

public
IdentityMap(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
IdentityMap(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
IdentityMap(IdentityMap<K, V> map)

Creates a new map identical to the specified map.

Method Summary

Modifier and TypeMethod and Description
public int
hashCode()

Overrides com.badlogic.gdx.utils.ObjectMap.hashCode.

Returns a hash code value for this object.

pack-priv int
locateKey(K key)

Overrides com.badlogic.gdx.utils.ObjectMap.locateKey.

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

protected int
place(K item)

Overrides com.badlogic.gdx.utils.ObjectMap.place.

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

Inherited from com.badlogic.gdx.utils.ObjectMap:
clearclearcontainsKeycontainsValueensureCapacityentriesequalsequalsIdentityfindKeygetgetisEmptyiteratorkeysnotEmptyputputAllputMissingremoveresizeshrinktoStringtoStringtoStringvalues

Constructor Detail

IdentityMapback to summary
public IdentityMap()

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

IdentityMapback to summary
public IdentityMap(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.

IdentityMapback to summary
public IdentityMap(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.

IdentityMapback to summary
public IdentityMap(IdentityMap<K, V> map)

Creates a new map identical to the specified map.

Method Detail

hashCodeback to summary
public int hashCode()

Overrides com.badlogic.gdx.utils.ObjectMap.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.
locateKeyback to summary
pack-priv int locateKey(K key)

Overrides com.badlogic.gdx.utils.ObjectMap.locateKey.

Doc from com.badlogic.gdx.utils.ObjectMap.locateKey.

Returns the index of the key if already present, else -(index + 1) for the next empty index. This can be overridden in this pacakge to compare for equality differently than Object#equals(Object).

placeback to summary
protected int place(K item)

Overrides com.badlogic.gdx.utils.ObjectMap.place.

Doc from com.badlogic.gdx.utils.ObjectMap.place.

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: return item.hashCode() & mask;