This post discusses how maps are implemented in Go. It is based on a presentation I gave at the GoCon Spring 2018 conference in Tokyo, Japan.
What is a map function?
To understand how a map works, let’s first talk about the idea of the map function. A map function maps one value to another. Given one value, called a key, it will return a second, the value.
map(key) → value
Now, a map isn’t going to be very useful unless we can put some data in the map. We’ll need a function that adds data to the map
insert(map, key, value)
and a function that removes data from the map
delete(map, key)
There are other interesting properties of map implementations like querying if a key is present in the map, but they’re outside the scope of what we’re going to discuss today. Instead we’re just going to focus on these properties of a map; insertion, deletion and mapping keys to values.
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics