Lists

Array (code)

A resizable, ordered or unordered array of objects. It often replaces ArrayList. It provides direct access to the backing array, which can be of a specific type rather than just Object[]. It can also be unordered, acting like a bag/multiset. In this case, a memory copy is avoided when removing elements (the last element is moved to the removed element's position).

The iterator returned by iterator() 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

• IntArray (code)
• FloatArray (code)
• BooleanArray (code)
• CharArray (code)
• LongArray (code)

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

Specialized lists

SnapshotArray (code)

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:

SnapshotArray array = new SnapshotArray();
// ...
Object[] items = array.begin();
for (int i = 0, n = array.size; i < n; i++) {
	Object item = items[i];
	// ...
}
array.end();

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 (code)

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.

PooledLinkedList (code)

A simple linked list that pools its nodes.

SortedIntList (code)

A sorted double linked list which uses ints for indexing.

Maps

ObjectMap (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.

Primitive maps

• IntMap (code)
• LongMap (code)
• ObjectIntMap (code)

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

Specialized maps

OrderedMap (code)

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.

IdentityMap (code)

This map is identical to ObjectMap except keys are compared using identity comparison (== instead of .equals()).

ArrayMap (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

ObjectSet (code)

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

Primitive sets

• IntSet (code)

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

Other collections

BinaryHeap (code)

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