Hacker News Reader

Comment by itripn | Hacker News Reader

People needs to stop confusing "random" with "non-deterministic". It is a stated attribute of a Hash Map (leaving aside special classes, such as a Tree Map), that iteration of keys will occur in a non-deterministic order.

That is different than random. Random implies that iterating the same Map twice (without intervening updates) will produce different results. I've never met a Hash Map for which that was true.

The irony is that the poster's own code violates the point he was trying to make -- when run under go 1.2.1, it produces insertion order results every time (at least for me). I've also never met a Hash Map (until this example in Go) which predictably produced insertion order key iteration. I am sure even here, it is mere coincidence.

I do believe the poster lacks a formal understanding of data structures. My apologies if that is incorrect, and I am missing his point.

View on HN

Yes, you are missing the point.

In Go, iteration order of keys was always non-deterministic.

At some point it was changed to be also random i.e. iterating the same hash the second time would produce a different sequence of key/values than the first time.

This is exactly what the article says, except using more words.

Listen. Order of key iteration is well understood attribute of a Hash Map, and it's always non-deterministic. That's what I have said, and I am not missing the point. The poster tries to imply an insertion order iteration in hash maps that has never existed.

My second, arguably more interesting point, is that the poster's own code violates the premise of his post.

Order of key iteration in a Hash Map is not non-deterministic, unless the hash is using a random salt. Unless you are using a random salt for each Hash Map, hashes can be precomputed and will always be the same for the same input of keys, therefore deterministic even though it may look non-deterministic in nature.

On the other hand, I agree that the author of the article, does not seem to understand the underlying data structures. Either that, or the way he has written the article portrays lack of understanding.

It is quite possible that pre 1.0 they may not have been using a hash map at all, and instead they were using an ordered map, which would have given an insertion order iteration.

Although note this is pure speculation as I have not tested this on pre 1.0, and in fact you may be absolutely correct that he is implying an iteration order that never existed.

What should be noted though is this: https://code.google.com/p/go/issues/detail?id=6719. It looks like that as of Go-1.3, there will be a sort of semi-random iteration, where while iterating each bucket in the hash map will be iterated over in increasing or decreasing order, chosen at random. Which is good as it is not too much of a performance hit, with the benefit that the iteration order will be non-deterministic for small maps, which is currently not the case.

EDIT:

Here is an explanation of iteration over Maps in Go <1.3 and >1.3:

Map iteration previously started from a random bucket, but walked each bucket from the beginning. Now, iteration always starts from the first bucket and walks each bucket starting at a random offset. For performance, the random offset is selected at the start of iteration and reused for each bucket.

Reply on news.ycombinator.com