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

関連記事