fastutil's hash maps

OpenHashMap<K, V> and OpenHashSet<T> are the open hash maps and sets of fastutil, the library many Java programs, Minecraft among them, keep their tables in: Long2ObjectOpenHashMap, Object2IntOpenHashMap, LongOpenHashSet and the rest. After the same operations, a loop goes over their keys in the order fastutil’s would. They’re for code ported from Java where the order shows. Everywhere else, Map and Set are faster.

CalxOutput

Tested

fn main() {
    var chunks = OpenHashMap<i64, String>()
    for x in 0i64..4 {
        chunks.insert((x << 32) | x, "chunk {x}")
    }
    println("{chunks}")
    var counts = OpenHashMap<String, i32>()
    for w in ["stone", "dirt", "stone", "sand"] {
        if counts.contains(w) {
            counts[w] += 1
        } else {
            counts.insert(String(w), 1)
        }
    }
    println("{counts} {counts["stone"]}")
    var seen = OpenHashSet<i32>()
    for k in [5, 0, -3, 5] {
        seen.insert(k)
    }
    println("{seen} {seen.contains(0)}")
}

Both are built in, like Map and Set. Indexing, loops, ==, printing, copy(), and moving and freeing work the same way as theirs (maps and sets). The key type needs JavaHash.

fastutil’s classes

fastutil has a class for each key type and value type. The key type is what picks the order; the value type doesn’t change it, so one Calx type stands for all of a key type’s classes:

Calx	fastutil
OpenHashMap<i32, V>, and i8, i16, u8, u16, u32, char and rune keys	Int2ObjectOpenHashMap<V>, Int2IntOpenHashMap, Int2LongOpenHashMap, and Byte2…, Short2… and Char2…
OpenHashMap<i64, V>, and u64 and usize keys	Long2ObjectOpenHashMap<V>, Long2IntOpenHashMap, Long2ByteOpenHashMap and the rest
OpenHashMap<K, V> for any other K	Object2ObjectOpenHashMap<K, V>, Object2IntOpenHashMap<K>, Object2BooleanOpenHashMap<K> and the rest
OpenHashSet<i32>, OpenHashSet<i64>, OpenHashSet<T>	IntOpenHashSet, LongOpenHashSet, ObjectOpenHashSet<T>, and ShortOpenHashSet and CharOpenHashSet

An integer key is placed by fastutil’s mix of the number itself, as the primitive classes do. Any other key is placed by mix of its java_hash, which is its Java hashCode, as the Object2… classes do. So a Long key in an Object2… table, whose hashCode isn’t the number, is written as a struct holding the i64, with the java_hash Long.hashCode gives.

fastutil’s methods

fastutil	Calx
new Long2ObjectOpenHashMap<>(), new LongOpenHashSet()	OpenHashMap<K, V>(), OpenHashSet<T>()
new …(expected), new …(expected, f)	OpenHashMap<K, V>(n), OpenHashMap<K, V>(n, f), with f an f32
put(k, v), add(x)	m.insert(k, v), s.insert(x)
get(k), getInt(k), containsKey(k), contains(x)	m[k] or m.get(k), m.contains(k), s.contains(x)
get(k) after defaultReturnValue(d)	m.get(k) ?? d
remove(k), removeInt(k)	m.remove(k), which gives the value or none
addTo(k, n), putIfAbsent, computeIfAbsent, merge	if m.contains(k) { m[k] += n } else { m.insert(k, n) }, and the like
size(), isEmpty(), clear(), trim()	len(), is_empty(), clear(), trim()
putAll(m2), addAll(c)	m.reserve(m2.len()), then m.insert for each key of m2, in its order
new …(m2), new …(c)	OpenHashMap<K, V>(m2.len()), reserve(m2.len()), then the inserts
clone()	m.copy()
Going over keySet(), values(), long2ObjectEntrySet() or forEach	for (k, v) in m
A loop that calls the iterator’s remove()	a loop that marks the keys, then m.remove_marked(marks) (below)

• Every way of adding a key puts it in the same slot, the first empty one from where its hash points, so addTo, putIfAbsent, computeIfAbsent and merge are written as contains and insert.
• OpenHashMap(n, f) sizes the table as fastutil does: the power of two at least n / f, and at least 2. Without them it’s fastutil’s default, room for 16 keys at a load factor of 0.75, which is 32 slots. A load factor that isn’t between 0 and 1 panics, as fastutil throws.
• reserve(n) is the room putAll and addAll make: room for len() + n keys, or, at a load factor of 0.5 or less, for n alone, as fastutil does.
• trim() shrinks the table to the smallest power of two that holds its keys, if that’s smaller. clear keeps the table’s size.
• Removing a key can shrink the table, to half its size, when it’s left less than a quarter full and is bigger than it started and than 16 slots, as fastutil’s does.
• copy() is clone(): the same slots, so the same order. A table built from another’s keys, as fastutil’s copy constructors build one, can go in another order, since the keys go in in the order the first table holds them:

CalxOutput

Tested

fn main() {
    var ids = OpenHashSet<i32>(4, 0.5)
    for k in [17, 1, 33, 2] {
        ids.insert(k)
    }
    var built = OpenHashSet<i32>(ids.len())
    built.reserve(ids.len())
    for k in ids {
        built.insert(k)
    }
    println("{ids} {built} {ids.copy()}")
    var big = OpenHashSet<i64>(1000)
    for k in 1i64..7 {
        big.insert(k * 100)
    }
    println("{big}")
    big.trim()
    println("{big}")
}

Taking out marked keys

m.remove_marked(marks) takes out each key whose mark is set, marks being a List<bool> with one mark for each key, in the order a loop over the table goes. It moves the keys as a loop over fastutil’s table that calls its iterator’s remove on those keys does, so the keys left are in fastutil’s places, and it gives the order that loop goes over the keys in, as each key’s place in the marking loop.

That isn’t always the table’s order. Taking a key out moves the keys after it in its run back, and one that moves from the first slots to the last, past the end of the table, is one the loop has gone past, so fastutil’s iterator goes over it at the end. Java code takes keys out with the iterator where it does something for each key as it goes, such as telling something else about each key it takes out. The order remove_marked gives is the order to do those things in:

CalxOutput

Tested

fn main() {
    // Each chunk's ticket, with the ticks it has left.
    var left = OpenHashMap<String, i32>()
    let chunks = ["w0", "w1", "w2", "w11", "w20", "w21", "w22", "w25", "w26", "w30"]
    let ticks = [0, 0, 0, 1, 0, 1, 1, 0, 0, 1]
    for i in 0usize..10 {
        left.insert(String(chunks[i]), ticks[i])
    }
    // Those with none left come out, as a Java loop takes them out with the
    // iterator, and each chunk is told about in the order that loop gets to it.
    var keys = List<String>()
    var marks = List<bool>()
    for (k, v) in left {
        keys.push(k.copy())
        marks.push(v == 0)
    }
    println("{keys}")
    var told = List<String>()
    for i in left.remove_marked(marks) {
        told.push(keys[i].copy())
    }
    println("{told}")
    println("{left}")
}

Taking w1 out moved w21 from the first slot to the last, which the loop had gone past, so the loop gets to it after w25.

• There’s a mark for each key, and a different number of marks panics: `remove_marked` needs a mark for each key: 3 marks for 2 keys.
• The loop doesn’t halve the table as it goes, as fastutil’s iterator doesn’t, so a table that lost most of its keys keeps its size. A key the loop gets to at the end is taken out as remove takes one out, which halves a table that’s left a quarter full.
• The marks are all made before any key comes out, so a key’s mark can’t depend on what the loop did before it got there. Loops that decide each key by the key and its value alone, as most do, work this way.

Order

The order is fastutil’s, worked out from rules its tables keep:

• A table is a power of two slots. A key’s slot is the first empty one from its hash, masked to the table’s size, going up and wrapping around.
• An integer table marks an empty slot with 0, so the key 0 is kept apart, and a loop goes over it first. Then a loop goes from the last slot to the first.
• An insert that finds the table holding its maximum, the slots times the load factor and less than all of them, rehashes it to the size for one more key than it then holds. Rehashing goes from the last slot down, putting each key in the new table the same way.
• Removing a key moves each later key of its run that would be found from the gap back into it, as fastutil’s shiftKeys does, so the table never needs a marker for a removed key.

OpenHashMap and OpenHashSet were checked against fastutil 8.5.18, the version Minecraft 26.3 ships, by running the same random operations on both: inserts, removes, lookups and addTo, putAll and addAll as reserve and inserts, trim, clear, and new tables of random sizes and load factors from 0.25 to 0.99. The keys were ints, including 0 and dense runs of small numbers, longs, strings and a record whose many keys share each hash, in long phases of adding and of removing, so tables grew to 4,096 slots and shrank about 450 times in each run. 60 runs of 50,000 operations, 3 million in all, went over the same keys in the same order at every one of 375,060 checks.

remove_marked was checked against fastutil 8.5.18’s iterators in a probe that runs fastutil itself, whose open tables run loops that remove the keys a modulus picks, and compare the order each loop goes in and the table after it. Of 7,698 such loops in 420 cases, 183 went out of the table’s order and 17 halved the table at the end, and every one matched, on Windows and Linux.

What’s different

• A table can’t change during a loop over it, which is a compile error. fastutil lets an iterator remove the key it’s on, which moves other keys and changes the order the rest of the loop goes in; in Calx, a loop marks the keys and remove_marked takes them out, giving the order fastutil’s loop would have gone in.
• Keys and values can’t be null. An Object2… table’s null key, which fastutil keeps apart like an integer table’s 0, isn’t there.
• fastutil’s Reference2… tables, and its Custom ones with a hash strategy, aren’t built. A Reference2… table places keys by their addresses, so its order changes from run to run, and code ported from Java has to pick a fixed one where the order shows.
• fastutil’s linked tables, Long2ObjectLinkedOpenHashMap and the rest, go in the order keys were added, which doesn’t come from fastutil’s hashing, so they’re LinkedMap and LinkedSet.

In C

• The table is named for its types, such as cx_omap_i64_String and cx_oset_i32. It’s an array of slots, each the key, or the key and value, in place; for keys that aren’t integers, an array of words beside it; and the runtime’s cx_ohead, the size, the keys and the load factor. A table that’s made empty allocates nothing until its first key.
• An integer table’s slots have room for one more, slot n, where the key 0 goes, and a 0 key in another slot means it’s empty. A table of other keys keeps, for each slot, the 30 bits of the key’s mixed hash that place it in any table, with the top bit set, and 0 for an empty slot, so finding a key compares words before keys, and rehashing never hashes a key again.
• A key and its value are in one slot, where fastutil keeps them in two arrays, so a lookup that finds a key reads one place.
• remove_marked tags each slot with its key’s place in a loop, moves the tags with the keys as it takes keys out from the last slot to the first, and keeps a list of the keys that move past the end, which it takes out last by their hashes, as fastutil’s iterator keeps one. The tags are one 32-bit word a slot, for the length of the call.
• Finding, inserting, removing and rehashing compile to C specialized for the key and value types, as Map’s do. The sizes fastutil picks, which don’t depend on the types, are the runtime’s, in calx_ohtable.c, linked into a program only when it uses these tables.