F4.04 · part 2 of 3
MapSet & membership
A set holds unique elements and answers one question fast: is this element present?
MapSet.member? does it in O(1), the same keyed lookup as a map. Sets also combine:
union, intersection, and difference
let you reason about whole collections at once.
The course keeps a set of built route strings; the link checker that grades every page asks whether each internal href is in it. Here that set meets the set of all F4 chapter routes. Select an operation.
Membership and set algebra
Two sets: built (routes whose modules are shipped) and f4
(every route in this chapter). Some routes are in both, some only one. Ask membership, or combine the sets.
The operation · select one
role: is the route in the set? O(1)
result: true
Membership is a single keyed lookup; the algebra builds on it. intersection
keeps what is in both sets, difference keeps what is in the first but not the second
— here, the F4 modules still to be built.
Advanced: a set is a map
A MapSet is a map whose keys are the elements and whose values are a placeholder, so
membership is exactly the O(1) map lookup from the previous dive, and adding a duplicate is a no-op —
which is why MapSet.new/1 deduplicates. Like a map it has no meaningful order. Reach
for a set when you need uniqueness or membership; a list when order matters and you will scan anyway; a map
when each key carries a value. The course’s link checker is one line in spirit:
MapSet.member?(allowed_routes(), href), and the same shape underlies
Phoenix.Presence, which tracks the set of users currently on a topic.
# a MapSet is a map under the hood; new/1 dedups MapSet.new([1, 2, 2, 3]) # => MapSet.new([1, 2, 3]) # the links gate, in spirit: def valid_link?(href), do: MapSet.member?(allowed_routes(), href) # set vs list vs map — pick by the question you ask # set: is X present? are these unique? (O(1) membership) # list: what is the order? walk them all (O(n) membership) # map: what value does key X hold? (O(1) lookup)
F4.04.1 · a map keys values
Each key resolves to a value in O(1).
F4.04.2 · a set keys presence
The element is the key; membership is the same O(1) lookup, returning a boolean.
Next: hashing & collisions — the mechanism under both, and why O(1) holds.
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.