F4 · Foundations · module 4
Maps, sets & hashing
Sorting (F4.03) bought fast search by paying for order. A hash map makes a different trade: it gives up order entirely and, in exchange, looks a value up by key in effectively constant time. A set is the same machinery answering one question — is this element present? — and hashing is what makes both O(1) on average.
The worked example is this course’s own data layer. The site runs on Phoenix LiveView; its
content is a map from route to a page record, keyed by a branded Snowflake id, and the
set of built routes is what the link checker tests against. Three angles open the module — lookup,
membership, and the hash underneath.
key → hash → bucket
"/maps" and "/sets" both hash to index 3 — a collision, resolved by chaining.
The page registry
Every page on this site is one entry in a map: the route is the key, a %Page{}
struct is the value, and the struct carries a branded Snowflake id that doubles as a cross-system pivot key.
Looking up a page, checking whether a route is built, hashing the key — select an angle.
The angle · select one
role: look up a page by route
expression: Map.fetch(pages, route) #=> {:ok, page}
One map, three jobs: it resolves a route to a page, its key set answers membership, and a hash of the key is what keeps both from degrading into a scan. The dives take each in turn.
Three deep dives
In order: looking values up in a map, testing membership in a set, and the hashing that makes both constant-time — each grounded in the course’s own registry.
Map.get, Map.fetch, and Map.put over the page registry — and why a LiveView’s socket.assigns is itself a map.MapSet.member? is the link checker; union, intersection, and difference compose the built and planned route sets.:erlang.phash2 turns a key into a slot, collisions resolve, and Elixir stores entries in a 32-way HAMT.Advanced: sort vs hash, and the HAMT
Two ways to make lookup cheap, with opposite trade-offs. A sorted array or a balanced tree keeps order and searches in O(log n); a hash map throws order away and looks up in O(1) on average, at the cost of needing a good hash and offering no meaningful iteration order. For the course registry that is the right trade — you fetch a page by exact route, never by “the next route after this one.”
Elixir keeps the constant small with structure. A small map (up to 32 keys) is a flat sorted array; a larger
one becomes a hash array mapped trie — a tree that branches 32 ways on chunks of the
key’s hash, so its depth is about log₃₂ n, four levels for
millions of keys. That is F4.05, and it is also what backs a LiveView’s socket.assigns.
# the course data layer, in spirit: pages = Jonnify.Course.pages() # %{route => %Page{}}, keyed by branded id Map.fetch(pages, "/elixir/algorithms/maps") # {:ok, %Page{}} · O(1) average MapSet.member?(built_routes, route) # true · the links gate # small map: flat. large map: a 32-way HAMT, depth ~ log32 n (F4.05)
F4.03 · ordering buys O(log n) search
Sort once, then binary-search the sorted sequence.
F4.04 · hashing buys O(1) lookup
No order at all — a hash sends the key straight to its slot.
Start with maps & key lookup, then MapSet & membership, then hashing & collisions. Next module: F4.05 — Hash Array Mapped Tries (HAMT), where the 32-way branching this module points at is built explicitly — the start of the persistent-map spine.
References
Primary sources for this lesson, and where it connects in the course.
Sources
- Hash table — Wikipedia — hashing and collisions.
Map/MapSet— Elixir documentation — maps and sets in Elixir.