🦁
【Go】mapは取り出す順序を「意図的に」ランダム化していた

2026/05/03に公開
 はじめにGoのmapをrangeでループすると取り出す順序はランダムになります。
「ハッシュテーブルだから順序が不定なんでしょ」くらいに思っていました。
ですが調べてみると、Goは内部で「わざわざ」乱数を呼んで、能動的に順序をランダム化していました。
この挙動を初めてちゃんと認識したので、備忘録としてまとめます。
この記事におけるGoのバージョンは1.26.2です。
!間違いのないよう調べたつもりですが、記事の内容に誤りがあればコメントにて教えていただけますと幸いです。

 【Go】mapは取り出す順序を「意図的に」ランダム化しているまず前提として、Goの公式ドキュメントには次のように書かれています。
The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.
「mapへのイテレーションは順序を保証しない」ということです。
実際に試すと、たしかに順序は一定ではありません。
サンプルコードmain.go
package main

import "fmt"

func main() {
    m := map[string]int{
        "apple":  1,
        "banana": 2,
        "cherry": 3,
    }
    for k, v := range m {
        fmt.Println(k, v)
    }
}
実行結果~/repos/go-sample
» go run main.go
banana 2
cherry 3
apple 1

~/repos/go-sample
» go run main.go
banana 2
cherry 3
apple 1

~/repos/go-sample
» go run main.go
apple 1
banana 2
cherry 3

~/repos/go-sample
» go run main.go
cherry 3
apple 1
banana 2

~/repos/go-sample
» go run main.go
apple 1
banana 2
cherry 3

 ハッシュテーブルだけが理由じゃないここで僕が誤解していたのが、「ハッシュテーブルだから自然に順序がバラつくだけ」という理解です。
たしかにハッシュテーブルでは、メモリ上の物理的な並びは挿入順とは異なる順序になります。
ですが、それだけだと同じmapに対するfor rangeは毎回同じ順序になってしまいます。
ただ、Goの実装はそれだけに頼っていません。
for rangeでmapをループするたびに、明示的にランダムな開始位置を選んでいます。
「たまたま順序がばらつく」のではなく「意図的に順序をばらつかせている」のです。

 ソースコードで確認実際のGoのソースコードでも確認してみたいと思います（Go1.26.2時点）。
for rangeでmapをループするとき、mapIterStartが呼ばれ、そこからit.Init() → it.Next()という流れで処理が始まります。
src/runtime/map.go
// mapIterStart initializes the Iter struct used for ranging over maps and
// performs the first step of iteration. The Iter struct pointed to by 'it' is
// allocated on the stack by the compilers order pass or on the heap by
// reflect. Both need to have zeroed it since the struct contains pointers.
func mapIterStart(t *abi.MapType, m *maps.Map, it *maps.Iter) {
    if raceenabled && m != nil {
        callerpc := sys.GetCallerPC()
        racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(mapIterStart))
    }

    it.Init(t, m)
    it.Next()
}
そしてこのit.Initの中で順序をランダム化しています。
src/internal/runtime/maps/table.go
// Init initializes Iter for iteration.
func (it *Iter) Init(typ *abi.MapType, m *Map) {
    it.typ = typ

    if m == nil || m.used == 0 {
        return
    }

    dirIdx := 0
    var groupSmall groupReference
    if m.dirLen <= 0 {
        // Use dirIdx == -1 as sentinel for small maps.
        dirIdx = -1
        groupSmall.data = m.dirPtr
    }

    it.m = m
    it.entryOffset = rand() // ここでランダム化！
    it.dirOffset = rand()   // ここでランダム化！
    it.globalDepth = m.globalDepth
    it.dirIdx = dirIdx
    it.group = groupSmall
    it.clearSeq = m.clearSeq
}
rand()は乱数生成の関数で、毎回違う値を返します。
ここでランダム化される値はentryOffsetとdirOffsetの2つです。
それぞれが何を意味しているのか理解するには、mapの構造をざっくり把握する必要があります。

 mapの構造をざっくり確認Goのmapは内部的に次のような階層構造になっています。
ディレクトリ(テーブルの配列)
├── テーブル0
│   ├── グループ0: [スロット0, スロット1, ..., スロット7]
│   ├── グループ1: [スロット0, スロット1, ..., スロット7]
│   └── ...
├── テーブル1
│   ├── グループ0: [スロット0, スロット1, ..., スロット7]
│   └── ...
└── ...
「ディレクトリの中に複数のテーブルがあり、各テーブルは複数のグループを持ち、グループは8個のスロットでできている」という構造です。
スロット1つに("apple", 1)のようなキーと値のペアが1つ入ります。

 2つのオフセットがやっていることこの構造を踏まえてentryOffsetとdirOffsetの役割をまとめます。

entryOffset: グループ内で、どのスロットから始めるかをランダムに決める

dirOffset: ディレクトリ内で、どのテーブルから始めるかをランダムに決める
「本棚の何段目から読み始めるか？」と「その段の何冊目から読み始めるか？」の両方を、for rangeのたびにランダムに決めている、というイメージです。
ソースコードのコメントにも、2つを別々にランダム化してることが明記されていました。
src/internal/runtime/maps/table.go
  // Randomize iteration order by starting iteration at a random slot
  // offset. The offset into the directory uses a separate offset, as it
  // must adjust when the directory grows.
  entryOffset uint64
  dirOffset   uint64
この実装によって、ハッシュテーブル自体の順序不定に加えて、能動的に順序をバラつかせているのです。

 なぜ積極的なランダム化をするのか？mapの順序に依存したコードを早期に発見させることが目的です。
仕様で「不定」と定めるだけだと、実装が偶然同じ順序を返した場合に、mapの順序へ依存したコードが見過ごされてしまいます。
ランダム化せずハードウェアやハッシュテーブルの挙動に任せていたら、たまたま同じ順序で動いていたコードが、ハードウェアやGoのバージョンが変わった際に崩れかねません。
「ローカルでは動くのにCI環境では動かない」といった問題が起きやすくなるはずです。
実行のたびに意図的に順序を変えることで、「たまたま動いていただけ」のコードが目立つようになります。
Go1のリリースノートに「Iterating in maps」という専用のセクションがあり、まさにこの動機が書かれていました。
This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem.
「イテレーション順序に依存したコードは壊れやすくなるため、問題が起きる前に修正が可能」という趣旨でした。
リリースノートには、これに加えて「ハードウェアによって順序が違っていたためテストが脆く、ポータビリティに欠けていた」という背景も書かれていました。

 なぜ順序を保証する方針を選ばなかったか？積極的にランダム化するのではなく、逆に順序を固定するアプローチもあり得たかと思います。
この点については次のIssueで議論されていました。
https://github.com/golang/go/issues/54500
「順序を固定してくれ」という提案が出ていますが、不採用になっています。
順序を保証するとmapの内部実装の選択肢が狭まるからです。
Goチーム側で変更を加えるたび順序まで保証するのは負担が大きく、パフォーマンスの最適化も難しくなります。
変更容易性を保つために順序を保証しない方針となっていたのでした。

 まとめmapから取り出す順序が不定なのは、ハッシュテーブルの性質だけが理由ではなく、意図的な設計でした。
mapの内部実装で2つの乱数を使って意図的にランダム化させている
順序に依存したコードを早期発見しバグの温床となるのを防ぐのが目的
内部実装の変更容易性を保つため、順序を保証しない方針となっていた
順序が大事な場面ではfor rangeに頼らず、キーをスライスに取り出してsortで並べ替えてから扱いましょう。
サンプルコードmain.go
package main

import (
    "fmt"
    "sort"
)

func main() {
    m := map[string]int{
        "apple":  1,
        "banana": 2,
        "cherry": 3,
    }
    keys := make([]string, 0, len(m))
    for k := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys) // key をソートしてから出力
    for _, k := range keys {
        fmt.Println(k, m[k])
    }
}
あるいはGo 1.23以降であれば、slicesとmapsパッケージを使ってもう少し簡潔に書けます。
サンプルコードmain.go
package main

import (
    "fmt"
    "maps"
    "slices"
)

func main() {
    m := map[string]int{
        "apple":  1,
        "banana": 2,
        "cherry": 3,
    }
    for _, k := range slices.Sorted(maps.Keys(m)) {
        fmt.Println(k, m[k])
    }
}
この記事が僕と同じように「ハッシュテーブルだから順序が不定なんでしょ」と思っていた方の参考になれば幸いです。

 参考文献https://go.dev/doc/go1#iteration
https://go.dev/doc/go1.23#iterators
https://go.dev/blog/swisstable
https://github.com/golang/go/blob/go1.26.2/src/internal/runtime/maps/table.go#L25-L33
はじめに

【Go】mapは取り出す順序を「意図的に」ランダム化している

ハッシュテーブルだけが理由じゃない

ソースコードで確認

mapの構造をざっくり確認

2つのオフセットがやっていること

なぜ積極的なランダム化をするのか？

なぜ順序を保証する方針を選ばなかったか？

まとめ

参考文献

Discussion
