Big-O Time Complexities for Elixir data structures

Map [1]

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]

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/3 and Keyword.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]

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, or Tuple.delete_at/2)

(erlang) array [6]

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'

References