Loading...
墨滴

楼仔

2021/05/04  阅读:18  主题:默认主题

Go系列教程3 - 字典

基本用法

字典属于引用类型,初始化方式主要有2种,分别为:

m1 := make(map[string]int)
m2 := map[string]int {
    "lvmenglou"32,
    "litinajie"28,
}

字典是被设计成“not addressable”,所以不能直接修改value成员,如果需要修改value成员,需要对元素整体替换:

type user struct {
    name string
    age byte
}
m := map[int]user {
    1: {"lvmenglou"32}
}
m[1].age += 1 // 错误:cannot assign to m[1].age

不能对nil字典进行写操作,否则会触发panic,但是可以读。

var m map[string]int
m["a"] = 1 // panic: assignment to entry in nil map

nil与空字典,这个需要注意:

var m1 map[string]int  // nil字典
m2 := map[string]int{} // 空字典,不等于nil

map属于非线程安全,如果多个线程同时对一个map进行读、写、删除操作,会触发panic,可以使用支持线程安全的sync.Map。

内存模型

先看一下map的数据结构:

type hmap struct {
    count     int 
    B         uint8  // bucket的数量是2^B, 最多可以放 loadFactor * 2^B 个元素,再多就要 hashGrow 了
    hash0     uint32 // hash seed
    buckets    unsafe.Pointer //2^B 大小的数组,如果 count == 0 的话,可能是 nil
    oldbuckets unsafe.Pointer // 扩容的时候,buckets 长度会是 oldbuckets 的两倍,只有在 growing 时候为空。
    // 其它省略...
}
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

B是map的bmap数组长度的对数,每个bmap里面存储了kv对,buckets是一个指针,指向实际存储的bmap数组的首地址,存储结构如下图:

每个bmap里面最多存储 8 个key,下图是bmap的内存模型,HOB Hash 指的就是top hash字段,每个 bucket 设计成最多只能放 8个key-value对,如果有第9个key-value落入当前的bucket,那就需要再构建一个bucket ,通过overflow指针连接起来(可以查看上图)。

查找数据

key经过哈希计算后得到哈希值,哈希值是64个bit 位(针对64位机),假如一个 key 经过哈希函数计算后,得到的哈希结果是:

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

其中最后5位是01010,值为10,表示10号桶。最前面8位10010111,值是151,用来在bmap中找数据用的,详见下图:

扩容缩容

一个map最多只能装8*2^B个数据,当数据量快满时,为了减少查询Hash冲突,就需要进行扩容。当bucket数量过多,然后数据又非常少时,就需要进行缩容(之前情况一般出现在数据大量删除的情况)。判断需要扩容和缩容的临界值,需要引入“装载因子”,感兴趣的同学可以自行百度。 当进行扩容时,比如B=5扩容到B=6,最低位需要扩到6位,然后重新Hash,找到在[]bmap对应的hash值,最高位不变。缩容的话,就是相反的方式。(因为最低位的第6位是0或者1,所以第6位为0的数据,因为值不变,所以不会重新进行Hash,第6位为1的数据,需要被Hash到扩容后的桶中)

为了更好举例,扩容前B=2,共有4个bmap,示例图如下:

假设overflow太多,触发了等量扩容,需要将数据变得更紧凑,操作如下:

假设针对上面情况,触发了2倍扩容,将B=2扩容到B=3,操作如下:

迭代遍历

本来map的遍历过程比较简单:遍历所有的bucket以及它后面挂的overflow bucket,然后挨个遍历 bucket中的所有 cell。每个bucket中包含8个cell,从有key的cell中取出 key和value,完成遍历。但是遍历如果发生在扩容的过程中,就会涉及到遍历新老 bucket 的过程。

所以在遍历过成功,如果map在库容,需要对新旧数据同时进行遍历,下面是扩容过程示例,图中进行二倍扩容后,oldbuckets中的1已经全部搬迁到了buckets中,所以遍历时,需要对oldbuckets和buckets都进行遍历。

总结

对于map的使用,大家肯定都会,所以基础的知识讲解的不多,主要是对map的底层结构进行了详细的讲解,正所谓知其然,必知其所以然!对于map的底层结构设计,感觉有些意思,特别是对于它的hash方式(取前N位和后M位),再结合它的扩容和缩容,其实可以从中提炼一些共性的东西。然后对于Rehash,这个和Redis的Rehash原因一样,这块应该是业内的通用设计方法,感兴趣的同学可以看看redis的字典结构和它rehash的方法。

楼仔

2021/05/04  阅读:18  主题:默认主题

作者介绍

楼仔