<p>When repeating the same binary over the same input, my program produces different results. Are maps/hashes not predictable, not even with the same input? Not that I mind, but I was puzzled when I ran into it. Google doesn't turn up much beyond conjecture.</p>
<hr/>**评论：**<br/><br/>tv64738: <pre><p>1) map iteration is randomized</p>
<p>2) <code>select</code> is randomized</p>
<p>3) timing of goroutines is inherently unpredictable</p>
<p><a href="https://golang.org/ref/spec" rel="nofollow">https://golang.org/ref/spec</a></p>
<p>None of this should really surprise you.</p></pre>sin2pifx: <pre><p>Aha, I forgot to add that there is no select, nor a goroutine. It's plain and single-threaded.</p>
<p>About map iteration, the spec says: "The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next." I never would have interpreted that to mean: on every run it'll be different.</p>
<p>BTW: Why shouldn't 1. surprise me? I know you can't rely on the order, but do other languages randomize map iteration?</p></pre>xiegeo: <pre><blockquote>
<p>"The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next."</p>
</blockquote>
<p>This is a property of how hash maps work. The go implementation additionally adds more randomness to help discover potential bugs in code that mistakenly assume deterministic order.</p></pre>sin2pifx: <pre><p>I wasn't aware it was randomized per run. It surprised me.</p></pre>xiegeo: <pre><p>Yes, it surprised me too when I first encountered it. It was a good surprise. I appreciate how well the Go team thought it out. <a href="https://www.youtube.com/watch?v=Tl7mi9QmLns" rel="nofollow">https://www.youtube.com/watch?v=Tl7mi9QmLns</a></p></pre>velco: <pre><p>No, non-determinism is not an inherent property of hash maps.
Go just uses an effectively different hash function on each run.</p></pre>xiegeo: <pre><p>And a different starting point for each iteration. </p>
<p>Not all hash maps has to be non-deterministic, but any code that handles iteration over a hash maps should not assume any ordering. (Personally I have no idea if the universes is deterministic or not, but I know there is no guaranteed prediction)</p>
<p>Considering a hash map without randomized hash or randomized iterator:</p>
<ul>
<li><p>Does insertion order change iteration order? Most times not, unless the insertions fit in the same basket.</p></li>
<li><p>Does insertion change order of other items? Most times not, unless the insertion cause the map to expand the number of baskets. Or a few items might change order depending on <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing" rel="nofollow">implementation</a>.</p></li>
<li><p>Does a lookup change ordering? Depending on implementation, often used items could be moved the front of a basket for faster access.</p></li>
<li><p>Does upgrading libraries or migrating architectures change ordering? Maybe and probably.</p></li>
</ul>
<p>An assumption on ordering could cause code that pass tests with hard to find bugs in production. </p></pre>tv64738: <pre><p>Randomizing hash table iteration order is a best practice across all programming languages; it prevents code relying on things not guaranteed, and goes hand-in-hand with preventing denial of service attacks.</p>
<p><a href="http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html" rel="nofollow">http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html</a></p></pre>sin2pifx: <pre><p>I'm fairly sure many other languages don't have per run randomization. Some state you cannot rely on a specific order, although e.g. Javascript's Map guarantees iteration in order of adding.</p></pre>danredux: <pre><p>It's actually really cool. Other languages just say "Don't rely on the order, it may change"... Go just goes ahead and always makes it change. Documentation through execution is a great last-resort!</p></pre>perfectstar04: <pre><p>FWIW, Python had had, intentionally, random ordering until 3.6. There's a lot of good discussion in <a href="/r/python" rel="nofollow">/r/python</a> on the topic.</p></pre>tv64738: <pre><p>If there's no per-run randomization in the hash function for a hash table, that means an attacker can figure out the collisions from timings and still launch an algorithmic DoS on you. General purpose hash tables need to seed their hash function with something that changes, and it should also change at runtime (e.g. as part of growing).</p>
<p>If you do implement random seed refreshing at grow time, now there's no stable iteration order anymore -- so you might as well actively randomize it, to prevent programmers from relying on it.</p></pre>comrade_donkey: <pre><p>It's not a question of whether any other languages do it or not (they probably do). It's a concious design decision that makes it clear that there is no ordering, even when executing the same self-contained program over and over again. This enables efficient map growth, among other simplifications.</p></pre>yocodaco: <pre><p>Map iteration is undefined!</p></pre>cloudfreak: <pre><p>elements in maps are randomized</p></pre>velco: <pre><p>Go map iteration is not-deterministic as a measure to prevent DDOS attacks via crafted input sequences, causing excessive number of collisions.</p></pre>
