29 March 2026 · 3 min
Consider the following problem. You have a large set of strings, maybe millions. You need to map these strings to 8-byte integers (uint64). These integers are given to you.
If you are working in Go, the standard solution is to create a map. The construction is trivial, something like the following loop.
m := make(map[string]uint64, N)
for i, k := range keys {
m[k] = values[i]
}
One downside is that the map may use over 50 bytes per entry.
In important scenarios, we might have the following conditions. The map is large (a million of entries or more), you do not need to modify it dynamically (it is immutable), and all queried keys are in the set. In such conditions, you can reduce the memory usage down to almost the size of the keys, so about 8 bytes per entry. One fast technique is the binary fuse filters.
I implemented it as a Go library called constmap that provides an immutable map from strings to uint64 values using binary fuse filters. This data structure is ideal when you have a fixed set of keys at construction time and need fast, memory-efficient lookups afterward. You can even construct the map once, save it to disk so you do not pay the cost of constructing the map each time you need it.
The usage is just as simple.
package main
import (
"fmt"
"log"
"github.com/lemire/constmap"
)
func main() {
keys := []string{"apple", "banana", "cherry"}
values := []uint64{100, 200, 300}
cm, err := constmap.New(keys, values)
if err != nil {
log.Fatal(err)
}
fmt.Println(cm.Map("banana")) // 200
}
The construction time is higher (as expected for any compact data structure), but lookups are optimized for speed. I ran benchmarks on my Apple M4 Max processor to compare constmap lookups against Go’s built-in map[string]uint64. The test uses 1 million keys.
| Data Structure | Lookup Time | Memory Usage |
|---|---|---|
| ConstMap | 7.4 ns/op | 9 bytes/key |
| Go Map | 20 ns/op | 56 bytes/key |
ConstMap is nearly 3 times faster than Go’s standard map for lookups! And we reduced the memory usage by a factor of 6.
The ConstMap may not always be faster, but it should always use significantly less memory. If it can reside in CPU cache while the map cannot, then it will be significantly faster.
Source Code The implementation is available on GitHub: github.com/lemire/constmap.
Daniel Lemire, "A Fast Immutable Map in Go," in Daniel Lemire's blog, March 29, 2026, https://lemire.me/blog/2026/03/29/a-fast-immutable-map-in-go/.
[BibTeX]
When the set of key/values is immutable, that brings up to me the topic of perfect hashing, of generating perfect hashing code (see the old favorite https://staff.itee.uq.edu.au/havas/TR0242.pdf), and also the balance between online construction and offline pre-compiled construction (where some of the memory cost can be moved from D-cache to I-cache). In short there are a lot of dimensions of merit for designing an immutable map and where the tradeoffs change depending on key space size, cache size, memory use..
Would iteration through such a map be possible?
Apologies if this is somewhere in the paper, I couldn’t easily grok it from the code.
I am not sure why you mean by iteration. The map does not store the keys, right? If you do have a list of keys, then you can, of course, query them in sequence.
Sorry, my comment has indeed made no sense. Or rather, only after your answer I see how wrong I was;)
I was thinking of a use that we have for experiment evaluation. The keys are known at compile time, but values change dynamically per request. There are “many” keys (20+), but not keys are looked up. Map is immutable, so in theory fits here, but sadly thrown away after evaluation so probably this wouldn’t be the best fit… unless perhaps we can define a “shape” of a map, to perhaps pre-build them and save on the creation.
Anyway, this is very cool, thank you!
“(it is immutable), and all queried keys are in the set. In such conditions, you can reduce the memory usage down to almost the size of the keys, so about 8 bytes per entry. One fast technique is the binary fuse filters.”
Er… a binary fuse filter is an approximate membership query data structure. But you don’t need membership information; you’ve stated the assumption that that “all queried keys are in the set”.
It sounds like you’re describing a “retrieval data structure” which maps a finite input set to b-bit values with no constraint on the returned value if the input is not in the set. This can indeed be implemented (for static data) in barely more than bN bits of storage. But not with a binary fuse filter.
This can indeed be implemented (for static data) in barely more than bN bits of storage. But not with a binary fuse filter.
I shared the code.
Hi,
Looks like it degrades with larger data sets, with benchN = 25_000_000:
goos: darwin
goarch: arm64
pkg: github.com/lemire/constmap
cpu: Apple M3 Max
BenchmarkConstMap-14 26225161 45.70 ns/op
BenchmarkVerifiedConstMap-14 22703551 52.66 ns/op
BenchmarkGoMap-14 30896678 47.21 ns/op
PASS
ok github.com/lemire/constmap 155.764s
Thanks anyways!
At 25M keys, a map data structure is going to use about 1 GB of RAM. The construction I propose is going to use about 200 MB.
So, going by your numbers, you get the same performance with 4 to 5 times less memory usage. I’d call it a win, wouldn’t you?
Sure, no doubt. But the access time degrades, same as for smaller then 400_000. No criticism here, simply for the sake of accuracy 🙂
But the access time degrades
What your number shows is about the same speed, not degraded.
Maybe I was not fully clear, sorry then. With 1_000_000 size it almost 3 times faster then go map. With 25mil or less then 400K it is almost the same as go map. Or I am mistaking?
The general idea is that a data structure that uses less memory can be faster if it can reside in faster memory (cache) while the larger data structure cannot.
Sure, depends on CPUs arch and cache sizes. ““
Tnx, nice work.
We can only use this if we are sure we will only query keys which are actually in the constmap right? Whereas a regular map will return a nil value in that case.
That’s the idea, yes.