実践Goのマップ

Go maps in action by Andrew Gerrand

はじめに

コンピューターサイエンスにおいてもっとも有用なデータ構造の一つがハッシュテーブルです。 ハッシュテーブルの実装は多岐にわたり、それぞれ異なる性質を持ちますが、 概ね高速な検索、追加、削除を提供します。Goにはハッシュテーブルを実装した組み込みのマップ型があります。

宣言と初期化

Goのマップ型は次のような見た目をしています。

map[KeyType]ValueType

ここで KeyType には比較可能であれば、どんな型でも使えます（詳細は後述します）。 また ValueType は別のマップも含め、本当にどんな型でもかまいません。

次の変数 m は文字列のキーから int 値へのマップです。

var m map[string]int

マップ型はポインタやスライスと同様に参照型です。そのため上記の m の値は nil であり、 初期化されたマップを指していません。nilマップは読み込みに対しては空のマップのように振る舞いますが、 nilマップへの書き込みを試みるとランタイムパニックが発生します。これはやってはいけません。 マップを初期化するには、組み込みの make 関数を使います。

m = make(map[string]int)

make 関数はハッシュマップのデータ構造を確保・初期化し、それを指すマップの値を返します。 そのデータ構造の具体的な中身はランタイムの実装に依存しており、言語自体で規定されているものではありません。 この記事ではマップの実装ではなく、その 使い方 に焦点を当てます。

マップを扱う

Goはマップを扱うためのおなじみの構文を提供しています。次の文はキー "route" に値 66 を設定します。

m["route"] = 66

次の文はキー "route" に格納されている値を取得し、新しい変数iに代入します。

i := m["route"]

要求したキーが存在しない場合、値の型の ゼロ値 が返されます。 この例では値の型は int なので、ゼロ値は 0 です。

j := m["root"]
// j == 0

組み込みの len 関数はマップ内の要素数を返します。

n := len(m)

組み込みの delete 関数はマップからエントリを削除します。

delete(m, "route")

delete 関数は何も返しません。また指定したキーが存在しない場合は何もしません。

2つの値を使った代入は、キーの存在を確認します。

i, ok := m["route"]

この文では、1番目の値（ i ）にはキー "route" に格納されている値が代入されます。 そのキーが存在しない場合、 i には値の型のゼロ値（ 0 ）が入ります。 2番目の値（ ok ）は、キーがマップに存在すれば true 、存在しなければ false になる bool 値です。

値を取得せずにキーの存在だけを確認したい場合は、1番目の値の代わりにアンダースコアを使います。

_, ok := m["route"]

マップの中身を反復処理するには、 range キーワードを使います。

for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}

いくつかのデータでマップを初期化するには、マップリテラルを使います。

commits := map[string]int{
    "rsc": 3711,
    "r":   2138,
    "gri": 1908,
    "adg": 912,
}

同じ構文は空のマップを初期化する際にも使えます。これは make 関数を使うのと機能的に同一です。

m = map[string]int{}

ゼロ値を活用する

マップの取得がキーの存在しないときにゼロ値を返してくれるのは、便利なことがあります。

たとえば、真偽値のマップは集合のようなデータ構造として使えます （真偽値型のゼロ値は false であることを思い出してください）。 次の例は Node の連結リストを巡回してその値を出力します。 リスト内の循環を検出するために Node のポインタのマップを使っています。

type Node struct {
    Next  *Node
    Value interface{}
}
var first *Node

visited := make(map[*Node]bool)
for n := first; n != nil; n = n.Next {
    if visited[n] {
        fmt.Println("cycle detected")
        break
    }
    visited[n] = true
    fmt.Println(n.Value)
}

式 visited[n] は、 n を訪問済みなら true 、そうでなければ false になります。 マップ内に n が存在するかどうかを確認するために2つの値を使った形式を使う必要はありません。 ゼロ値のデフォルトの挙動がそれを代わりにやってくれます。

もう一つ、ゼロ値が役立つ例はスライスのマップです。 nilスライスへの追加は単に新しいスライスを確保するだけなので、スライスのマップへ値を追加するのは1行で済み、 キーが存在するかどうかを確認する必要はありません。 次の例では、スライス people に Person の値が格納されています。 それぞれの Person は Name と Likes のスライスを持っています。 この例では、それぞれの「好きなもの」をそれを好きな人々のスライスに関連付けるマップを作成します。

type Person struct {
    Name  string
    Likes []string
}
var people []*Person

likes := make(map[string][]*Person)
for _, p := range people {
    for _, l := range p.Likes {
        likes[l] = append(likes[l], p)
    }
}

チーズが好きな人々の一覧を出力するには次のようにします。

for _, p := range likes["cheese"] {
    fmt.Println(p.Name, "likes cheese.")
}

ベーコンが好きな人の数を出力するには次のようにします。

fmt.Println(len(likes["bacon"]), "people like bacon.")

range も len もnilスライスを長さ0のスライスとして扱うので、 たとえチーズやベーコンを好きな人が誰もいなかった（そんなことはまずないでしょうが）としても、 この2つの例はどちらも問題なく動作することに注意してください。

キーの型

先に触れたように、マップのキーには比較可能であれば、どんな型でも使えます。 言語仕様ではこれが厳密に定義されていますが、 簡単に言うと、比較可能な型は真偽値、数値、文字列、ポインタ、チャネル、インターフェース型、 そしてそれらの型のみを含む構造体や配列です。 このリストに明らかに含まれていないのは、スライス、マップ、関数です。 これらの型は == を使って比較できないため、マップのキーとしては使えません。

文字列や int 、その他の基本型がマップのキーとして使えるのは当然に思えますが、 構造体をキーにできることは意外かもしれません。 構造体は複数の次元にわたってデータにキーを付けるために使えます。 たとえば、次のマップのマップは、国別のウェブページのアクセス数を集計するために使えます。

hits := make(map[string]map[string]int)

これは、文字列から「 string から int へのマップ」へのマップです。 外側のマップの各キーはウェブページへのパスであり、それぞれが自分自身の内側のマップを持ちます。 内側のマップの各キーは2文字の国コードです。 次の式は、オーストラリアの人がドキュメントページを読み込んだ回数を取得します。

n := hits["/doc/"]["au"]

残念なことに、このアプローチはデータを追加する際に扱いにくくなります。 というのも、任意の外側のキーに対して、内側のマップが存在するかどうかを確認し、 必要であれば作成しなければならないからです。

func add(m map[string]map[string]int, path, country string) {
    mm, ok := m[path]
    if !ok {
        mm = make(map[string]int)
        m[path] = mm
    }
    mm[country]++
}
add(hits, "/doc/", "au")

一方、構造体をキーとする単一のマップを使う設計であれば、こうした複雑さはすべて解消されます。

type Key struct {
    Path, Country string
}
hits := make(map[Key]int)

ベトナムの人がホームページを訪れたとき、対応するカウンタをインクリメント（そして必要なら作成）するのは1行で済みます。

hits[Key{"/", "vn"}]++

同様に、スイスの人が仕様書を何人読んだかを調べるのも簡単です。

n := hits[Key{"/ref/spec", "ch"}]

並行性

マップは並行使用に対して安全ではありません。マップに対して同時に読み書きした場合に何が起こるかは定義されていません。 複数の実行中のゴルーチンからマップへの読み書きを行う必要がある場合は、 何らかの同期機構によってアクセスを調停しなければなりません。 マップを保護する一般的な方法の一つはsync.RWMutexを使うことです。

次の文は、マップと埋め込みの sync.RWMutex を含む無名構造体である counter 変数を宣言します。

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

カウンタから読み込むには、読み込みロックを取得します。

counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)

カウンタに書き込むには、書き込みロックを取得します。

counter.Lock()
counter.m["some_key"]++
counter.Unlock()

反復処理の順序

range ループを使ってマップを反復処理するとき、反復処理の順序は規定されておらず、 反復のたびに同じ順序になる保証もありません。 反復処理の順序を安定させる必要がある場合は、その順序を指定する別のデータ構造を維持しなければなりません。 次の例では、キーのソート済みの別スライスを使って map[int]string をキー順に出力します。

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}

By Andrew Gerrand