Hash tables, equality and hashing

Suppose a route planner keeps a lookup table keyed by the whole list of stops, and one search walks a bucketA slot of a hash table's internal array; every key whose hash selects that slot is kept in a short list, walked by the equality function. of a thousand routes instead of jumping to one. Those routes share a long common prefix, and OCaml’s Hashtbl.hash reads only the first ten meaningful parts of a key, so a thousand of them receive the same hash and pile into one bucket. A hash table trades a little care over its keys for lookups that are often faster than a map’s; pick the wrong equality or hashing function and it decays into a slow association list.

You will add, replace and remove bindings and watch how they stack, meet the sharp edges of the polymorphic comparison and Hashtbl.hash, build a Hashtbl.Make table whose equality and hashing agree, repair a table that lets similar keys collide, and share one table safely between domains.

How add, replace and remove treat earlier bindings

A Hashtbl maps keys to values in place: unlike a map, it is changed by side effect, and Hashtbl.add never overwrites. It pushes a new binding on top of any earlier one for the same key, so the table behaves like a stack per key. The session builds a table of feature flags and watches one key, "fast_checkout", through every operation:

from session import toplevel

# add hides earlier bindings instead of replacing them; find returns the newest, find_all every binding newest
# first, and remove uncovers the one below. replace overwrites the current binding. find_and_replace and
# find_and_remove (OCaml 5.5) return the previous binding, None on the first insert. A table of feature flags per
# environment shows the stack. Values recorded with OCaml 5.5.1.
toplevel("""
let flags = Hashtbl.create 16;;
Hashtbl.add flags "fast_checkout" false;;
Hashtbl.add flags "fast_checkout" true;;
Hashtbl.find flags "fast_checkout";;
Hashtbl.find_all flags "fast_checkout";;
Hashtbl.length flags;;
Hashtbl.replace flags "fast_checkout" false;;
Hashtbl.find_all flags "fast_checkout";;
Hashtbl.length flags;;
Hashtbl.remove flags "fast_checkout";;
Hashtbl.find flags "fast_checkout";;
Hashtbl.find_and_replace flags "fast_checkout" true;;
Hashtbl.find_all flags "fast_checkout";;
Hashtbl.find_and_replace flags "dark_mode" true;;
Hashtbl.find_and_remove flags "fast_checkout";;
Hashtbl.find_and_remove flags "fast_checkout";;
Hashtbl.find_opt flags "fast_checkout";;
Hashtbl.mem flags "dark_mode";;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let flags = Hashtbl.create 16;;
val flags : ('_weak1, '_weak2) Hashtbl.t = <abstr>
# Hashtbl.add flags "fast_checkout" false;;
- : unit = ()
# Hashtbl.add flags "fast_checkout" true;;
- : unit = ()
# Hashtbl.find flags "fast_checkout";;
- : bool = true
# Hashtbl.find_all flags "fast_checkout";;
- : bool list = [true; false]
# Hashtbl.length flags;;
- : int = 2
# Hashtbl.replace flags "fast_checkout" false;;
- : unit = ()
# Hashtbl.find_all flags "fast_checkout";;
- : bool list = [false; false]
# Hashtbl.length flags;;
- : int = 2
# Hashtbl.remove flags "fast_checkout";;
- : unit = ()
# Hashtbl.find flags "fast_checkout";;
- : bool = false
# Hashtbl.find_and_replace flags "fast_checkout" true;;
- : bool option = Some false
# Hashtbl.find_all flags "fast_checkout";;
- : bool list = [true]
# Hashtbl.find_and_replace flags "dark_mode" true;;
- : bool option = None
# Hashtbl.find_and_remove flags "fast_checkout";;
- : bool option = Some true
# Hashtbl.find_and_remove flags "fast_checkout";;
- : bool option = None
# Hashtbl.find_opt flags "fast_checkout";;
- : bool option = None
# Hashtbl.mem flags "dark_mode";;
- : bool = true

Adding false then true left find returning the newest, true, while find_all returned [true; false], the current binding first, and length counted both. replace changed the top binding only, so find_all became [false; false]; remove took the top one off and uncovered the binding below, so find returned false again. Follow the stack of bindings for "fast_checkout" as each operation runs:

find_and_replace and find_and_remove, both new in OCaml 5.5, do the change and hand back the previous binding in one step: find_and_replace flags "fast_checkout" true returned Some false and left [true], while the same call on the never-seen "dark_mode" returned None. find_and_remove returned Some true the first time and None the second, once the key was gone.

That stacking is exactly what trips people up when they mean to update a value rather than keep its history.

What the polymorphic table trusts, and where it breaks

The polymorphic Hashtbl leans on two built-in functions: the structural comparison that = and compare use, and the hash functionhash function: A function that turns a key into an integer used to choose the key's bucket in a hash table; OCaml's built-in one, Hashtbl.hash, reads only a bounded part of the key. Hashtbl.hash. Both have edges worth knowing before you trust them with a key. The manual’s overview calls the table’s equality =, but the table’s own code calls compare, and the difference shows up below. The session puts each to the test:

from session import toplevel

# The polymorphic table leans on two built-in functions: the structural comparison and Hashtbl.hash. Both have sharp
# edges. Comparing values that contain a function raises; a cyclic value still hashes because hash stops early;
# nan is equal to itself under the built-in comparison, so it works as a key in the polymorphic table; and == asks a
# different question from =. Values recorded with OCaml 5.5.1.
toplevel("""
let price1 = ("in_rupees", fun paise -> paise / 100);;
let price2 = ("in_rupees", fun paise -> paise / 100);;
price1 = price2;;
compare price1 price2;;
let handlers = Hashtbl.create 16;;
Hashtbl.replace handlers "/" (fun () -> "home page");;
Hashtbl.replace handlers "/about" (fun () -> "about us");;
(Hashtbl.find handlers "/about") ();;
let hash_of_ring () = let rec ring = 1 :: 2 :: ring in Hashtbl.hash ring;;
hash_of_ring ();;
nan = nan;;
compare nan nan;;
let readings = Hashtbl.create 16;;
Hashtbl.replace readings nan "sensor offline";;
Hashtbl.replace readings nan "still offline";;
Hashtbl.length readings;;
Hashtbl.find_opt readings nan;;
"3" ^ "4" == "34";;
let code = "3" ^ "4";;
Repr.phys_equal code "34";;
code = "34";;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let price1 = ("in_rupees", fun paise -> paise / 100);;
val price1 : string * (int -> int) = ("in_rupees", <fun>)
# let price2 = ("in_rupees", fun paise -> paise / 100);;
val price2 : string * (int -> int) = ("in_rupees", <fun>)
# price1 = price2;;
Exception: Invalid_argument "compare: functional value".
# compare price1 price2;;
Exception: Invalid_argument "compare: functional value".
# let handlers = Hashtbl.create 16;;
val handlers : ('_weak1, '_weak2) Hashtbl.t = <abstr>
# Hashtbl.replace handlers "/" (fun () -> "home page");;
- : unit = ()
# Hashtbl.replace handlers "/about" (fun () -> "about us");;
- : unit = ()
# (Hashtbl.find handlers "/about") ();;
- : string = "about us"
# let hash_of_ring () = let rec ring = 1 :: 2 :: ring in Hashtbl.hash ring;;
val hash_of_ring : unit -> int = <fun>
# hash_of_ring ();;
- : int = 436528
# nan = nan;;
- : bool = false
# compare nan nan;;
- : int = 0
# let readings = Hashtbl.create 16;;
val readings : ('_weak3, '_weak4) Hashtbl.t = <abstr>
# Hashtbl.replace readings nan "sensor offline";;
- : unit = ()
# Hashtbl.replace readings nan "still offline";;
- : unit = ()
# Hashtbl.length readings;;
- : int = 1
# Hashtbl.find_opt readings nan;;
- : string option = Some "still offline"
# "3" ^ "4" == "34";;
- : bool = false
# let code = "3" ^ "4";;
val code : string = "34"
# Repr.phys_equal code "34";;
- : bool = false
# code = "34";;
- : bool = true

A value that contains a function cannot be reliably compared: price1 = price2 and compare price1 price2 both raised Invalid_argument "compare: functional value". The manual says equality between functional values raises, and that compare applied to them may raise. A table whose keys hold functions therefore raises whenever it must compare two different ones, which happens when they share a bucket, so keep functions out of the keys. They are fine as values, though: the handler table stored two and called (Hashtbl.find handlers "/about") () to get "about us". Hashtbl.hash examined a cyclic list and returned 436528 without looping, because it stops after a bounded number of nodes; the manual promises that hash always terminates and accepts a value of any type, while it warns that the comparison itself “may not terminate” on a cycle, so never compare cyclic values.

nan is the subtle one. nan = nan is false, yet compare nan nan is 0, and the polymorphic table compares with compare: storing nan twice left length at 1 and find_opt returned Some "still offline". This table reads what each built-in does with a tricky key:

The last lines separate the structuralstructural equality: Comparing two values by their contents with =, so two separately built strings with the same characters are equal. == compares identity instead. More in “Booleans, characters, strings and bytes” question from the physical one, as the booleans and strings lesson first drew it: "3" ^ "4" == "34" was false and Repr.phys_equal code "34" was false, because the two strings are different values in memory, while code = "34" was true. Repr.phys_equal, from OCaml 5.4, is the named form of ==, and = is now Repr.equal.

Hashtbl.Make needs an equality and a hash that agree

When keys need their own notion of equality, Hashtbl.Make builds a table from a module with a type t, an equal and a hash. The one rule that ties them together, from the manual, is that equal a b being true must imply hash a = hash b: two keys the table should treat as one must land in the same bucket, or equal never gets to compare them. The session builds a case-insensitive table of Indian city names, once with a hash that forgets to lower-case and once with a hash that agrees:

from session import run, write

# Hashtbl.Make needs an equal and a hash that agree: if equal a b is true, hash a must equal hash b. A
# case-insensitive city table whose hash forgets to lower-case breaks that rule, so the same city lands in two
# buckets; lowering the case in the hash as well fixes it. The choice of equal also decides whether nan behaves.
# Counts and findings, not timings. Recorded with OCaml 5.5.1.
write("cities.ml", """module Broken = Hashtbl.Make (struct
  type t = string
  let equal a b = String.lowercase_ascii a = String.lowercase_ascii b
  let hash = Hashtbl.hash
end)

module City = Hashtbl.Make (struct
  type t = string
  let equal a b = String.lowercase_ascii a = String.lowercase_ascii b
  let hash s = Hashtbl.hash (String.lowercase_ascii s)
end)

let show = function Some n -> string_of_int n | None -> "not found"

let () =
  let b = Broken.create 16 in
  List.iter (fun (c, pin) -> Broken.replace b c pin)
    [ "Pune", 411001; "Mumbai", 400001; "PUNE", 411057 ];
  Printf.printf "broken hash: equal says Pune = pune, but hashes agree? %b\\n"
    (Hashtbl.hash "Pune" = Hashtbl.hash "pune");
  Printf.printf "broken hash: find \\"pune\\" = %s, entries = %d (one city twice)\\n"
    (show (Broken.find_opt b "pune")) (Broken.length b);
  let c = City.create 16 in
  List.iter (fun (city, pin) -> City.replace c city pin)
    [ "Pune", 411001; "Mumbai", 400001; "PUNE", 411057 ];
  Printf.printf "fixed hash:  equal and hash agree on Pune and pune? %b\\n"
    (Hashtbl.hash (String.lowercase_ascii "Pune")
     = Hashtbl.hash (String.lowercase_ascii "pune"));
  Printf.printf "fixed hash:  find \\"pUnE\\" = %s, entries = %d\\n"
    (show (City.find_opt c "pUnE")) (City.length c)
""")
run("""
ocamlopt cities.ml -o cities
./cities
""")

# The equality a Make uses also decides how a tricky value such as nan behaves as a key.
write("nan_key.ml", """module Plain = Hashtbl.Make (struct
  type t = float let equal = ( = ) let hash = Hashtbl.hash
end)
module Total = Hashtbl.Make (struct
  type t = float let equal = Float.equal let hash = Hashtbl.hash
end)

let found = function Some _ -> "found" | None -> "not found"

let () =
  let a = Plain.create 16 in
  Plain.replace a nan "offline"; Plain.replace a nan "offline";
  Printf.printf "equal = (=):        nan gives %d entries, lookup %s\\n"
    (Plain.length a) (found (Plain.find_opt a nan));
  let t = Total.create 16 in
  Total.replace t nan "offline"; Total.replace t nan "offline";
  Printf.printf "equal = Float.equal: nan gives %d entries, lookup %s\\n"
    (Total.length t) (found (Total.find_opt t nan))
""")
run("""
ocamlopt nan_key.ml -o nan_key
./nan_key
""")

$ ocamlopt cities.ml -o cities
$ ./cities
broken hash: equal says Pune = pune, but hashes agree? false
broken hash: find "pune" = not found, entries = 3 (one city twice)
fixed hash:  equal and hash agree on Pune and pune? true
fixed hash:  find "pUnE" = 411057, entries = 2
$ ocamlopt nan_key.ml -o nan_key
$ ./nan_key
equal = (=):        nan gives 2 entries, lookup not found
equal = Float.equal: nan gives 1 entries, lookup found

The broken table had equal lower-case its arguments but left hash reading the raw string, so "Pune" and "PUNE" hashed to different buckets: looking up "pune" found nothing, and the table ended with three entries for two cities. Lower-casing inside hash as well put every spelling in one bucket, where equal could merge them, so find "pUnE" returned 411057 and length was 2. Step through why the agreeing hash makes the lookup land where the key lives:

The choice of equal also decides how a difficult value behaves. With equal = ( = ), nan gave two entries that could not be found, because nan = nan is false; with equal = Float.equal, which agrees with compare x y = 0, the table held one entry and found it. The manual lists that pairing, compare x y = 0 with hash, as the one that handles nan correctly, and lists ( == ) with hash for keys compared by physical equality, such as mutable or cyclic objects.

When similar keys pile into one bucket

Hashtbl.hash is seeded_hash_param 10 100 0: it reads at most ten meaningful nodes of a key, and at most a hundred nodes in all, then stops. The session confirms the identity and shows what the bound costs when keys share a long prefix, as the route table does. The same bounded hash put a thousand keys into one memo-table bucket in the sequences lesson; here it is a weakness to repair:

from session import run, write

# Hashtbl.hash reads at most ten meaningful nodes of a key, so keys that are alike in their first ten nodes collide,
# whatever the seed. A route table keyed by the whole list of stops is the weakness: a thousand routes that share a
# long prefix all land in one bucket. Keying by a hash of the whole route is the fix. The check counts key
# comparisons and the longest bucket, failing on the weak table and passing on the fix. Counts, not timings;
# recorded with OCaml 5.5.1.
write("routes.ml", """let route last = List.init 10 (fun i -> Printf.sprintf \"S%02d\" i) @ [ last ]

let () =
  Printf.printf \"hash \\"Pune\\" = %d = seeded_hash_param 10 100 0 (%d)\\n\"
    (Hashtbl.hash \"Pune\") (Hashtbl.seeded_hash_param 10 100 0 \"Pune\");
  Printf.printf \"seeded_hash of \\"Pune\\": seed 1 = %d, seed 2 = %d\\n\"
    (Hashtbl.seeded_hash 1 \"Pune\") (Hashtbl.seeded_hash 2 \"Pune\");
  let a = route \"Agra\" and z = route \"Kochi\" in
  Printf.printf \"two routes differ (%b) yet share one hash (%b)\\n\"
    (a <> z) (Hashtbl.hash a = Hashtbl.hash z);
  Printf.printf \"a seed does not separate them: seed 1 %b, seed 2 %b\\n\"
    (Hashtbl.seeded_hash 1 a = Hashtbl.seeded_hash 1 z)
    (Hashtbl.seeded_hash 2 a = Hashtbl.seeded_hash 2 z);
  Printf.printf \"reading the whole key does: 11 nodes %b, concat %b\\n\"
    (Hashtbl.hash_param 11 100 a <> Hashtbl.hash_param 11 100 z)
    (Hashtbl.hash (String.concat \"/\" a) <> Hashtbl.hash (String.concat \"/\" z));
  let routes = List.init 1000 (fun k -> route (Printf.sprintf \"D%04d\" k)) in
  let distinct f = List.sort_uniq compare (List.map f routes) |> List.length in
  Printf.printf \"1000 routes, distinct hashes: default %d, whole-key %d\\n\"
    (distinct Hashtbl.hash) (distinct (fun r -> Hashtbl.hash (String.concat \"/\" r)));
  let tests = ref 0 in
  let module Weak = Hashtbl.Make (struct
    type t = string list
    let equal a b = incr tests; a = b
    let hash = Hashtbl.hash
  end) in
  let module Whole = Hashtbl.Make (struct
    type t = string list
    let equal a b = incr tests; a = b
    let hash r = Hashtbl.hash (String.concat \"/\" r)
  end) in
  let weak = Weak.create 16 in
  tests := 0; List.iter (fun r -> Weak.replace weak r ()) routes;
  let wi = !tests in
  tests := 0; List.iter (fun r -> ignore (Weak.find weak r)) routes;
  let wf = !tests in
  let whole = Whole.create 16 in
  tests := 0; List.iter (fun r -> Whole.replace whole r ()) routes;
  let hi = !tests in
  tests := 0; List.iter (fun r -> ignore (Whole.find whole r)) routes;
  let hf = !tests in
  let weak_max = (Weak.stats weak).Hashtbl.max_bucket_length in
  let whole_max = (Whole.stats whole).Hashtbl.max_bucket_length in
  Printf.printf \"weak table: %d comparisons to fill, %d to find all; longest bucket %d\\n\" wi wf weak_max;
  Printf.printf \"whole-key:  %d comparisons to fill, %d to find all; longest bucket %d\\n\" hi hf whole_max;
  let healthy m = m <= 16 in
  Printf.printf \"bucket check (longest <= 16): weak %b, whole-key %b\\n\"
    (healthy weak_max) (healthy whole_max);
  let rnd = Hashtbl.create ~random:true 16 in
  List.iter (fun r -> Hashtbl.replace rnd r ()) routes;
  Printf.printf \"random seed on: holds %d, finds a route %b, longest bucket %d\\n\"
    (Hashtbl.length rnd) (Hashtbl.mem rnd (route \"D0999\"))
    (Hashtbl.stats rnd).Hashtbl.max_bucket_length
""")
run("""
ocamlopt routes.ml -o routes
./routes
""")

$ ocamlopt routes.ml -o routes
$ ./routes
hash "Pune" = 409604893 = seeded_hash_param 10 100 0 (409604893)
seeded_hash of "Pune": seed 1 = 79970758, seed 2 = 887172893
two routes differ (true) yet share one hash (true)
a seed does not separate them: seed 1 true, seed 2 true
reading the whole key does: 11 nodes true, concat true
1000 routes, distinct hashes: default 1, whole-key 1000
weak table: 499500 comparisons to fill, 500500 to find all; longest bucket 1000
whole-key:  1456 comparisons to fill, 1945 to find all; longest bucket 9
bucket check (longest <= 16): weak false, whole-key true
random seed on: holds 1000, finds a route true, longest bucket 1000

hash "Pune" was 409604893, exactly seeded_hash_param 10 100 0 "Pune". Two routes that differ only in their eleventh stop shared one hash, a collisionhash collision: When two keys that are not equal receive the same hash and so share a bucket, where the equality function tells them apart; some collisions are unavoidable and expected., under hash and under every seed, because the hash stops before the eleventh node; reading the whole key, with hash_param 11 100 or by hashing String.concat "/" route, told them apart. Over a thousand routes sharing a ten-stop prefix, the default hash produced a single distinct value: the weak table made 499,500 comparisons to fill and 500,500 to find them all, in one bucket of length 1,000. Keying by the whole route gave 1,000 distinct hashes, 1,456 comparisons to fill, and a longest bucket of 9. The same idea with small numbers and thirteen slots, where keys that share a home slot k mod 13 form one chain:

This visualiser adds each key to the end of its bucket’s list, while OCaml’s own table adds to the front, as the first section showed; the length of a bucket, which is what slows a lookup, is the same either way. A check that the longest bucket stays at most 16 failed on the weak table and passed on the whole-key table, which is the test to keep.

A random seed is a different defence, and a narrower one. Creating a table with ~random:true, or calling Hashtbl.randomize (), picks the hash randomly from about 2^30 functions, which the manual recommends for tables that hold untrusted keys because it defeats keys chosen in advance against the fixed seed. But the randomized table’s longest bucket still held all 1,000 routes: a seed changes the numbers, not how much of the key the hash reads, so keys that differ only past the examined part collide under every seed. Only reading the whole key separates them.

These two defences answer different threats, so a table exposed to outside input often wants both at once.

Sharing a table between domains needs a lock

A Hashtbl is mutable and carries no lock of its own. The manual states it plainly, as an alert on the module: “Unsynchronized accesses to hash tables are a programming error.” Two domainsdomain: An OCaml 5 unit of parallel execution: Domain.spawn starts a function on a new domain, which runs OCaml code on another processor, and Domain.join waits for its result. More in “Parallelism with domains and atomics” that add to one table at the same moment can lose an update or leave the table in an invalid state, because a resize or a bucket update is several steps that must not interleave. The session fixes it with a Mutex: every update runs inside Mutex.protect, which locks the mutex, runs the body and always releases it, even on an exception:

from session import run, write

# One hash table shared by four domains. Every update runs inside Mutex.protect, so the domains take turns and no
# update is lost: the two page counters add up to exactly the work done. Only the safe version runs here; the
# version without the lock is a programming error, so its result is not reproducible and is never recorded. The
# totals below are the same on every run. Recorded with OCaml 5.5.1.
write("visits.ml", """let () =
  let hits = Hashtbl.create 16 in
  let m = Mutex.create () in
  let bump page =
    Mutex.protect m (fun () ->
        let n = Option.value ~default:0 (Hashtbl.find_opt hits page) in
        Hashtbl.replace hits page (n + 1))
  in
  let worker () =
    for i = 1 to 25_000 do bump (if i mod 2 = 0 then "/home" else "/search") done
  in
  let domains = List.init 4 (fun _ -> Domain.spawn worker) in
  List.iter Domain.join domains;
  Printf.printf "pages tracked: %d\\n" (Hashtbl.length hits);
  Printf.printf "/home   = %d\\n" (Hashtbl.find hits "/home");
  Printf.printf "/search = %d\\n" (Hashtbl.find hits "/search");
  Printf.printf "total   = %d (4 domains x 25,000 updates)\\n"
    (Hashtbl.fold (fun _ n acc -> acc + n) hits 0)
""")
run("""
ocamlopt visits.ml -o visits
./visits
""")

$ ocamlopt visits.ml -o visits
$ ./visits
pages tracked: 2
/home   = 50000
/search = 50000
total   = 100000 (4 domains x 25,000 updates)

Four domains each made 25,000 updates, split between two page counters. Under the lock the updates took turns, so nothing was lost: /home and /search each ended at exactly 50,000 and the total was 100,000, the same on every run. The sequence below is what the lock enforces for one shared key, one domain at a time:

Without the mutex nothing about the result is promised: two domains can read the same count, each add one and write it back, losing an increment, and the manual warns that unsynchronized accesses may leave the table itself in an invalid state. That race is a programming error, so this lesson runs only the safe version. Mutex.protect arrived in OCaml 5.1, and a Mutex is the smallest fix; a table under heavy parallel load is better replaced by one table per domain, merged at the end.

Practise: bindings, equality, hashing and locks

These questions run new keys and new numbers through the lesson’s tables. Work out each result or count in your head before you open the answer:

Interview questions

Warm-up (fresher to 2–5 years): what separates Hashtbl.add from Hashtbl.replace, and which job suits each?

Hashtbl.add tbl k v pushes a new binding for k on top of any earlier one: find then returns the newest, find_all returns every binding newest first, length counts them all, and remove takes the top one off and uncovers the binding below. Hashtbl.replace tbl k v instead overwrites the current binding, so a key keeps a single entry. Use replace for the common case of a mutable map, where each key has one value you update; the table then stays the size of the key set. Use add only when the stack is the point, for example a scope stack where a name can be shadowed and the earlier meaning must return after a remove, which is the behaviour an association list also has. A loop that uses add to update a running total is the usual bug: it hides every old total and grows the table without bound.

Two deeper questions follow. Work out your own first move for each, then open the first step on its page:

Key takeaways

• Hashtbl.add stacks bindings and remove uncovers them, so a key behaves like a stack; replace overwrites the top, and the 5.5 find_and_replace and find_and_remove return the previous binding, None on the first insert.
• The polymorphic table tests keys with the built-in compare and Hashtbl.hash: comparing two different function-holding keys can raise, a cyclic key may make it loop while hash stops early, and nan works as a key only because compare treats it as equal to itself.
• Hashtbl.Make needs an equal and a hash that agree: a hash that forgot to lower-case a city name kept the same city in two buckets, and lowering the case in both fixed it.
• Hashtbl.hash reads at most ten meaningful nodes, so a thousand routes sharing a ten-stop prefix fell into one bucket; a random seed stops crafted keys, but only hashing the whole key spreads out long similar keys.
• A hash table shared between domains is a programming error without a lock; four domains made 100,000 updates with none lost once each update ran inside Mutex.protect.