func main() {
m := map[interface{}]int{
1: 1,
"a": 2,
}
m[[]int{1, 2, 3}] = 3
m[func() {}] = 4
}
// panic: runtime error: hash of unhashable type []int
// panic: runtime error: hash of unhashable type func()
登入後複製
Everything looks fine until you try to assign an uncomparable type as a map key.
That's when you'll hit a runtime error, which is trickier to deal with than a compile-time error. Because of this, it's usually a good idea to avoid using interface{} as a map key unless you have a solid reason and constraints that prevent misuse.
But that error message: "hash of unhashable type []int" might seem a bit cryptic. What's this about a hash? Well, that's our cue to dig into how Go handles things under the hood.
Map Anatomy
When explaining the internals of something like a map, it's easy to get bogged down in the nitty-gritty details of the Go source code. But we're going to keep it light and simple so even those new to Go can follow along.
What you see as a single map in your Go code is actually an abstraction that hides the complex details of how the data is organized. In reality, a Go map is composed of many smaller units called "buckets."
type hmap struct {
...
buckets unsafe.Pointer
...
}
登入後複製
Look at Go source code above, a map contains a pointer that points to the bucket array.
This is why when you assign a map to a variable or pass it to a function, both the variable and the function's argument are sharing the same map pointer.
But don't get it twisted, maps are pointers to the hmap under the hood, but they aren't reference types, nor are they passed by reference like a ref argument in C#, if you change the whole map m2, it won't reflect on the original map m1 in the caller.
In Go, everything is passed by value. What's really happening is a bit different: when you pass the map m1 to the changeMap function, Go makes a copy of the *hmap structure. So, m1 in the main() and m2 in the changeMap() function are technically different pointers point to the same hmap.
Map is passed by value
For more on this topic, there's a great post by Dave Cheney titled There is no pass-by-reference in Go.
Each of these buckets can only hold up to 8 key-value pairs, as you can see in the image below.
Buckets of a map
The map above has 2 buckets, and len(map) is 6.
So, when you add a key-value pair to a map, Go doesn't just drop it in there randomly or sequentially. Instead, it places the pair into one of these buckets based on the key's hash value, which is determined by hash(key, seed).
Let's see the simplest assignment scenario in the image below, when we have an empty map, and assign a key-value pair "hello": 1 to it.
Assign a key-value pair to an empty map
It starts by hashing "hello" to a number, then it takes that number and mods it by the number of buckets.
Since we only have one bucket here, any number mod 1 is 0, so it's going straight into bucket 0 and the same process happens when you add another key-value pair. It'll try to place it in bucket 0, and if the first slot's taken or has a different key, it'll move to the next slot in that bucket.
Take a look at the hash(key, seed), when you use a for-range loop over two maps with the same keys, you might notice that the keys come out in a different order:
func main() {
a := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6}
b := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6}
for i := range a {
print(i, " ")
}
println()
for i := range b {
print(i, " ")
}
}
// Output:
// a b c d e f
// c d e f a b
登入後複製
How's that possible? Isn't the key "a" in map a and the key "a" in map b hashed the same way?
But here's the deal, while the hash function used for maps in Go is consistent across all maps with the same key type, the seed used by that hash function is different for each map instance. So, when you create a new map, Go generates a random seed just for that map.
In the example above, both a and b use the same hash function because their keys are string types, but each map has its own unique seed.
"Wait, a bucket has only 8 slots? What happens if the bucket gets full? Does it grow like a slice?"
Well, sort of. When the buckets start getting full, or even almost full, depending on the algorithm's definition of "full", the map will trigger a growth, which might double the number of main buckets.
But here's where it gets a bit more interesting.
When I say "main buckets," I'm setting up for another concept: "overflow buckets." These come into play when you've got a situation with high collisions. Imagine you have 4 buckets, but one of them is completely filled with 8 key-value pairs due to high collisions, while the other 3 buckets are sitting empty.
The full post is available here: https://victoriametrics.com/blog/go-map/.
