Dictionaries and sets, and the 1.13 order change

Counting the letters of “mississippi” takes one line in a loop: counts[ch] = get(counts, ch, 0) + 1 gave 4 i’s, 1 m, 2 p’s and 4 s’s. Print a dictionary of five city names, though, and Julia 1.13.1 lists them as delhi, chennai, kolkata, mumbai, pune, while 1.12.7 and the 1.10 LTS list the same keys as kolkata, delhi, mumbai, chennai, pune, because Julia 1.13 replaced the hash function that decides where each key is stored.

This lesson builds, reads and updates dictionaries with runs recorded on all three releases. You will count and group with get and get!, see which keys a dictionary treats as the same, write code and tests that hold whatever the order, combine dictionaries with merge and mergewith, and compare two collections with sets.

A dictionary maps each key to one value

A dictionarydictionary: A collection of entries, each a key and a value, that finds the value of a key without searching the others: Julia's Dict. Each key appears once, and keys are compared with isequal., Julia’s Dict, holds entries of a key and a value and finds the value of a key without searching through the others. Each key appears once. The previous lesson built one from pairs; this program builds two by counting, the most common job a dictionary does:

# Counting with a dictionary: the letters of a word, then the words of a short weather note in Marathi and English.
counts = Dict{Char, Int}()
for ch in "mississippi"
    counts[ch] = get(counts, ch, 0) + 1          # get gives 0 while ch is not a key yet
end
println(sort!(collect(counts)))                  # sorted, so the print is the same on every run

note = """
आज पुण्यात पाऊस पडला. The rain started at six,
and the rain did not stop: पाऊस थांबला नाही.
आज शाळा बंद होती, so the gauge was read twice.
"""
words = split(lowercase(note), [' ', '\n', '.', ',', ':']; keepempty = false)
freq = Dict{String, Int}()
for w in words
    freq[w] = get(freq, w, 0) + 1
end
println(length(words), " words, ", length(freq), " different")
top = sort!(collect(freq); by = p -> (-p.second, p.first))   # most frequent first, then by word
for (w, n) in first(top, 5)
    println("  ", rpad(w, 6), n)
end
println("haskey(freq, \"rain\") = ", haskey(freq, "rain"), ", get(freq, \"snow\", 0) = ", get(freq, "snow", 0))
try
    freq["snow"]
catch err
    println(sprint(showerror, err))
end

by_station = Dict{String, Vector{Float64}}()
for (station, t) in [("Pune", 25.2), ("Kochi", 27.9), ("Pune", 24.8)]
    push!(get!(by_station, station, Float64[]), t)   # get! stores an empty vector the first time
end
println(sort!(collect(by_station)))
delete!(freq, "the")
println("after delete!: haskey = ", haskey(freq, "the"), ", ", length(freq), " keys")

from session import files, run

# Counting letters and words with get, then grouping with get!, on the current release.
files("word_counts.jl")
run("""
julia word_counts.jl
""")

$ julia word_counts.jl
['i' => 4, 'm' => 1, 'p' => 2, 's' => 4]
28 words, 23 different
  the   3
  rain  2
  आज    2
  पाऊस   2
  and   1
haskey(freq, "rain") = true, get(freq, "snow", 0) = 0
KeyError: key "snow" not found
["Kochi" => [27.9], "Pune" => [25.2, 24.8]]
after delete!: haskey = false, 22 keys

The first loop counts the letters. Step through it and watch what get returns for each one:

get(counts, ch, 0) returns the value stored for ch, or the default, 0, when ch is not a key yet, so one line both starts a new count and raises an old one. The same idiom counted the 28 words of a short weather note in Marathi and English, 23 of them different: “the” 3 times, and “rain”, “आज” and “पाऊस” twice each. The text was lowercased first, so “The” and “the” are one key.

Asking for a key that is missing is different from asking with a default. freq["snow"] stopped with KeyError: key "snow" not found, while haskey(freq, "rain") answered true and get(freq, "snow", 0) returned 0. Choose the form by what a missing key means: an error in your data, or a value you can supply.

get! goes one step further: when the key is missing it stores the default before returning it. push!(get!(by_station, station, Float64[]), t) created an empty vector for a station the first time it appeared and added to the same vector afterwards, which grouped the readings as "Pune" => [25.2, 24.8]. delete!(freq, "the") removed a key, leaving 22.

Two keys are the same key when isequal says so

A dictionary needs a rule for “the same key”. The documentation gives it: keys are compared with isequal and hashed with hash. The two must agree: values that are isequal must have the same hash, or the dictionary could not find one by the other.

# Which keys a Dict treats as the same: isequal decides, and hash must agree with it.
d = Dict(1 => :a, 1.0 => :b, -0.0 => :c, 0.0 => :d)
println(length(d), " entries; d[1] = ", repr(d[1]))
println(sort!(collect(d); by = string))          # sorted for a stable print
println("isequal(1, 1.0) = ", isequal(1, 1.0), ", hash(1) == hash(1.0): ", hash(1) == hash(1.0))
println("isequal(-0.0, 0.0) = ", isequal(-0.0, 0.0), ", although -0.0 == 0.0 is ", -0.0 == 0.0)

stations = Dict("Pune" => 1)
println("\"pune\" is a key: ", haskey(stations, "pune"), "; :Pune is a key: ", haskey(stations, :Pune))

key = [18.52, 73.86]                             # a vector as a key
places = Dict(key => "Pune")
push!(key, 560.0)                                # the key object changes after it was stored
println("length = ", length(places), ", haskey(places, key) = ", haskey(places, key))
println("haskey(places, [18.52, 73.86]) = ", haskey(places, [18.52, 73.86]))
fixed = Dict((18.52, 73.86) => "Pune")           # a tuple cannot change
println("tuple key found: ", haskey(fixed, (18.52, 73.86)))

from session import files, run

# Which keys a Dict treats as the same, and a key that changes after it was stored.
files("keys_isequal.jl")
run("""
julia keys_isequal.jl
""")

$ julia keys_isequal.jl
3 entries; d[1] = :b
Pair{Real, Symbol}[-0.0 => :c, 0.0 => :d, 1.0 => :b]
isequal(1, 1.0) = true, hash(1) == hash(1.0): true
isequal(-0.0, 0.0) = false, although -0.0 == 0.0 is true
"pune" is a key: false; :Pune is a key: false
length = 1, haskey(places, key) = false
haskey(places, [18.52, 73.86]) = false
tuple key found: true

Four pairs gave three entries. isequal(1, 1.0) is true and hash(1) == hash(1.0) printed true, so 1 and 1.0 are one key, and d[1] returned :b, the value written with the key 1.0. -0.0 and 0.0 are two keys, because isequal(-0.0, 0.0) is false even though -0.0 == 0.0 is true, a difference the floating-point lesson met for NaN as well. Strings compare exactly: “pune” is not the key “Pune”, and the symbol :Pune is not the string either.

The last lines store a vector as a key and then change that vector. Step through the lookups that followed:

The entry was still there, length(places) was 1, but no lookup could reach it: the changed vector had a new hash valuehash value: The number hash(x) computes from a value, which a Dict or a Set uses to choose where to store it. Values that are isequal have the same hash; Julia 1.13 changed the hash of many values, hash(42) among them. that led to an empty slot, and a new vector with the old numbers led to the right slot but no longer compared equal. The documentation warns that changing a stored key can leave a hash table internally inconsistent. A tuple key, (18.52, 73.86), cannot change, and the program found it.

The order of keys is unspecified, and Julia 1.13 changed it

The five cities went in as mumbai, delhi, chennai, kolkata and pune, and no release this track runs gave them back in that order:

# The order in which a Dict hands out its keys: not the order they went in, and not the same on every release.
cities = ["mumbai", "delhi", "chennai", "kolkata", "pune"]
d = Dict(c => length(c) for c in cities)
println("inserted:      ", join(cities, ", "))
println("keys(d):       ", join(keys(d), ", "))
println("hash(42):      ", hash(42))

grown = copy(d)
for k in 1:12
    grown["extra$k"] = k                         # the table grows and the keys are placed again
end
println("after growing: ", join(filter(in(cities), collect(keys(grown))), ", "))

println("sorted:        ", join(sort!(collect(keys(d))), ", "))
try
    println("sort(keys(d)): ", join(sort(keys(d)), ", "))
catch err
    println("sort(keys(d)): ", typeof(err))
end
same = Dict(c => length(c) for c in reverse(cities))
println("d == same:     ", d == same)            # == compares entries, not order

from session import files, run, use

# The same five keys on the current release, on 1.12.7 and on the 1.10 LTS: Julia 1.13 changed the hash function.
files("dict_order.jl")
run("""
julia --version
julia dict_order.jl
""")
use("1.12.7")
run("""
julia --version
julia dict_order.jl
""")
use("1.10.12")
run("""
julia --version
julia dict_order.jl
""")

$ julia --version
julia version 1.13.1
$ julia dict_order.jl
inserted:      mumbai, delhi, chennai, kolkata, pune
keys(d):       delhi, chennai, kolkata, mumbai, pune
hash(42):      16440345385870586648
after growing: chennai, kolkata, delhi, mumbai, pune
sorted:        chennai, delhi, kolkata, mumbai, pune
sort(keys(d)): chennai, delhi, kolkata, mumbai, pune
d == same:     true
$ julia --version
julia version 1.12.7
$ julia dict_order.jl
inserted:      mumbai, delhi, chennai, kolkata, pune
keys(d):       kolkata, delhi, mumbai, chennai, pune
hash(42):      1098236396662648698
after growing: chennai, pune, kolkata, mumbai, delhi
sorted:        chennai, delhi, kolkata, mumbai, pune
sort(keys(d)): MethodError
d == same:     true
$ julia --version
julia version 1.10.12
$ julia dict_order.jl
inserted:      mumbai, delhi, chennai, kolkata, pune
keys(d):       kolkata, delhi, mumbai, chennai, pune
hash(42):      1098236396662648698
after growing: chennai, pune, kolkata, mumbai, delhi
sorted:        chennai, delhi, kolkata, mumbai, pune
sort(keys(d)): MethodError
d == same:     true

The order comes from where each key sits. Julia’s Dict keeps its entries in a table of slots, and the source of 1.13.1 shows how a key is placed: its hash, cut down to the size of the table, picks a slot, and when that slot is taken the key goes into the next free one, a method called linear probing. Iterating walks the slots from the first to the last. The figure below is a small table of 8 slots built the same way, with one simplification so you can check every step by hand: the hash of a whole number is the number itself, so a key’s first slot is the key mod 8.

The keys went in as 23, 8, 41, 30 and 15 and sit in the slots as 8, 41, 15, 30 and 23, the order a loop over the table would give. Type 16 as the table size and run it again: four of the five keys move, and this time the slot order happens to match the order of insertion. A real Dict changes in both ways. When it grows, every key is placed again in a larger table: after 12 more keys the cities came out as chennai, kolkata, delhi, mumbai, pune on 1.13.1. And a new hash function places every key anew: Julia 1.13 hashes strings with a new function, RapidhashNano, and mixes small values such as integers differently too, so hash(42) printed 16440345385870586648 there but 1098236396662648698 on 1.12.7 and 1.10.12.

Code that must give the same result everywhere sorts what it prints or compares. sort!(collect(keys(d))) worked on all three releases, while sort(keys(d)) worked on 1.13.1 and threw a MethodError on 1.12.7 and 1.10.12, so it ties code to the newest release. d == same was true on every release, because == compares the entries, not the order. When the order of insertion matters, the OrderedDict of the OrderedCollections.jl package keeps it, as its documentation says.

merge and mergewith combine dictionaries

Two days of rain-gauge readings, in millimetres, sit in two dictionaries that share two gauges. Combining them raises one question: what happens to a key that is in both? merge keeps the value of the dictionary further right, and mergewith combines the two values with a function you give:

# Two days of rain-gauge readings, in mm, combined in two ways.
monday = Dict("Pune" => 12, "Nagpur" => 0, "Kochi" => 31)
tuesday = Dict("Pune" => 8, "Kochi" => 22, "Nashik" => 5)

latest = merge(monday, tuesday)                  # a key in both: the later Dict's value wins
println("merge:     ", sort!(collect(latest)))
totals = mergewith(+, monday, tuesday)           # a key in both: the values are combined with +
println("mergewith: ", sort!(collect(totals)))
mergewith!(+, monday, Dict("Nagpur" => 3))       # the ! form changes monday itself
println("monday:    ", sort!(collect(monday)))

# merge with a combining function: still runs on Julia 1.13, which deprecates it in favour of mergewith.
totals = merge(+, Dict("Pune" => 12), Dict("Pune" => 8))
println(totals)

from session import files, run

# merge and mergewith on two days of readings, then the older merge(+, ...) form with deprecation warnings switched on.
files("merge_counts.jl", "old_merge.jl")
run("""
julia merge_counts.jl
julia --depwarn=yes old_merge.jl
""")

$ julia merge_counts.jl
merge:     ["Kochi" => 22, "Nagpur" => 0, "Nashik" => 5, "Pune" => 8]
mergewith: ["Kochi" => 53, "Nagpur" => 0, "Nashik" => 5, "Pune" => 20]
monday:    ["Kochi" => 31, "Nagpur" => 3, "Pune" => 12]
$ julia --depwarn=yes old_merge.jl
┌ Warning: `merge(combine::Callable, d::AbstractDict, others::AbstractDict...)` is deprecated, use `mergewith(combine, d, others...)` instead.
│   caller = top-level scope at old_merge.jl:2
└ @ Core ~/demo/old_merge.jl:2
Dict("Pune" => 20)

Follow mergewith(+, monday, tuesday) as it builds its result:

merge gave Pune 8 and Kochi 22, tuesday’s values, while mergewith(+, …) added them, Pune 20 and Kochi 53. A key in only one dictionary goes into either result unchanged. Both return a new dictionary; mergewith! changes its first argument instead, and added Nagpur’s 3 mm to monday itself. mergewith needs Julia 1.5 or later, which every release this track runs has.

The second program uses an older form, merge(+, a, b). It still ran on 1.13.1 and gave Dict("Pune" => 20), but with deprecation warnings switched on, --depwarn=yes, Julia printed that it is deprecated and to use mergewith instead, as the 1.13 release notes say. Julia prints nothing by default, so such calls are easy to miss until a future release removes them.

A set keeps each value once

A setset: A collection that holds each value at most once, compared with isequal, such as Set(["A-101", "B-207"]). It answers x in s with a hash lookup, and the order of its elements cannot be relied on. is a collection that holds each value at most once, by the same isequal rule as the keys of a dictionary. In the source of Julia 1.13.1 a Set is a Dict whose values are all nothing, and x in s is haskey on that dictionary: a hash lookup, not a search through a list. Its order is unspecified too: the documentation calls it an implementation detail that cannot be relied on. This program compares two audits of a lab’s instruments by their serial numbers:

# Serial numbers of the instruments in a lab before and after an audit, as sets.
before = Set(["A-101", "A-102", "B-207", "C-330"])
after = Set(["A-101", "B-207", "C-330", "D-412", "B-207"])   # B-207 was counted twice
println(length(after), " instruments after the audit")
show_set(label, s) = println(rpad(label, 22), join(sort!(collect(s)), ", "))
show_set("in both:", intersect(before, after))
show_set("missing after audit:", setdiff(before, after))
show_set("new in the audit:", setdiff(after, before))
show_set("in exactly one:", symdiff(before, after))
show_set("in either:", union(before, after))
println("\"A-101\" in after: ", "A-101" in after, ", Set([\"A-101\"]) ⊆ before: ", Set(["A-101"]) ⊆ before)

# Flagging serial numbers that were counted twice, with in!, which tests and inserts in one call.
seen = Set{String}()
for serial in ["A-101", "B-207", "A-101", "C-330", "B-207"]
    if in!(serial, seen)                         # true if it was there already; otherwise it is added
        println("counted twice: ", serial)
    end
end
println(length(seen), " different serial numbers")

from session import files, run, use

# Set operations on two audits, then in! on the current release and on the 1.10 LTS, which does not have it.
files("inventory_sets.jl", "seen_twice.jl")
run("""
julia --version
julia inventory_sets.jl
julia seen_twice.jl
""")
use("1.10.12")
run("""
julia --version
!julia seen_twice.jl
""")

$ julia --version
julia version 1.13.1
$ julia inventory_sets.jl
4 instruments after the audit
in both:              A-101, B-207, C-330
missing after audit:  A-102
new in the audit:     D-412
in exactly one:       A-102, D-412
in either:            A-101, A-102, B-207, C-330, D-412
"A-101" in after: true, Set(["A-101"]) ⊆ before: true
$ julia seen_twice.jl
counted twice: A-101
counted twice: B-207
3 different serial numbers
$ julia --version
julia version 1.10.12
$ julia seen_twice.jl
ERROR: LoadError: UndefVarError: `in!` not defined
Stacktrace:
 [1] top-level scope
   @ ~/demo/seen_twice.jl:4
in expression starting at ~/demo/seen_twice.jl:3
[exit status 1]

Step down the operations the run printed:

The audit wrote down five numbers and the set kept four, because B-207 was counted twice. intersect, setdiff and union answered three different questions, and the order of the arguments of setdiff decided which one: A-102 is missing from the audit, D-412 is new to the list. "A-101" in after and Set(["A-101"]) ⊆ before, the subset test also written issubset, both gave true.

in!(serial, seen) tests and inserts in one call: it returned true for A-101 and B-207 the second time they appeared, and the loop ended with 3 different numbers. The 1.10.12 run stopped at that line with UndefVarError: `in!` not defined, because in! needs Julia 1.11. Code for the LTS writes the two steps out: serial in seen ? println(…) : push!(seen, serial).

Practise: an inventory difference

Check yourself on counting, keys, order, merging and sets. The session opens with the part of the lesson your answers have found hardest, and each wrong choice says what it overlooked:

Interview questions

Warm-up (fresher to 2–5 years): how does a Julia Dict decide that two keys are the same, and what does that mean for 1 and 1.0?

A Dict compares keys with isequal and finds them by hash, and the two agree: values that are isequal have the same hash. isequal(1, 1.0) is true and hash(1) == hash(1.0) is true, so 1 and 1.0 are one key: a dictionary built from 1 => :a and 1.0 => :b has a single entry, and d[1] returns :b, the value written last. isequal is stricter than == for floating-point zeros, so -0.0 and 0.0 are two keys, and it treats NaN as equal to itself, so NaN can be found. Strings compare exactly, so “Pune” and “pune” are different keys, and a string is never equal to a symbol of the same name.

Two harder questions follow, about a test that broke when Julia 1.13 changed the hash function and about a cache whose entries go missing. Decide your answer first, then open each first step:

Key takeaways

• get(d, k, default) gives a value or a default, get! also stores the default, d[k] throws a KeyError for a missing key, and delete! removes one.
• A Dict compares keys with isequal and finds them by hash, so 1 and 1.0 are one key, -0.0 and 0.0 are two, and a key that changes after it is stored can no longer be found.
• The order of a Dict follows its slots, so it changes when the table grows and when the hash changes, as it did in Julia 1.13; sort with sort!(collect(keys(d))) and compare with ==.
• merge keeps the later value of a shared key, mergewith(f, a, b) combines the two values, and merge(f, a, b) is deprecated from Julia 1.13.
• A Set keeps each value once; intersect, setdiff, union and ⊆ compare collections, and in!, from Julia 1.11, tests and inserts in one call.