Map [1]
| Operation | Time Complexity |
|---|---|
| Access | O(log n) |
| Search | O(log n) |
| Insertion | O(n) for < 32 elements, O(log n) for >= 32 elements [2] |
| Deletion | O(n) for < 32 elements, O(log n) for >= 32 elements |
Caveats:
- With fewer than 32 elements, a Map is a list of tuples sorted by keys
- With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)
- Maps are unordered, allow any key type, but disallow duplicate keys
List [3]
| Operation | Time Complexity |
|---|---|
| Access | O(n) |
| Search | O(n) |
| Insertion | O(1) for prepending, otherwise O(n) |
| Deletion | O(1) if first element, otherwise O(n) |
Caveats
- Lists are not arrays as in other languages, but single-linked lists
Keyword [4]
| Operation | Time Complexity |
|---|---|
| Access | O(n) |
| Search | O(n) |
| Insertion | O(n) |
| Deletion | O(n) |
Tuple [5]
| Operation | Time Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insertion | O(n) |
| Deletion | O(n) |
Caveats
- Tuples are better for reading, whereas Lists are better for traversals
- Avoid using tuples as a collection
- (i.e. avoid
Tuple.append/2,Tuple.insert_at/2, orTuple.delete_at/2)
- (i.e. avoid
(erlang) array [6]
| Operation | Time Complexity |
|---|---|
| Access | O(log n) [7] |
| Search | O(log n) |
| Insertion | O(log n) |
| Deletion | O(log n) |
Caveats
- An array is a trie of small tuples, with a smaller memory overhead to Lists
- Deletion is actually a replace with the default value and creates sparse arrays
- For real deletion, use sparse_to_list/1, which has O(n) complexity
MapSet [8]
Same complexities as 'Map'