jasper的技术小窝

关注DevOps、运维监控、Python、Golang、开源、大数据、web开发、互联网

深入Golang之map

作者:jasper | 分类:Golang | 标签:   | 阅读 208 次 | 发布:2017-09-16 10 p.m.

现在我们接着来看一看Golang中的map,map具有O(1)的存取速度,所以十分高效。同Java语言一样,Golang的map也是hash结构的,代码在“runtime/hashmap.go”中,下面让我们来细细剖析。

map的数据结构

map中的header:

type hmap struct {
    count     int
    flags     uint8
    B         uint8
    noverflow uint16
    hash0     uint32

    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr       

    extra *mapextra
}

其中buckets是一个有2^B个Buckets的一个数组,当count为0的时候,buckets可以为nil;其中第一个Bucket是用一段连续的内存空间,而后面的Bucket的空间是使用mallocgc分配的。

其中还有一个oldbuckets是在hash表扩容的时候才会用到,上面也说了buckets大小为2^8,也即是按照2的倍数来增长,正常情况下,oldbuckets为空,在扩容的过程中,oldbuckets会暂时存放之前buckets中的数据。

bucket的数据结构为:

type bmap struct {
    tophash [bucketCnt]uint8
}

其中bucketCnt是常量8,意味着每个bucket最多存放8个键值对,如果多于8个,就会创建一个新的bucket,并和之前的bucket链起来。

在tophash里面存放的这8个键值对的key的高8位,这个可以作为一个主键,用作查找时候的匹配。

盗图来看一看其存储结构:

可以看到,bucket中键值的放置顺序,是key放在一起,而value放在一起,这是考虑到减少内存对齐的内存消耗。

map中的查找过程

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 忽略部分代码

    // 得到key的hash值
    alg := t.key.alg
    hash := alg.hash(key, uintptr(h.hash0))
    m := uintptr(1)<<h.B - 1
    // hash值对m取余数得到对应的bucket
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

    // 如果老的bucket还没有迁移,则在老的bucket里面找
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }

    // 获取hash值得高8位
    top := uint8(hash >> (sys.PtrSize*8 - 8))
    if top < minTopHash {
        top += minTopHash
    }
    for {
        for i := uintptr(0); i < bucketCnt; i++ {

           //如果高8位不一样就找下一个
            if b.tophash[i] != top {
                continue
            }

            // 找到之后获取到对应的key
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }

            // 如果key相等,就取出value
            if alg.equal(key, k) {
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v
            }
        }

        // 如果当前bucket没有找到,则找bucket链的下一个bucket
        b = b.overflow(t)
        if b == nil {
            return unsafe.Pointer(&zeroVal[0])
        }
    }
}

过程已经在代码里面注释出来了,需要注意得是,由于bucket的数量是2的倍数,所有在对hash取余数的时候,并不是hash mod len(buckets)而是等价的hash & len(buckets);另外提醒,这里的高八位是用来加速key的比较的,并不是key的offset。

map的插入/更新过程

插入和更新这里放在一起说;其实和查找过程一样,都是查找到对应的key,如果没有存在就多了一个allocate的动作。

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

// 已经省略部分代码,只展示插入部分的代码
// 没有从mapping里面找到key,如果已经达到了load factor的最大值,那我们就继续开始扩容
if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again 
    }

    if inserti == nil {
        // 当然的burrent满了的话,就allocate一个新的
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // 在插入的位置,存储键值
    if t.indirectkey {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectvalue {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(val) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++
}

注意在扩容的过程中,oldbucket是被冻结的,但是查找的时候回去找,如果在oldbucket中找到了这个key,那么会在迁移完之后,给其加一个标记。

map的删除过程

前面的查找过程和之前的类似,就不再多说了,我们就来看看找到之后会做些什么。

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {

    // 找到之后分别释放key和value的内存
    if t.indirectkey {
        *(*unsafe.Pointer)(k) = nil
    } else {
        typedmemclr(t.key, k)
    }
    v := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*uintptr(t.keysize) + i*uintptr(t.valuesize))
    if t.indirectvalue {
        *(*unsafe.Pointer)(v) = nil
    } else {
        typedmemclr(t.elem, v)
    }

    // 把对应的tophash里面的置为空
    b.tophash[i] = empty
    h.count--
}

map的增量扩容

其实在上面的map的插入的时候也已经提到了,插入的时候会看下当前和load factor的比较,来决定是否会扩容,如果之前为2^B,那么扩容之后就是2^(B+1),每次扩容都是之前的两倍。扩容之后需要重新计算一下每一项在hash表中的新位置,这个工作其实golang并没有扩容之后就完成,而是分摊到每次的插入和删除之中,所以使用的是增量扩容。

这样做的目的可以缩短时间,把扩容总的时间分摊到每一次的hash操作之中。就是上面说的oldbucket存在的意义,新表为原来的两倍,然后需要做数据迁移,把数据迁移到新的之上;这个过程就是逐渐来完成的,迁移完成之后再把oldbucket释放掉。

所有说这是一个空间换时间的设计。

判断是否要扩容的条件是:

func overLoadFactor(count int64, B uint8) bool {
    // TODO: rewrite to use integer math and comparison?
    return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<<B))
}

即需要满足count数大于8(这个当然了,不然一个bucket就够了),并且count数大于等于可容纳的个数时,就触发一次扩容,其中这个平衡点有loadFactor来决定,loadFactor在这里是一个常量6.5,那么这个值是怎么得来的呢,只能说是一个测试结果:

  loadFactor    %overflow  bytes/entry     hitprobe    missprobe
        4.00         2.13        20.77         3.00         4.00
        4.50         4.05        17.30         3.25         4.50
        5.00         6.85        14.77         3.50         5.00
        5.50        10.55        12.94         3.75         5.50
        6.00        15.27        11.67         4.00         6.00
        6.50        20.90        10.79         4.25         6.50
        7.00        27.14        10.15         4.50         7.00
        7.50        34.03         9.73         4.75         7.50
        8.00        41.10         9.40         5.00         8.00

%overflow 溢出率,平均一个bucket有多少个kv的时候会溢出
bytes/entry 平均存一个kv需要额外存储多少字节的数据
hitprobe 找到一个存在的key平均需要找几下
missprobe 找到一个不存在的key平均需要找几下

可以看到这里采用了一个中间值6.5,来平衡。

例子

同样地,在Golang中的map似乎也是实现了一种类似于”引用“类型的功能,这个和前一篇的slice一样的,例如:

func changeMap(mp map[string]int) {
    mp["d"] = 4
    mp["a"] = 100
    fmt.Printf("changeMap func %p\n", mp)
}
func main() {
    var mp = map[string]int{"a": 1, "b": 2, "c": 3}
    fmt.Printf("%p\n", &mp)
    changeMap(mp)
    fmt.Println(mp)
}

运行结果:

0xc42000c028
changeMap func 0xc420014180
map[b:2 c:3 d:4 a:100]

顺序请忽略啊,map是无序的。可以看到参数传递后的确是修改了参数的值。但是其实地址是不一样的,只是因为map的数据结构的关系,达到了”引用“类型一样的效果而已。具体就是上面说的map结果是实际存的是一个指向底层bucket数组的指针。

总结

golang的map总体上来说,性能不错,典型的空间换时间,访问时,只访问高8位来加速;扩增时,靠插入来均摊时间,总体上来说是个高效的hashmap。


转载请注明出处:http://www.opscoder.info/goalng_map.html

【上一篇】 深入Golang之slice
【下一篇】 深入Golang之interface
其他分类: