Go: for rangeにおけるmapのイテレーション順序について

概要

Goにおけるfor rangeでmapをループさせる際のイテレーション順序について整理します。

Goにおいて、for rangeでmapの要素をループさせる際、イテレーションの順序は決まっていません。
これはGo言語の仕様で定められており、ループ順序を前提としたコードを書かないために定められています。

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. If you require a stable iteration order you must maintain a separate data structure that specifies that order.

go.dev

この順序が実際にどう決まっているかについて、Goのランタイムでどういう実装になっているかを整理します。

前提 - Go v1.22.4

for rangeにおける mapのループの例

ここでは簡単に、mapをfor rangeによってループさせる例を示します。

package main

import "fmt"

func main() {

    m := map[string]int{
        "a": 100,
        "b": 200,
        "c": 300,
        "d": 400,
        "e": 500,
    }

    for k, v := range m {
        fmt.Printf("%s : %d \n", k, v)
    }
}

mapの要素をイテレートして、そのキーと値を表示させます。

これを実行すると、実行するごとに要素の順番が変わっていることを確認できます。

$ go run main.go
b : 200 
c : 300 
d : 400 
e : 500 
a : 100 

$ go run main.go
a : 100 
b : 200 
c : 300 
d : 400 
e : 500 

$ go run main.go
c : 300 
d : 400 
e : 500 
a : 100 
b : 200 

$ go run main.go
c : 300 
d : 400 
e : 500 
a : 100 
b : 200 

mapのイテレーションで順序が保証されていない理由

この理由については、簡単にいうとGoの古いバージョンからの互換性を保つためのものとなります。
古いバージョンでは、もともとmapのイテレーション順について仕様で定義されていませんでした。そのため実行するハードウェアプラットフォームによって異なっていたようです。
これにより、mapをイテレーションするテストでは実行する環境でテスト結果が異なってしまい、環境によってテストが成功したりしなかったりするという課題がありました。

go.dev

Goのv1系では、for rangeによるmapのイテレーション順は不定であると定義されました。
そのため、順序を想定したmapのfor rangeを扱っている箇所は修正が必要です。

Goランタイムによる mapのイテレーション時の処理について

次に、実際にGoランタイムではmapのイテレーションの順番をどのように決めているかについて整理します。

ランタイムにおけるmapに関する実装は src/runtime/map.go で確認できます。

mapのデータ構造について

Goにおけるmapのデータ構造について説明します。

Goにおいては、mapはハッシュテーブルと同義です。map内にバケットが存在し、そのデータはバケットの配列に格納されます。
各バケットは最大8つのキー・バリューのペアを含むことができます。 そのハッシュ値の下位のビットは、どのバケットを選択するかを決めるのに利用されます。
また、上位のビットは単一のバケット内のどのエントリかを決めるのに利用されます。

もしあるバケットで8より多い数のデータが追加された場合、追加のバケットを連結し、そこに格納されます。

ハッシュテーブルを増やす必要がある際、Goランタイムはその時点でのバケット数を2倍にし、新しい配列を持ったバケットを追加します。

mapのイテレータ用の構造体について

mapをイテレーションする際に使う hiter という構造体も用意されています。

go/src/runtime/map.go at ace5bb40d027b718b67556afcd31bf54cff050ab · golang/go · GitHub

// A hash iteration structure.
// If you modify hiter, also change cmd/compile/internal/reflectdata/reflect.go
// and reflect/value.go to match the layout of this structure.
type hiter struct {
    key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
    elem        unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
    t           *maptype
    h           *hmap
    buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
    bptr        *bmap          // current bucket
    overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
    oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
    startBucket uintptr        // bucket iteration started at
    offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
    wrapped     bool           // already wrapped around from end of bucket array to beginning
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}

この中で、 hiter.startBucket がイテレーションの開始するバケットを選択するものになります。
イテレーションの初期化処理において、この値を設定する箇所があります。

mapのイテレーションの初期化

mapのイテレーションの初期化処理は、 mapiterinit という関数で実装されています。

go/src/runtime/map.go at ace5bb40d027b718b67556afcd31bf54cff050ab · golang/go · GitHub

この初期化処理の中で、map内のどのバケットから処理をするかを決めていますが、この際に乱数をもとにバケットを選択しています。

...
    // decide where to start
    r := uintptr(rand())
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))
...

Goにおいて for range でmapのイテレーションの順番が不定となるのは、この処理によるものであることがわかります。

おわりに

以上となります。 この記事では mapについての概要の説明を行いました。
また、for rangeにおけるmapのイテレーションの順序は仕様で不定となっていて、Goランタイムの実装を確認し、実際にイテレーションの初期化処理で開始位置がランダムになっていることを確認できました。

今回は取り上げませんでしたが、Goランタイムの実装は非常に興味深いため、別の記事でも気になる箇所について取り上ようと思います。