title: Go: what determines the iteration order for map keys?
body: <p>The <a href="http://golang.org/doc/go_spec.html#RangeClause" rel="noreferrer">Go Programming Language Specification</a> says:</p>
  
  <blockquote>
    <p>3. The iteration order over maps is not specified. [...]</p>
  </blockquote>
  
  <p>That's to be expected since a map type can be implemented as a hash table, or as a search tree, or as some other data structure. But how is <code>map</code> actually implemented in Go?</p>
  
  <p>Put differently, what determines the iteration order of the keys in</p>
  
  <pre><code>for k, _ := range m { fmt.Println(k) }
  </code></pre>
  
  <p>I started wondering about this after I saw that a map with <code>string</code> keys apparently <em>do</em> have a certain iteration order. A program like</p>
  
  <pre><code>package main
  import ("fmt"; "time"; "rand")
  
  func main() {
      rand.Seed(time.Seconds())
      words := [...]string{"foo", "bar", "a", "b", "c", "hello", "world",
          "0", "1", "10", "100", "123"}
      stringMap := make(map[string]byte)
      for i := range rand.Perm(len(words)) {
          stringMap[words[i]] = byte(rand.Int())
      }
      fmt.Print("stringMap keys:")
      for k, _ := range stringMap { fmt.Print(" ", k) }
      fmt.Println()
  }
  </code></pre>
  
  <p>prints the following on my machine:</p>
  
  <pre><code>stringMap keys: a c b 100 hello foo bar 10 world 123 1 0
  </code></pre>
  
  <p><em>regardless</em> of the insertion order.</p>
  
  <p>The equivalent program with a <code>map[byte]byte</code> map also prints the keys in a shuffled order, but here the key order <em>depends</em> on the insertion order.</p>
  
  <p>How is all this implemented? Is the <code>map</code> specialized for integers and for strings?</p>