Goで、mapをrangeでイテレーションすると、取り出す順番は実行ごとに異なる罠

#はじめに
タイトルどおりですが、気をつけましょうという話です。
不思議な現象だと思ったので簡単な記事にしました。

理由までは、わかってません。
ご存じの方は、教えて頂けると幸いです。

ソースを見ると乱数が使われているようです。
https://golang.org/src/runtime/hashmap.go?h=map#L231
詳しくはコメントを参照。

#実験環境
go version go1.4.2 darwin/amd64
(つまりMac OS Xです）

##実行コマンド
go run main.go

#実験

例えば、他の言語で言うsetみたいなのをしたかったとします。

main.go

package main

import (
	"fmt"
)

func main() {

	set := map[int] bool{}

	set[175] = true
	set[119] = true
	set[450] = true

	fmt.Println(set)

	//イテレーション1
	for key, _ := range set {
		fmt.Print(key)
		fmt.Print(" ")
	}
	fmt.Println()

	//イテレーション2
	for key, _ := range set {
		fmt.Print(key)
		fmt.Print(" ")
	}
	fmt.Println()
}

これで実行すると

結果1

map[175:true 119:true 450:true]
175 119 450 
175 119 450 

こんな感じですよね。
イテレーション1とイテレーション2は同じ はず
ですので。
mapも入れた順になってますね。
もう一度、実行してみましょう

結果2

map[450:true 175:true 119:true]
175 119 450 
119 450 175

あれ、今度はイテレーション1とイテレーション2で、 違う 結果になってますね。。
これはおかしいですね。。
（ちなみに、10回ほど実行しても変わらなかったこともあります。）

#別の言語だと

連想配列の取り出しは、一般に順不同であるというコメントも見受けられたので実験してみました。

(そもそも僕は連想配列の取り出しは、一般に順不同ということを知りませんでしたが）

連想配列とMapは、厳密に等価かどうかわかりませんが、とりあえず僕がさくっと書ける２つの言語で。

##Javaの場合

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        map.put(175, true);
        map.put(119, true);
        map.put(450, true);

        for (Map.Entry<Integer, Boolean> element : map.entrySet()) {
            System.out.print(element.getKey());
            System.out.print(" ");
        }
        System.out.println();

        for (Map.Entry<Integer, Boolean> element : map.entrySet()) {
            System.out.print(element.getKey());
            System.out.print(" ");
        }
        System.out.println();

    }

}

Javaの実行結果

119 175 450 
119 175 450 

（20回ほど実行しても同じ）

##Python2の場合

hoge = {175: True, 119: True, 450: True}

for k in hoge:
    print k,

print ""

for k in hoge:
    print k,
print ""

pythonの実行結果

450 119 175
450 119 175

（こちらも20回ほど実行しても同じ）

#まとめ

mapをrangeでイテレーションすると、実行するたびに異なる結果になりました。
こういうふうに使われる方は気をつけましょう。

Goでは乱択アルゴリズムが使われているようです。