Go maps in action | Hacker News Reader

Go maps in action

blog.golang.org

67 pointszoowar19 comments

I don't really get it. It's a hash. Big deal.

I know what a hash is. Wow, Go has hashes. Yeah, I knew that too.

blinks So... yeah. I mean, it's the Go blog, so cool. Blog about things in the language, but in terms of 'interesting things about Go' or 'interesting things about tech I expect to see on hacker news frontpage' this is pretty much a 0 for me...

So an article titled "Go maps in action" is about Go maps and... you're underwhelmed? Dissatisfied? This is an article for people who want to learn about Go maps. I'm not sure what you expected.

You would be surprised how valuable these kinds of "entry level" articles are. I get more grateful mail about the basic articles than I do the advanced ones, because the audience is so much wider.

So, not for you I guess.

reminds me of people defending reposts on reddit.

Yeah I've never seen it three minutes ago on frontpage, so the repost is OK for me and people like me.

Maps in Go is definitely a good lesson for hackers who doesn't know about maps...

The fact that slices cannot be used as keys in maps was, for me, a fairly big turn off.

Using a slice as a key doesn't make much sense; a slice is a fundamentally-mutable view onto an underlying array, which itself may be mutable.

Quick testing shows that you can use arrays:

    func main() {
        a := [4]int{1,2,3,4}
        m := make(map[[4]int]string)
        m[a] = "Hello"
        fmt.Println(m[[4]int{1,2,3,4}])
    }

Although that will be klunky, since the size of the array is in the type of the array. And still mutable. Mutating keys is bad.

In all my years of using maps, I can't think of when I wanted to index by something that was truly an arbitrary-length array of things. If you want to index by something like a tuple of things, declare a datatype for that purpose. What exactly are you trying to do by using a slice as a key?

I was lazy when I complained about not be able to use slices as keys, I guess I really meant to complain that there is no arbitrary-length immutable sequence type that I can use as keys to a map (other than strings, which are sequences of characters and are allowed as keys to a map).

For an example where you might want to do this consider storing a count of the frequency with which different words follow a given n-gram (sequence of n words) in some corpus, the sort of thing you'd need to make a Markov chain nonsense text generator (like the example programs in chapter 3 of The Practice of Programming: http://cm.bell-labs.com/cm/cs/tpop/code.html).

Of course, you can always take your immutable sequences and represent them as strings, as other languages such as Perl, Awk and Lua force you to do. But I really like that I'm not forced to use such kludges in, say, Python or Haskell.

http://play.golang.org/p/tLhF-JIRVv forget using strings like Perl, Awk, and Lua.

Sorry if I'm being stupid, but how does this solve the problem of using arbitrary/variable length sequences of, say, numbers as map keys?

Doing m[f(a)] = b is not that much less convenient than m[a] = b. You can wrap it in a function if it seems easier. If f() seems expensive, then you should reconsider whether you should be using a (hash) map at all (or use a struct and cache the key value in there.)

Just to be clear: you are not explaining how car54whereareu's code solves the problem of using arbitrary length sequences as keys, but rather explaining a different solution, right?

car54whereareu's code, which uses structs as keys doesn't seem to me as if it would work for variable length sequences given Go's types.

Your solution is what I had in mind when I said above you can concert your keys to strings. The way I see it there are two cases for m[f(a)]:

1. f is injective: this pretty much forces f to return a string, since it must return a data type that is allowed as a key and that can represent arbitrary length sequences without loss of information.

2. f is not injective: then we're using f as a hash function and we need to store the full key inside the value (i.e., m[f(a)]=pair(a,b)) so look ups can make equality checks for the key. You also need to handle f-collisions somehow (I just described disallowing keys with the same f, but that may not work for certain applications). You are basically writing your own hash table at this point.

Based on my understanding, you're right-- you'd have to use a string to get a truly arbitrary length key. However, you can use interface types as I've commented above, which gives you some flexibility, but not truly arbitrary flexibility.

If you want to tune for performance, you can always replace the convert-to-string code with something custom later. I've seen a few HashTable implementations in Go floating around on the internet.

Yes you are right, using a struct for a key does not directly solve the variable length key problem. Until I read the article I didn't know you could use structs for keys, that's all, but thanks for expecting deeper thoughts.

Because of golang I'm starting to wonder just how many keys a person might want, and that's a different way of thinking for someone used to python or clojure.

This is a problem in a number of languages, in various guises. Generally you'll want the solution as outlined car54whereareu, but I don't deny that Go makes it harder to vary the type parameter than I'd like (it's easy to make a map with a 3-tuple key, easy to make a map with a 4-tuple key, not easy to pick between them without sacrificing type safety somewhere). It works almost exactly like Haskell, if you couldn't just say "a" for the key type of a map. And if you have no good way to label keys as immutable.

You can use interfaces types as the keys to a map. So you could easily have a map with both 3-tuples and 4-tuples as keys, just by having one struct with 3 elements and one with 4 implement the same interface and using that as the key. Of course, if you want a truly arbitrary length key, you'll probably have to use the convert-to-string trick.

A map is a hash table. I'm confused as to why you don't use either a custom hashing function or your own custom datatype that organizes your data according to the sequence order of your key. While a generic hashing function that can operate on any type of data could be implemented in the language, I believe the flexibility of defining the hashing function yourself is perfectly acceptable considering the performance implications of having a universal hash function. The reason why is this: The table lookup should fundamentally be roughly an O(1) operation after hashing your key value. A universal hashing function that operates on arbitrary-length immutable sequences would likely be an additional O(n) (where n is the length of the sequence) complexity built into the map structure. I don't believe that's acceptable from a language standpoint.

There's nothing stopping you writing your own hash map that can be configured with a custom hash function.

The builtin map is limited to types for which the language defines ==. It's a simplifying trade-off; I don't think "acceptable" versus "unacceptable" enters into it. One could imagine expanding the builtin map type to support a hash function, and that was something that was considered early on, but it added complexity that just wasn't needed most of the time.

Another application of arbitrary-length sequences is storing sparse multivariable polynomials as maps from monomials to coefficients.

Very helpful, thanks for posting this! The parts about map declaration vs. make() vs. new() are the most valuable tidbits, I think. A lot of the rest is mostly just very handy tips and pointers.

Go everyday, but still going.

Reply on news.ycombinator.com