Dive C4.04.1

Hashing & the cost model

A key reaches a value two ways: a hash to a bucket, or a comparison down a tree. .NET gives you both — and F# defaults to the tree.

A hash function turns a key into an integer; the integer picks a slot, and the value sits there. That is what lets a hash table look a value up in O(1) average time — no scan, no order. On .NET the hash table is System.Collections.Generic.Dictionary: mutable, bucketed by GetHashCode(). But F#'s own keyed collections, Map and Set, are not hash tables — they are balanced search trees, ordered by comparison, with O(log n) lookup and a new value on every write. The Elixir course (E4.04) teaches hashing as the one road to fast lookup; F# has two, and this dive draws the fork. Every echo below was produced by dotnet fsi.

Compare the two roads Module hub

C4.04.1 · part 1

A hash turns a key into a slot

Every .NET value carries a GetHashCode(): a function from the value to an int. A hash table sizes itself to some number of buckets, takes the hash modulo that count, and stores the entry in the chosen bucket. Two keys that land in the same bucket collide, and the table chains or probes to keep them apart. Because the bucket is computed, not searched for, lookup is O(1) on average — independent of how many keys the table holds.

let key = "JOB0a"
key.GetHashCode()    // val it : int = ...  (a 32-bit term hash)
// a hash table takes (hash &&& mask) to pick one of its buckets — O(1) average

hash function: GetHashCode() — maps a key to an int. Equal keys must hash equally.
bucket: one slot of the table; the entry lands in hash mod bucketCount.
collision: two distinct keys in the same bucket; resolved by chaining or probing.
O(1) average: lookup cost is independent of size, given a good hash and few collisions.

Two roads to a value: hash, or compare

Select a road. The Dictionary hashes the key straight to a bucket; the Map compares the key down a balanced tree. The diagram marks the path, the code shows the F# (verified in dotnet fsi), and the readout names the cost. The fixed keys are three branded job ids.

"JOB0a" reaches its value · select a road

cost: O(1) average — a hash bucket

A hash computes the slot; a tree compares its way down. The hash wins on the constant, the tree wins on order and immutability. F# defaults to the tree because its data is immutable and comparison is total.

C4.04.1 · part 2

The proof: a Map comes out sorted

The clearest evidence that Map is a comparison tree, not a hash bucket, is that its keys come back in order regardless of insertion order. A hash table has no meaningful order — its keys are scattered across buckets by hash.

let m =
    Map.empty<string,int>
    |> Map.add "JOB0c" 1
    |> Map.add "JOB0a" 2
    |> Map.add "JOB0b" 3

m |> Map.toList |> List.map fst
// val it : string list = ["JOB0a"; "JOB0b"; "JOB0c"]
// inserted c, a, b — read back a, b, c. A tree, ordered by comparison.

A Dictionary makes no such promise: d.Keys comes out in an unspecified order set by the hashing. If a structure has to read in key order — or be immutable and shared — that is the Map; if the only thing that matters is the smallest lookup constant, that is the Dictionary.

C4.04.1 · part 3

The cost model, side by side

Two structures, two cost models. The choice is rarely about raw speed at small sizes — both are fast — and more about whether order and persistence matter.

Dictionary vs Map / Set on .NET
property	Dictionary<'K,'V>	Map<'K,'V> / Set<'T>
structure	mutable hash table	immutable balanced search tree
lookup / insert	O(1) average, O(n) worst	O(log n)
order	none (hash order)	sorted by comparison
mutation	in place	a new value per write, shared
key requirement	equality + GetHashCode	total comparison

Elixir E4.04 — one hash structure

# Elixir — a hash map, O(1) average, 32-way HAMT underneath
Map.get(rows, "JOB0a")   # the row, in O(1) average

F# — two structures, the tree by default (verified in FSI)

// F# Map — a comparison tree, O(log n), ordered, immutable
Map.tryFind "JOB0a" rows   // val it : int option = Some 2
// reach for Dictionary only when O(1) mutation beats order + sharing

The efficiency note for the parity: Elixir's Map and MapSet are hash structures (a 32-way HAMT — the subject of the next two C4 modules), so their lookup is O(1) average. F#'s default Map / Set are O(log n) trees, trading a slightly larger asymptotic cost for total ordering and the same structural sharing. Where Elixir reaches one structure, F# offers the explicit choice.

EchoMQ in F#

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.

The F# EchoMQ port (echo_fs) keys each queue's job rows by the branded id. The field is a Map, not a Dictionary — so the rows are ordered by id, and because a branded id's bytes sort as its mint time, the row order is the mint order, for free.

EchoMQ in F#

The rows field is a Map from branded id to job row — quoted verbatim from echo_fs/EchoMQ/Store.fs:

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

Why a Map and not a hash Dictionary: the id is itself the comparison key, and id order is mint order (the Base62/Snowflake property), so the tree keeps the queue's rows time-ordered with no second index. Lookup costs O(log n) — a few comparisons over a queue's working set (verified in FSI over a fixed map):

let rows =
    Map.empty<string,string>
    |> Map.add "JOB0c" "row-c"
    |> Map.add "JOB0a" "row-a"
    |> Map.add "JOB0b" "row-b"

Map.tryFind "JOB0a" rows       // val it : string option = Some "row-a"
rows |> Map.toList |> List.map fst // val it : string list = ["JOB0a"; "JOB0b"; "JOB0c"]
// the rows read back in id order = mint order — a Dictionary would not

The in-memory Store keys its rows by branded id 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 cost model

A hash reaches a slot in O(1) average; a comparison tree reaches it in O(log n), ordered. F# offers both — Dictionary and Map.

The next dive

The store keeps the tree. The next dive takes the immutable Map in depth: add, tryFind, and a new map on every write.

Where this leads

The cost model is the fork: hash for the smallest constant, comparison tree for order and immutability. The next dive takes F#'s immutable Map — the structure the store uses — through its verbs and its structural sharing. The third takes the Set.

↑ C4.04 · Maps, sets & hashing C4.04.2 · Immutable maps → C4.04.3 · Sets

References

Sources

Microsoft — .NET documentation — Dictionary<TKey,TValue> and Object.GetHashCode.
FSharp.Core API reference — the Map module.
Microsoft — F# documentation — F# collection types and the value-vs-reference distinction.

Related in this course

Elixir — Maps, sets & hashing (E4.04) — hashing as the one road to fast lookup.
C4.04 — Maps, sets & hashing — the module hub.
C4.04.2 — Immutable maps — the next dive.
C1.07 — Collections — list, array, seq, Map & Set in F#.