はじめに
Go の map について調べたことのメモ書きです。
実装
このあたりのようです。
// This file contains the implementation of Go's map type. // // A map is just a hash table. The data is arranged // into an array of buckets. Each bucket contains up to // 8 key/elem pairs. The low-order bits of the hash are // used to select a bucket. Each bucket contains a few // high-order bits of each hash to distinguish the entries // within a single bucket. // // If more than 8 keys hash to a bucket, we chain on // extra buckets. // // When the hashtable grows, we allocate a new array // of buckets twice as big. Buckets are incrementally // copied from the old bucket array to the new bucket array. // // Map iterators walk through the array of buckets and // return the keys in walk order (bucket #, then overflow // chain order, then bucket index). To maintain iteration // semantics, we never move keys within their bucket (if // we did, keys might be returned 0 or 2 times). When // growing the table, iterators remain iterating through the // old table and must check the new table if the bucket // they are iterating through has been moved ("evacuated") // to the new table.
冒頭コメントを見ると以下のようなことが書かれてます。
- マップは単なるハッシュテーブルである
- データはバケット(データの入れ物)の配列として配置され、各バケットには、最大 8 つのキー/要素のペアが含まれる
- ハッシュの下位ビットはバケットの選択に使用され、各ハッシュの上位ビットは単一のバケット内のエントリを区別するために使用される
- 8 個を超えるキーがバケットにハッシュされる場合は、追加のバケットを連鎖する
map の宣言・初期化
以下のようにすると、変数 m は文字列キー, intの値を持つ map になりますが、この m は nil となるようで、書き込み時にエラーが発生します。
var m map[string]int
例えば以下のようにしてみます。
package main import "fmt" func main() { var m map[string]int fmt.Printf("%p %T %v\n", m, m, m) m["foo"] = 42 fmt.Println(m) }
実行すると以下のように panic が発生します。
% go run main.go
0x0 map[string]int map[]
panic: assignment to entry in nil map
goroutine 1 [running]:
main.main()
/path/to/main.go:8 +0x2e
exit status 2
fmt.Printf の出力で 0x0 map[string]int map[] となっていますが、 一番左側に16進数で出力されているのはポインタの値で, 0x0 となっておりメモリが確保されていないようで、このことからメモリ上に要素追加に必要な場所が確保されていないためのようです。
次に、組み込み関数 make を使って map を宣言します。 この時はコンパイル時に makemap 関数が呼び出されるようですがこのあたりの仕組みはまだ詳しく理解できてません
m := make(map[string]int)
以下のようにして実行してみます。
package main import "fmt" func main() { m := make(map[string]int) fmt.Printf("%p %T %v\n", m, m, m) m["foo"] = 42 fmt.Println(m) }
正常に実行されました。
% go run main.go 0xc00007c0c0 map[string]int map[] map[foo:42]
fmt.Printf の出力で 0xc00007c0c0 map[string]int map[] となっており、 一番左側に16進数で出力されているのはポインタの値で, 0xc00007c0c0 となっておりメモリが確保されているようでした。
makemap 関数を見てみます。
// makemap implements Go map creation for make(map[k]v, hint). // If the compiler has determined that the map or the first bucket // can be created on the stack, h and/or bucket may be non-nil. // If h != nil, the map can be created directly in h. // If h.buckets != nil, bucket pointed to can be used as the first bucket. func makemap(t *maptype, hint int, h *hmap) *hmap { : }
makemap() の詳しい実装は理解できてませんが、以下のような形式のデータが返されるようです。
// A header for a Go map. type hmap struct { // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go. // Make sure this stays in sync with the compiler's definition. count int // # live cells == size of map. Must be first (used by len() builtin) flags uint8 B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details hash0 uint32 // hash seed buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) extra *mapextra // optional fields }
