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 32 and fewer elements, a Map is a list of tuples sorted by keys
- With more than 32 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 (List) [4]
A Keyword (list) has the same time complexities as List.
Every entry in a Keyword (list) is a tuple with the first element being the key and the second element the value.
keyword = [{:a, 1}, {:b, 2}]Caveats
- A keyword list does not guarantee order.
- A keyword list may have duplicate keys, but duplicates are often ignored by functions like
Keyword.get/3(returns the first match) and are even removed by e.g.Keyword.put/3andKeyword.delete/2.
iex> Keyword.get([{:a, 1}, {:a, 2}], :a)
1
iex> Keyword.put([{:a, 1}, {:a, 2}], :a, 3)
[a: 3]
iex> Keyword.delete([{:a, 1}, {:a, 2}], :a)
[]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
- For real deletion, use sparse_to_list/1, which has
MapSet [8]
Same complexities as 'Map'
I believe a map is O(n) for <= 32 elements. This states that it is O(n) for < 32 elements. Please correct me if I'm wrong, but I doubled checked
by creating a map with 32 elements and it retains sorting order.
Thank you a ton for providing this resource!