0

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?

Improve this question
12
  • 2
    You don't need to write an entire hash-table implementation, you just define a proxy key for your slice depending on how you want to define equality. e.g. for a slice of bytes you could hash those bytes. You can always store a slice in a map. (if equality were simple, it would be defined, but it is not -- see also the FAQ: go.dev/doc/faq#map_keys) Commented Aug 5, 2024 at 17:02
  • @JimB Two dynamic arrays are equal if they have the same length and their elements are equal. Two slices are equal, if they have the same length and capacity and their elements are equal. If Go made either choice, it would work for me, but it decided to do neither, and that's tedious to work around. Commented Aug 5, 2024 at 17:14
  • Why not equal if just length and elements are equal, since allocation patterns may be different but result in the same data (which is how slices.Equal works)? Why not equal only if the backing arrays are the same address? Are pointers equal, or what they point to? What about slices of slices? Regardless of how you want to define it, it's not a feature of the language, and it's not difficult to work around in the rare cases you need a map key based on a slice. Commented Aug 5, 2024 at 17:19
  • 1
    @MWB arrays are not mutable as keys, because assignment of an array is always a copy of the entire value. Commented Aug 5, 2024 at 17:30
  • 3
    Technically, slices are not dynamic arrays. They are views on arrays. Commented Aug 5, 2024 at 17:37

1 Answer 1

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Accepting this for now, as this seems to be the best suggestion so far. I'm curious if it's possible to do better, performance-wise, using unsafe and reflect though.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.