数据结构

map实现的两个关键数据结构

hmap 定义了map的结构
bmap 定义了hmap.buckets中每个bucket的结构，bmap的结构比较特殊，详见下面的说明

// map 数据结构
type hmap struct {
    count     int // 元素的个数, len() 的值
    flags     uint8
    B         uint8  // bucket个数为：2^B；可以保存的元素个数： 填充因子(默认6.5) * 2^B 
    noverflow uint16 // 溢出桶数量
    hash0     uint32 // 哈希因子

    buckets    unsafe.Pointer // Buckets数组，大小为 2^B 
    oldbuckets unsafe.Pointer // 前面的Buckets，在增长时非nil
    nevacuate  uintptr        // 迁移状态，进度

    extra *mapextra // optional fields
}

// bucket 数据结构
type bmap struct {
    tophash [bucketCnt]uint8 // bucketCnt 是常量=8，一个bucket最多存储8个key/value对
    // 后面紧跟着8个key
    // 再后面是8个value
    // 最后是overflow的指针
}

也就是说每个bucket(bmap)的结构并不是bmap字面定义的那么简单，其实是由四个部分组成的。
这样组织比k/v, k/v...的形式复杂，
好处就是节约内存，比如key的类型为string，value的类型uint8, 在考虑到字节对齐的时候，如果使用k/v的格式存储会浪费内存，使用8个key/8个value的格式会更紧凑。
为了更好的理解bmap的动态结构，使用下面的结构图进行说明, keys为紧挨着的8个key，values为紧挨着的8个values

bmap结构

bucket结构实例

var m map[string]string
为了更加方便的理解bmap结构，将其构造为如下的形式，实际中与其类似，但直接使用的指针偏移来实现的

type bmapTest struct {
    tophash  [8]uint8
    keys     [8]string // map key的数据类型为string
    values   [8]string // map value的数据类型为string
    overflow unsafe.Pointer
}
func main() {
    b := bmapTest{}
    // 计算每个bucket占用的内存大小 
    fmt.Println(unsafe.Sizeof(b)) // out: 272
}

map 创建

创建map时主要使用如下函数

func makemap_small() *hmap 
func makemap(t *maptype, hint int, h *hmap) *hmap 
func makemap64(t *maptype, hint int64, h *hmap) *hmap // hint类型为int64， 实质还是调用的 makemap

当创建map时不指定hint大小，如下面所示的m1。那么调用makemap_small来进行创建
当指定了hint(代表初始化时可以保存的元素的个数)的大小的时候，若hint<=8, 使用makemap_small进行创建map，否则使用makemap创建map

    m1 := make(map[string]string)
    m2 := make(map[string]string, hint)

makemap与makemap_small差异在于buckets的初始化上

makemap_small 源码分析

主要是创建hmap结构并初始化hash因子就结束了，并没有初始化buckets，makemap的要较其复杂一些，下面将结合具体的例子进行说明

func makemap_small() *hmap {
    h := new(hmap) 
    h.hash0 = fastrand()
    return h
}

makemap源码分析- make(map[string]string, 10)

下面进行源码分析(64位cpu中指针占8个字节)，并对关键的变量值以及步骤进行说明。
从上面的分析可以知道，创建 make(map[string]string, 10) ，由于hint=10, 大于8，因此将使用makemap来实现。

makemap

//  hint=10，可以容纳hint个元素
func makemap(t *maptype, hint int, h *hmap) *hmap {
    if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
        hint = 0
    } 

    // initialize Hmap
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand() // hash因子

    // 确定B的大小，每个桶(不含溢出桶)可以有8个k/v对，hmap中含有 1<< B 个桶，具体见overLoadFactor分析
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B // 此时 B=1

    // h.B = 1 创建buckets
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)// 分配内存
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

overLoadFactor 实现
在确定hmap.B的值的时候，需要调用此函数。当调用make(map[string]string, 10)时，count=10

const (
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits // =8

    loadFactorNum = 13
    loadFactorDen = 2
)    

// 如果 count > 8 && count > 13 * ( (1<<B) / 2 ), 返回true
// 1 << B bucket个数, 负载因子为： 13/2=6.5
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

makeBucketArray
确定桶的个数后，进行内存的分配，内存的分配采用array连续内存的分配方式

// b=1
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b) // base = 1 << 1 = 2
    nbuckets := base       // nbuckets = 2

    if b >= 4 {
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

    if dirtyalloc == nil {
        // 申请内存，结构为一个数组，每个元素为 bucket， 个数为 1<<B = 2个，会申请连续内存大小为 bucket.size*nbuckets = 2*272 = 544个字节
        // 这里说明一下 bucket.size为什么等于272？ bmap的结构由四个部分组成，tophash，8个key，8个value，1一个指针。
        // tophash是一个数组，数组的大小为8，类型为uint8, uint8占一个字节，总计字节 8*1 = 8
        // key,value的数据类型都是string类型,string类型占16个字节，总计字节 8*16 + 8*16 = 256
        // 指针在64位cpu上占8个字节。因此总和为 8 + 256 + 8 = 272 个字节
        buckets = newarray(t.bucket, int(nbuckets)) 
    } else {
        buckets = dirtyalloc
        size := t.bucket.size * nbuckets
        if t.bucket.kind&kindNoPointers == 0 {
            memclrHasPointers(buckets, size)
        } else {
            memclrNoHeapPointers(buckets, size)
        }
    }

    if base != nbuckets {
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets))
    }
    return buckets, nextOverflow
}

至此map的创建完成，为了更加理解map创建后，内存分配的结构情况，见下图所示

hmap数据结构

总结

上面的实例只是针对一个map的创建实例进行的说明，当hint传入的值大小不同的时候，在创建map的时候会进行不同的初始化操作，可以根据传入的值结合代码进行具体的分析。基本分如下情况：

当使用 make(map[string]string) 创建map的时候，只是创建了hmap结构，并没有初始化buckets
当使用 make(map[string]string, hint)创建map的时候，依据传入的map的hint的值的不同会进行buckets的初始化操作

go map源码分析(一) - 创建map