Why can't Go slice be used as keys in Go maps

问题:

Why can't Go slice (which is an implementation of Go arrays) be used as keys in Go maps pretty much the same way arrays can be used as keys?

回答1:

Here's Nigel Tao's answer from https://groups.google.com/forum/#!topic/golang-nuts/zYlx6sR4F8Y:

One reason is that arrays are value types. If a0 is an [N]int (an array) then doing

a1 := a0
a1[0] = 0

will not affect a0[0] at all.

In comparison, slices refer to an underlying array. Copying a slice value is O(1) instead of O(length). If s0 is an []int (a slice) then doing

s1 := s0
s1[0] = 0

will affect what s0[0] is.

http://play.golang.org/p/TVkntIsLo8

Map keys need some notion of equality. For arrays, this is simply element-wise equality. For slices, there is more than one way to define equality: one is element-wise equality, another is referring to the same array backing store. Furthermore, does map insertion need to make an (expensive) copy of the entire backing array? Copying would probably be less surprising, but it is inconsistent with what assignment does.

What should this code snippet print?

m := make(map[[]int]bool)
s0 := []int{6, 7, 8}
s1 := []int{6, 7, 8}
s2 := s0
m[s0] = true
s2[0] = 9
println(m[s0])
println(m[s1])
println(m[s2])

Different programmers can have different expectations. To avoid confusion, we have simply decided not to allow slices as map keys for now.

回答2:

To answer the exact "why cant?":

Spec: Map types:

The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice.

The spec does not allow key types where comparison is not defined. Spec: Comparison operators also confirms this:

Slice, map, and function values are not comparable.

For reasoning, see smarx's answer (which quotes Nigel Tao's answer). And read on.

Go's map uses a hashmap implementation. In general (regardless of the programming language) mutating a value that is used as a key in a hashmap might result in undefined (or unexpected the least) behavior. Usually the hashcode of the key is used to designate the bucket in which the value (key-value pair) is placed. If the key changes and you ask for the associated value for that key, the implementation might look in the wrong bucket (and therefore report that it can't find it) because a changed key value most likely gives a different hashcode which might designate a different bucket.

In Go slices are just descriptors to a contiguous part of an underlying array, and assigning slice values only copies these descriptors. So using a slice as key you would expect that the map implementation only copies this slice header (which is the pointer to the first referenced element in the underlying array, the length and the capacity). It would only work if hash comptation and equality would use these 3 elements and nothing else, but to us (humans, programmers) a slice means the elements that can be accessed through the slice header - which can also be modified (causing problems described above).

If a map would allow a slice as keys, to function properly, it would have to update its internal state and data structure whenever a slice element of any slice (that is used as a key) is modified which is not to be expected.

Arrays are cool in this regard: an array means all its elements; copying an array copies all the elements, and comparison is defined like:

Array values are comparable if values of the array element type are comparable. Two array values are equal if their corresponding elements are equal.

And if you modify an element of an array that you used as a key before: not a problem as the new array (with that modified element) is not equal to the original which is stored and used in the map, so querying the associated value with the modified array will justifiably yield no results, and querying with the unmodified, original array will properly give you back the previously stored value.