Lists

The iterator returned by is always the same instance, allowing the Array to be used with the enhanced for-each (for( : )) syntax without creating garbage. Note however that this differs from most iterable collections! It cannot be used in nested loops, else it will cause hard to find bugs.

Primitive lists

These are identical to Array except they use primitive types instead of objects. This avoids boxing and unboxing.

This is identical to Array except it guarantees that array entries provided by begin(), between indexes 0 and the size at the time begin was called, will not be modified until end() is called. This can be used to avoid concurrent modification. It requires iteration to be done a specific way:

If any code inside begin() and end() would modify the SnapshotArray, the internal backing array is copied so that the array being iterated over is not modified. The extra backing array created when this occurs is kept so it can be reused if a concurrent modification occurs again in the future.

DelayedRemovalArray

This is identical to Array except any removals done after begin() is called are queued and only occur once end() is called. This can be used to avoid concurrent modification. Note that code using this type of list must be aware that removed items are not actually removed immediately. Because of this, often !SnapshotArray is easier to use.

(code)

A sorted double linked list which uses ints for indexing.

Maps

(code)

An unordered map. This implementation is a cuckoo hash map using three hashes, random walking, and a small stash for problematic keys. Null keys are not allowed, null values are. No allocation is done except when growing the table size.

Keys may only be in one of three locations in the backing array, allowing this map to perform very fast get, containsKey, and remove. Put can be a bit slower, depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the map will have to rehash to the next higher POT backing array size.

These maps are identical to ObjectMap except they use primitive types for the keys, except ObjectIntMapand ObjectFloatMap which use primitive values. This avoids boxing and unboxing.

Specialized maps

This map is identical to ObjectMap except keys are also stored in an Array. This adds overhead to put and remove but provides ordered iteration. The key Array can be sorted directly to change the iteration order.

(code)

This map uses arrays for both the keys and values. This means get does a comparison for each key in the map, but provides fast, ordered iteration and entries can be looked up by index.

Sets

Exactly like ObjectMap, except only keys are stored. No values are stored for each key.

Primitive sets

These maps are identical to ObjectSet except they use primitive types for the keys. This avoids boxing and unboxing.

Other collections

(code)

A . Can be a min-heap or a max-heap.

Benchmarks

The benchmark below shows the difference between array and hashtable lookup (.contains() or .get()) using libGDX collection methods. If you have less than 1024 elements in a list, you shouldn’t bother whether you’re using arrays or hashtables (Maps or Sets). Mind the fact that hashtables have significantly slower iteration than arrays and cannot be ordered.

  1.                            2                         0ms                         0ms
  2.                            4                         0ms                         0ms
  3.                            8                         0ms                         1ms
  4.                           16                         0ms                         1ms
  5.                           32                         0ms                         0ms
  6.                           64                         0ms                         0ms
  8.                          256                         1ms                         0ms
  9.                          512                         1ms                         0ms
  10.                         1024                         2ms                         0ms
  11.                         2048                         4ms                         0ms
  12.                         4096                        11ms                         0ms
  13.                         8192                        22ms                         0ms
  14.                        16384                        80ms                         0ms
  15.                        32768                       112ms                         0ms