Goブログ

Goマップの実践

Andrew Gerrand
2013年2月6日

はじめに

コンピュータサイエンスで最も有用なデータ構造の1つがハッシュテーブルです。さまざまな特性を持つ多くのハッシュテーブル実装が存在しますが、一般的に、高速な検索、追加、削除を提供します。Goはハッシュテーブルを実装する組み込みのマップ型を提供します。

宣言と初期化

Goのマップ型は次のようになります

map[KeyType]ValueType

ここで、KeyTypeは比較可能な任意の型（詳細は後述）であり、ValueTypeは別のマップを含む任意の型にすることができます。

この変数mは、文字列キーから整数値へのマップです

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"]

このステートメントでは、最初の値（i）に、キー"route"の下に格納された値が割り当てられます。そのキーが存在しない場合、iは値型のゼロ値（0）になります。2番目の値（ok）は、キーがマップに存在する場合はtrue、存在しない場合はfalseとなるboolです。

値を取得せずにキーをテストするには、最初の値の代わりにアンダースコアを使用します

_, 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であることを思い出してください）。この例では、Nodesの連結リストを走査し、その値を印刷します。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、nが存在しない場合はfalseになります。マップ内のnの存在をテストするために2値形式を使用する必要はありません。ゼロ値のデフォルトがそれを行います。

役立つゼロ値のもう1つの例は、スライスのマップです。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スライスを長さゼロのスライスとして扱うため、最後の2つの例は、誰もチーズやベーコンを好きでなくても（ありそうもないことですが）機能することに注意してください。

キー型

前述のように、マップキーは比較可能な任意の型にすることができます。言語仕様はこれを正確に定義していますが、要するに、比較可能な型は、ブール、数値、文字列、ポインタ、チャネル、インターフェース型、およびそれらの型のみを含む構造体または配列です。リストにないものとして、スライス、マップ、および関数があります。これらの型は==を使用して比較できず、マップキーとして使用することはできません。

文字列、整数、およびその他の基本型がマップキーとして使用できることは明らかですが、構造体キーは予想外かもしれません。構造体は、複数の次元でデータをキー付けするために使用できます。たとえば、このマップのマップは、国別のWebページヒットを集計するために使用できます

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

これは、stringから（stringからintへのマップ）へのマップです。外側のマップの各キーは、独自の内部マップを持つWebページへのパスです。各内部マップキーは、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"}]

並行性

マップは並行使用に対して安全ではありません。同時に読み書きするとどうなるかは定義されていません。並行して実行されるゴルーチンからマップを読み書きする必要がある場合は、アクセスを何らかの同期メカニズムによって仲介する必要があります。マップを保護する一般的な方法の1つは、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()

反復順序

範囲ループでマップを反復処理する場合、反復順序は指定されておらず、反復ごとに同じであるとは限りません。安定した反復順序が必要な場合は、その順序を指定する別のデータ構造を維持する必要があります。この例では、キー順に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])
}