-
Notifications
You must be signed in to change notification settings - Fork 4
Collections Overview
Brian Burton edited this page Mar 8, 2024
·
19 revisions
JImmutable Collections contains a variety of fully immutable collections designed to suit different needs in an application. This page describes the various collections (as of version 1.9) and their general performance characteristics. For each collection the summary lists the factory method used to create an instance, the general algorithmic complexity of the collection, and a description of the collection's uses and characteristics.
The complexity is expressed in big-oh notation which means "on the order of" or "within some constant multiple of" the value in parentheses. logX(n) means log to the base X of the number of elements in the collection. To give an idea of scale log32(100000) is 3.3 while log2(100000) is 16.6. "Within some constant factor" means that there will be fixed costs associated with the implementation so one algorithm with a given big-oh complexity might be 2-3 times faster than another with the same complexity.
Generally speaking java.util.ArrayList will be faster than IList unless insertion or deletion in mid-list is required since it simply updates a mutable array but for most algorithms the difference will be negligible to overall run time. IMaps are generally comparable in performance (i.e. within acceptable limits for most algorithms) to java.util.Maps. See the [Comparative Performance] page for an idea of how the immutable maps and arrays compare to java.util.Maps.
| Factory | Complexity | Description |
|---|---|---|
| IArrays.of() IArrays.allOf() | O(log32(n)) | A sparse array allowing any integer (positive or negative) as index. Indexes do not need to be consecutive and the array allocates memory only for indexes actually inserted into the array. Implemented internally as an integer trie with 32-way branching. Iterators and Streams visit elements in order by index with negative indexes visited before positive indexes. No direct java.util analog but similar to a TreeMap but with better performance. |
| IMaps.hashed() | O(log32(n)) | A hash map using hashCode() and equals() methods of keys. Keys and values are stored in hash mapped array tries using linked lists or binary trees for collision handling (two keys having same hash code). Performance scales roughly linearly with size of the collection since depth of the trie never exceeds 7 levels. Intended as a replacement for java.util.HashMap. Iterators and Streams visit elements in an unspecified order. |
| IMaps.sorted() | O(log2(n)) | A tree map using a Comparator object to sort and compare keys. Keys and values are stored in binary trees. Intended as a replacement for java.util.TreeMap. Iterators and Streams visit elements in sort order of keys as specified by the Comparator. |
| IMaps.ordered() | O(2 * log32(n)) | A hash map using hashCode() and equals() methods of keys. Keys and values are stored in hash mapped array tries using linked lists or binary trees for collision handling (two keys having same hash code). Keys in the map are tracked in a linked list to govern iterator order. Performance is nearly constant since depth of the trie never exceeds 7 levels. Perhaps as much as twice the overhead of a hashed map since it maintains two data structures internally. Intended as a replacement for java.util.LinkedHashMap. Iterators and Streams visit elements in the order they were originally inserted into the map. |
| ILists.of() ILists.allOf() | O(log2(n)) | A "list" implemented internally as a balanced binary tree with leaf nodes containing up to 128 values each. Allows elements to be inserted or removed anywhere in the list (prior to 3.0.0 only at either end of the list). Allows elements to be replaced anywhere within the list. Intended as a replacement for java.util.List. Iterators and Streams visit elements in order by index. Supports efficient append, prefix, and suffix operations. |
| IDeques.of() IDeques.allOf() | O(log32(n)) | A deque implemented internally as a 32-way tree. Similar to list but allows elements to be inserted only at the front or back of the list. Faster to build and use than IList when all you need is an ordered collection that supports iteration and getting values from the collection by index. Intended as a replacement for most uses of java.util.List in algorithms that do not require insertion or removal from the middle of the list. Otherwise use IList. Iterators and Streams visit elements in order by index. |
| ISets.hashed() | O(log32(n)) | A set implemented internally using a hash map. Keys are stored in hash mapped array tries using hashCode() and equals() methods to compare keys. Intended as a replacement for java.util.HashSet. Iterators and Streams visit elements in an unspecified order. |
| ISets.sorted() | O(log2(n)) | A set implemented internally using a balanced binary tree. Keys are compared using a Comparator. Intended as a replacement for java.util.TreeSet. Iterators and Streams visit elements in sort order of keys as specified by the Comparator. |
| ISets.ordered() | O(2 * log32(n)) | A set implemented internally using a linked list for sort order and a hash mapped trie for searching. Performance is nearly constant since depth of the trie never exceeds 7 levels. Perhaps as much as twice the overhead of a hashed set since it maintains two data structures internally. Intended as a replacement for java.util.LinkedHashSet. Iterators and Streams visit elements in the order they were originally inserted into the map. |
| IListMaps.hashed() | O(log32(n)) | A hash map mapping keys to ILists. Performance similar to a hashed map. Iterators and Streams visit elements in an unspecified order. |
| IListMaps.sorted() | O(log2(n)) | A sorted map mapping keys to ILists. Performance similar to a sorted map. Iterators and Streams visit elements in sort order of keys as specified by the Comparator. |
| IListMaps.ordered() | O(2 * log32(n)) | A sorted map mapping keys to ILists. Performance similar to an ordered map. Iterators and Streams visit elements in the order they were originally inserted into the map. |
| ISetMaps.hashed() | O(log32(n)) | A hash map mapping keys to ISets. Performance similar to a hashed map. Iterators and Streams visit elements in an unspecified order. Sets are all equivalent to one created by ISets.hashed(). |
| ISetMaps.sorted() | O(log2(n)) | A sorted map mapping keys to ISets. Performance similar to a sorted map. Iterators and Streams visit elements in sort order of keys as specified by the Comparator. Sets are all equivalent to one created by ISets.hashed(). |
| ISetMaps.ordered() | O(2 * log32(n)) | An ordered map mapping keys to ISets. Performance similar to an ordered map. Iterators and Streams visit elements in the order they were originally inserted into the map. Sets are all equivalent to one created by ISets.hashed(). |
| ISetMaps.templated() | variable | Allows an ISetMap to be constructed by mixing and matching map and set implementations. Caller provides template map and set implementation. |
| ISetMaps.factory() | variable | Allows an ISetMap to be constructed by mixing and matching map and set implementations. Factory allows map and set implementation to be defined in a builder-like fashion. |
| IMultisets.hashed() | O(log32(n)) | A multiset implemented internally using a hashed map. Keys are stored in hash mapped array tries using hashCode() and equals() methods to compare keys. Iterators and Streams visit elements in an unspecified order. |
| IMultisets.sorted() | O(log2(n)) | A multiset implemented internally using a balanced binary tree. Keys are compared using a Comparator. Iterators and Streams visit elements in sort order of keys as specified by the Comparator. |
| IMultisets.ordered() | O(2 * log32(n)) | A multiset implemented internally using a linked list for sort order and a hash mapped trie for searching. Performance is nearly constant since depth of the trie never exceeds 7 levels. Somewhat more overhead then a hashed multiset since it maintains two data structures internally. Iterators and Streams visit elements in the order they were originally inserted into the map. Parallel Streams are not supported. |
In addition to the static factory methods several of the collections also have builder implementations to simplify creation of instances. Builders can be created using a static factory methods.
| Collection | Builder Method | Notes |
|---|---|---|
| IArray | IArrays.builder() | Auto increments array indicies starting at 0. |
| IDeque | IDeques.builder() | |
| IList | ILists.builder() | |
| IMap | IMaps.hashedBuilder() | |
| IMap | IMaps.sortedBuilder() | |
| IMap | IMaps.orderedBuilder() | More for convenience than performance. |
| ISet | ISets.hashedBuilder() | |
| ISet | ISets.sortedBuilder() | |
| ISet | ISets.orderedBuilder() | More for convenience than performance. |
In addition to the static factory methods and builders several of the collections also have Collector implementations. These can be used to construct collections using java Streams. Static methods in the ICollectors class can be used to produce empty Collectors. The collection classes also offer instance methods to create pre-filled Collectors that can be used to effectively append values to an existing collection.
| Collection | Static Method | Instance Method | Notes |
|---|---|---|---|
| IArray | ICollectors.toArray() | ||
| IDeque | ICollectors.toDeque() | dequeCollector() | |
| IList | ICollectors.toList() | listCollector() | |
| IListMap | ICollectors.toListMap() | listMapCollector() | Hashed. |
| IListMap | ICollectors.toOrderedListMap() | listMapCollector() | Sorted by insertion order. |
| IListMap | ICollectors.toSortedListMap() | listMapCollector() | Sorted by key. |
| IListMap | ICollectors.groupingBy() | listMapCollector() | Groups stream values into ILists using a key extraction function. |
| IMap | ICollectors.toMap() | mapCollector() | Hashed. |
| IMap | ICollectors.toOrderedMap() | mapCollector() | Sorted by insertion order. |
| IMap | ICollectors.toSortedMap() | mapCollector() | Sorted by key. |
| IMultiset | ICollectors.toMultiset() | multisetCollector() | Hashed. |
| IMultiset | ICollectors.toOrderedMultiset() | multisetCollector() | Sorted by insertion order. |
| IMultiset | ICollectors.toSortedMultiset() | multisetCollector() | Sorted by key. |
| ISet | ICollectors.toSet() | setCollector() | Hashed. |
| ISet | ICollectors.toOrderedSet() | setCollector() | Sorted by insertion order. |
| ISet | ICollectors.toSortedSet() | setCollector() | Sorted by key. |
| ISetMap | ICollectors.toSetMap() | setMapCollector() | Hashed. |
| ISetMap | ICollectors.toOrderedSetMap() | setMapCollector() | Sorted by insertion order. |
| ISetMap | ICollectors.toSortedSetMap() | setMapCollector() | Sorted by key. |