Module C4.04

Maps, sets & hashing

A key reaches a value two ways on .NET — a hash to a bucket, or a comparison down a tree. F# defaults to the tree, and the choice is the whole module.

The Elixir course teaches this in E4.04 as one idea: a hash map looks a value up in O(1) average, and a set is the same machinery answering membership. F# re-derives it on .NET with a fork that has to be taught honestly. System.Collections.Generic.Dictionary is a mutable hash table — O(1) average, no order. F#'s Map and Set are immutable balanced search trees — O(log n), ordered by comparison, and a new value every write. Both are real and both have their place; this module builds all three across three dives. The running example is the F# EchoMQ port's queue state, which holds a Map<string, Job> of rows and a Set<string> of pending ids at once. Every snippet was produced by dotnet fsi.

The three dives Back to C4 · Algorithms

One key, three structures

A keyed collection answers one of three questions: what value sits at this key (a map), is this element present (a set), and how does the key reach its place at all (hashing). On .NET the third question has two answers. A hash table runs the key through GetHashCode(), picks a bucket, and reads in O(1) average — that is Dictionary. A balanced search tree compares the key down O(log n) levels and reads in order — that is F#'s Map and Set.

The first dive states hashing and the cost model, and draws the Dictionary vs Map fork in full. The second takes the immutable map: Map.add, Map.tryFind, and the rule that every write returns a new map sharing the old one. The third takes the set: membership, idempotent dedup, the ordered minimum, and set algebra. Each closes with how the F# EchoMQ port uses the structure.

The three dives · select one

C4.04.1 · Hashing & the cost model

A hash turns a key into a slot for O(1) average lookup — that is Dictionary. F#'s Map takes the other road: a comparison tree, O(log n), ordered. The dive draws both and the trade between them.

You learn how a key reaches a slot, and the Dictionary-vs-Map fork

Open this dive · or pick another above

The same key, three jobs: a map resolves it to a value, a set answers whether it is present, and hashing or comparison is what gets it there. Read the cost from which road the structure takes.

The rows map and the pending set, side by side

Select a structure. The diagram marks the rows it touches, the code shows the F# (verified in dotnet fsi), and the readout names what the operation costs. The fixed data is the F# EchoMQ port's queue state: a Map of three job rows keyed by branded id, and a Set of pending ids.

The structure · select one

cost: O(log n) — a comparison tree

The rows are a tree keyed by id, so they read in order and share on every write; the pending ids are the same tree without values, answering membership. A Dictionary would trade that order for a smaller constant.

The module's running example — the rows map and the pending set

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

Every dive in this module carries an EchoMQ in F# block, grounded in the real echo_fs port — the F# skeleton of the EchoMQ bus at the repository root. One queue's state holds two of this module's structures at once: a Map of job rows and a Set of pending ids. That single record ties the module together — a map read by key, a set tested for membership, both immutable and shared.

EchoMQ in F#

One queue's state is a record. Two of its fields are this module's structures — quoted verbatim from echo_fs/EchoMQ/Store.fs:

/// One queue's state.
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>
      // … Schedule, Active, Dead, Paused, Completed, Failed }

Admission writes both at once — refuse a duplicate id, else add the row to the map and the id to the set (verbatim, echo_fs/EchoMQ/Store.fs):

if st.Rows.ContainsKey id then
    st, Admission.Duplicate
else
    let row = Job.create id payload
    { st with
        Rows = st.Rows.Add(id, row)
        Pending = st.Pending.Add id },
    Admission.Enqueued

The in-memory Store keeps the rows and the pending set today (echo_fs/EchoMQ/Store.fs, Job.fs — built and tested). The Valkey transport (EchoMQ.Connector) lands next; until then Connector.eval raises "EchoMQ Valkey connector: coming soon".

The three dives

Read them in order. Each stands on valid F#: every // val it : echo below the code was produced by dotnet fsi, and each carries an EchoMQ in F# block grounded in the echo_fs port. Together they take a keyed collection from the cost model, through the immutable map, to the set.

live module hub built dive ready soon specified

C4.04.1built

Hashing & the cost model

A key to a slot via GetHashCode — O(1) average. The fork: Dictionary (hash) vs Map (comparison tree, O(log n), ordered).

EchoMQthe rows keyed by branded id — a Map, ordered, not a hash bucket

C4.04.2built

Immutable maps

Map.add / Map.tryFind / Map.containsKey; every write returns a new map, the old one intact — structural sharing.

EchoMQStore.Rows is a Map; Rows.Add(id, row) is a fresh map

C4.04.3built

Sets

Set.add / Set.contains; membership, idempotent dedup, the ordered minimum, and set algebra.

EchoMQStore.Pending is a Set; Set.minElement is the oldest id

Elixir E4.04 · one idea

Elixir's Map and MapSet are hash structures — O(1) average lookup, a 32-way HAMT underneath — the model the Elixir course teaches.

F# C4.04 · two structures

F# splits the choice: Dictionary is the hash table (O(1) average), Map / Set are comparison trees (O(log n), ordered, immutable). The module teaches both.

References

Sources

Microsoft — F# documentation — F# collections, Map and Set.
FSharp.Core API reference — the Map and Set modules.
The F# Software Foundation — F#'s home on the .NET runtime.
Microsoft — .NET documentation — Dictionary<TKey,TValue> and GetHashCode.

Related in this course

Elixir — Maps, sets & hashing (E4.04) — the sibling this module reflects.
C4 — Algorithms & Data Structures — the chapter this module opens.
C1.07 — Collections — list, array, seq, Map & Set — the F# collection types in depth.
C4.04.1 — Hashing & the cost model — start the module here.