Is Map a Hash table?

Questions / Help
1

this is a question of the computer science. Is Elixir map a hash table? Or is it a keyword list having unique keys? I ask this because of the shape of Enum functions looking the same… for example fn {key, value} -> ... end looks same for maps and keyword lists

How is map stored in memory? Is getting a key O(1) operation in Elixir map? Is getting a key O(n) operation in Elixir list?

1 Like
2

Maps are stored either as hash map or as tuple (when small enough). Keyword lists are normal linked lists with {atom, term} for all items.

Enum functions work with any value implementing Enumerable.t. Datatype specific functions are in Map, Keyword or List.

4 Likes
3

Thank you!

4

If you want to take a deep-dive in how maps are implemented internally, I recommend the blog article Breaking Erlang Maps by @jlouis. Small maps are stored as a ‘flatmap’: a sorted array of keys + their values. Big maps are stored as a ‘hash-array mapped trie’, which allows them to be persistent data structures (in a snippet like x = %{a: 1, b: 2, c: 3}; y = Map.put(x, :b, 4) we do not have to copy the fields of x to construct y but can re-use all unchanged fields of x directly).

9 Likes