gohashmapdynamic-arrays

Store dynamic arrays in a hash table in Golang?


In Go, people use "slices" as dynamic arrays, because plain arrays have sizes that should be known at compile time.

But while equality is conceptually simple for dynamic arrays, Go does not define it for slices (because slices behave differently depending on other things in the underlying array). As a result, slices cannot be used as keys in a map.

And so there is no simple way to store dynamic arrays in a hash table in Go.

How do Go programmers work around this limitation? Do people write their own hash table implementations for this?


Solution

  • Slices are not allowed as map keys to prevent subtle bugs due to mutating keys after they are placed on the map. A slice is a view over an array, so if you use a slice key to insert a value to a map and then someone changes the underlying array, the inserted value becomes unreachable using the old key. Arrays can be used as map keys, because when you assign an array, its contents will be copied, and there is no way to modify an existing map key.

    That said, the use of slices as map keys is sometimes necessary (i.e. writing a cache based on a slice of values), and you can hack it by creating a map of maps for every element in a slice. This does not work with higher order slices, but works reasonably well for slices of comparables (e.g. []string) containing relatively few elements. An implementation of this idea is here: https://github.com/bserdar/slicemap