Go 言語での map の実装についてのメモ
Published: 2023/4/4
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics
Go 言語における map の実装は、 map のオブジェクトそれ自体とは別に、 map 型情報データをランタイムに伝えることで実現されている。 (コンパイラがそれを関数呼出に埋め込むことで、伝えている。)
map 型情報は、
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type // internal type representing a hash bucket
hmap *_type // internal type representing a hmap
keysize uint8 // size of key slot
indirectkey bool // store ptr to key instead of key itself
valuesize uint8 // size of value slot
indirectvalue bool // store ptr to value instead of value itself
bucketsize uint16 // size of bucket
reflexivekey bool // true if k==k for all keys
needkeyupdate bool // true if we need to update key on overwrite
}
という構造体であり、キーと要素の型情報を持っている。
特に、 key
の _type
については、キーとしての equality check に利用されたりする。
Tags: go
関連記事
Go 言語の interface についてのメモ
2023/4/3