3 ms·

It's completely unclear from this post whether the poster is a) a student who doesn't understand hash tables and is using the word "random" in its colloquial se

by blahedo 12y ago

It's completely unclear from this post whether the poster is a) a student who doesn't understand hash tables and is using the word "random" in its colloquial sense of "arbitrary", or b) someone who did know that hash tables store in a non-obvious order and is using the word "random" in its technical sense. Given that the poster says that "you would think" the iteration order has anything to do with the insertion order, and doesn't show multiple iteration runs with different results, I'm rather inclined to assume the former. Is there evidence in the other direction?

dickeytk 12y ago
it is random, isn't it? https://code.google.com/p/go/source/detail?r=02c15930f43c https://code.google.com/p/go/source/detail?r=02c15930f43c
- teraflop 12y ago
  Well, sort of. The hash table stores elements in a semi-deterministic order, dependent only on the keys and a per-map hash seed. Every time you iterate over it, you start at a randomly-chosen point in the table and iterate sequentially. So although you can't rely on seeing elements in the same order on any particular iteration, the order itself is far from uniformly random.
  - deleted 12y ago
    [deleted]
ahuth 12y ago
Here: http://blog.golang.org/go-maps-in-action http://blog.golang.org/go-maps-in-action "When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next." Also, "Since Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation."
josteink 12y ago
To play devils advocate here... There's nobody saying a map has to be a hash map. It could be any sort of map. Look at JavaScript. Those are just plain maps. Why should expecting sophisticated hashes for simple maps be the default?
- kevingadd 12y ago
  JS Object is actually an ordered map, because they failed to specify whether it was ordered or not early on, and we ended up stuck with the particular map implementation IE used (there are now lots of applications out there that depend on getting back k/v pairs in the order they were added).
  - bshimmin 12y ago
    In the ECMAScript language spec, at least as far back as 1999, it quite specifically does say "unordered".
    - magicalist 12y ago
      yes, but kevingadd was (almost certainly) talking about in practice. In fact, I vaguely recall reading that the V8 team originally wanted to abandon insertion-order enumeration for performance but couldn't because too much code broke on the web. It's not quite insertion order, though, which is one of the issues with just specifying it in ES6 as it's implemented. If you insert with a numeric key (or a string that's strictly a number), I believe the JS engines don't agree on the order in which the numeric key will be enumerated in relation to the alphanumeric ones (v8 and spidermonkey will put the numeric ones ahead of all the keys, sorted ascending, then do the rest in insertion order, for instance).
- zwegner 12y ago
  Another good example is C++, std::map is (usually) a red-black tree.
- blahedo 12y ago
  I'm not saying it has to be a hash map either; just that the author's post is consistent with plain old hashtable behaviour (i.e. the results are not iterated in insertion order, nor in natural order). By posting just a single example of a map iteration, the author has not demonstrated that the iteration order is "random" nor even that it changes each time through (though from other posts here, I gather that it does). Essentially, I'm not calling out the author's claim as unbelievable, I'm calling out the article for being unconvincing.
coldtea 12y ago
Hmm, seems like part of the artcile went over your head, especially the references to the intentional change of this behaviors from Go's designers. The story with regards to random traversal is about hiding an implementation detail the users should not rely on.

by blahedo 12y ago

dickeytk 12y ago

it is random, isn't it? https://code.google.com/p/go/source/detail?r=02c15930f43c https://code.google.com/p/go/source/detail?r=02c15930f43c

teraflop 12y ago
Well, sort of. The hash table stores elements in a semi-deterministic order, dependent only on the keys and a per-map hash seed. Every time you iterate over it, you start at a randomly-chosen point in the table and iterate sequentially. So although you can't rely on seeing elements in the same order on any particular iteration, the order itself is far from uniformly random.
- deleted 12y ago
  [deleted]

ahuth 12y ago

Here: http://blog.golang.org/go-maps-in-action http://blog.golang.org/go-maps-in-action "When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next." Also, "Since Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation."

josteink 12y ago

To play devils advocate here... There's nobody saying a map has to be a hash map. It could be any sort of map. Look at JavaScript. Those are just plain maps. Why should expecting sophisticated hashes for simple maps be the default?

kevingadd 12y ago
JS Object is actually an ordered map, because they failed to specify whether it was ordered or not early on, and we ended up stuck with the particular map implementation IE used (there are now lots of applications out there that depend on getting back k/v pairs in the order they were added).
- bshimmin 12y ago
  In the ECMAScript language spec, at least as far back as 1999, it quite specifically does say "unordered".
  - magicalist 12y ago
    yes, but kevingadd was (almost certainly) talking about in practice. In fact, I vaguely recall reading that the V8 team originally wanted to abandon insertion-order enumeration for performance but couldn't because too much code broke on the web. It's not quite insertion order, though, which is one of the issues with just specifying it in ES6 as it's implemented. If you insert with a numeric key (or a string that's strictly a number), I believe the JS engines don't agree on the order in which the numeric key will be enumerated in relation to the alphanumeric ones (v8 and spidermonkey will put the numeric ones ahead of all the keys, sorted ascending, then do the rest in insertion order, for instance).
zwegner 12y ago
Another good example is C++, std::map is (usually) a red-black tree.
blahedo 12y ago
I'm not saying it has to be a hash map either; just that the author's post is consistent with plain old hashtable behaviour (i.e. the results are not iterated in insertion order, nor in natural order). By posting just a single example of a map iteration, the author has not demonstrated that the iteration order is "random" nor even that it changes each time through (though from other posts here, I gather that it does). Essentially, I'm not calling out the author's claim as unbelievable, I'm calling out the article for being unconvincing.

coldtea 12y ago

Hmm, seems like part of the artcile went over your head, especially the references to the intentional change of this behaviors from Go's designers. The story with regards to random traversal is about hiding an implementation detail the users should not rely on.