hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

go map数据结构和源码详解

2019-11-18杂谈搜奇网18°c
A+ A-

目次

  • 1. 媒介
  • 2. go map的数据构造
    • 2.1 中心结体体
    • 2.2 数据构造图
  • 3. go map的经常运用操纵
    • 3.1 建立
    • 3.2 插进去或更新
    • 3.3 删除
    • 3.4 查找
    • 3.5 range迭代
      • 3.5.1 初始化迭代器mapiterinit()
      • 3.5.2 迭代历程mapiternext()
  • 4. go map的扩容缩容
    • 4.1 扩容缩容的基本道理
    • 4.2 为何叫“伪缩容”?怎样完成“真缩容”?
  • 5 Q&A症结知识点
    • 5.1 基本道理
    • 5.2 时候复杂度和空间复杂度剖析

1. 媒介

本文以go1.12.5版本剖析,map相干的源码在runtime包的map开首的几个文件中,重要为map.go。
go的map底层完成体式格局是hash表(C++的map是红黑树完成,而C++ 11新增的unordered_map则与go的map相似,都是hash完成)。go map的数据被置入一个由桶构成的有序数组中,每一个桶最多能够寄存8个key/value对。key的hash值(32位)的低阶位用于在该数组中定位到桶,而高8位则用于在桶中辨别key/value对。
go map的hash表中的基本单元是桶,每一个桶最多存8个键值对,超了,则会链接到分外的溢出桶。所以go map是基本数据构造是hash数组+桶内的key-value数组+溢出的桶链表
当hash表凌驾阈值须要扩容增进时,会分派一个新的数组,新数组的大小平常是旧数组的2倍。这里从旧数组将数据迁移到新数组,不会一次全量拷贝,go会在每次读写Map时以桶为单元做动态搬家分散。

2. go map的数据构造

我们先相识基本的数据构造,背面再看源码就简朴多了。

2.1 中心结体体

map重要由两个中心的构造,即基本构造和桶完成:

  • hmap:map的基本构造
  • bmap:严格来说hmap.buckets指向桶构成的数组,每一个桶的头部是bmap,以后是8个key,再是8个value,末了是1个溢出指针。溢出指针指向分外的桶链表,用于存储溢出的数据
const ( // 症结的变量
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits  // 一个桶最多存储8个key-value对
    loadFactorNum = 13 // 散布因子:loadFactorNum / loadFactorDen = 6.5。
    loadFactorDen = 2  // 即元素数目 >= (hash桶数目(2^hmp.B) * 6.5 / 8) 时,触发扩容
)
// map的基本数据构造
type hmap struct {
    count     int    // map存储的元素对计数,len()函数返回此值,所以map的len()时候复杂度是O(1)
    flags     uint8  // 纪录几个特别的位标记,如当前是不是有别的线程正在写map、当前是不是为雷同大小的增进(扩容/缩容?)
    B         uint8  // hash桶buckets的数目为2^B个
    noverflow uint16 // 溢出的桶的数目的近似值
    hash0     uint32 // hash种子

    buckets    unsafe.Pointer // 指向2^B个桶构成的数组的指针,数据存在这里
    oldbuckets unsafe.Pointer // 指向扩容前的旧buckets数组,只在map增进时有用
    nevacuate  uintptr        // 计数器,标示扩容后搬家的进度

    extra *mapextra // 保留溢出桶的链表和未运用的溢出桶数组的首地点
}

// 桶的完成构造
type bmap struct {
    // tophash存储桶内每一个key的hash值的高字节
    // tophash[0] < minTopHash示意桶的分散状况
    // 当前版本bucketCnt的值是8,一个桶最多存储8个key-value对
    tophash [bucketCnt]uint8
    // 特别注重:
    // 现实分派内存时会请求一个更大的内存空间A,A的前8字节为bmap
    // 背面顺次跟8个key、8个value、1个溢出指针
    // map的桶构造现实指的是内存空间A
}

// map.go里许多函数的第1个入参是这个构造,从成员来看很明显,此构造标示了键值对和桶的大小等必要信息
// 有了这个构造的信息,map.go的代码就能够与键值对的详细数据范例解耦
// 所以map.go用内存偏移量和unsafe.Pointer指针来直接对内存举行存取,而无需体贴key或value的详细范例
type maptype struct {
    typ        _type
    key        *_type
    elem       *_type
    bucket     *_type // internal type representing a hash bucket
    keysize    uint8  // size of key slot
    valuesize  uint8  // size of value slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

C++运用模板能够依据差别的范例生成map的代码。
golang则经由过程上述maptype构造体通报键值对的范例大小等信息,从而map.go直接用指针操纵对应大小的内存来完成全局一份map代码同时适用于差别范例的键值对。这点上能够以为比拟C++用模板完成map的体式格局,go map的目的文件的代码量会更小。

2.2 数据构造图

map底层建立时,会初始化一个hmap构造体,同时分派一个足够大的内存空间A。个中A的前段用于hash数组,A的后段预留给溢出的桶。因而hmap.buckets指向hash数组,即A的首地点;hmap.extra.nextOverflow初始时指向内存A中的后段,即hash数组末端的下一个桶,也即第1个预留的溢出桶。所以当hash争执须要运用到新的溢出桶时,会优先运用上述预留的溢出桶,hmap.extra.nextOverflow顺次今后偏移直到用完一切的溢出桶,才有能够会请求新的溢出桶空间。

上图中,当须要分派一个溢出桶时,会优先从预留的溢出桶数组里取一个出来链接到链表背面,这时候不须要再次请求内存。但当预留的桶被用完了,则须要请求新的内存给溢出桶。

3. go map的经常运用操纵

3.1 建立

运用make(map[k]v, hint)建立map时会挪用makemap()函数,代码逻辑比较简朴。
值得注重的是,makemap()建立的hash数组,数组的前面是hash表的空间,当hint >= 4时背面会追加2^(hint-4)个桶,以后再内存页帧对齐又追加了若干个桶(拜见2.2章节构造图的hash数组部份)
所以建立map时一次内存分派既分派了用户预期大小的hash数组,又追加了肯定量的预留的溢出桶,还做了内存对齐,一举多得。

// make(map[k]v, hint), hint即预分派大小
// 不传hint时,如用new建立个预设容量为0的map时,makemap只初始化hmap构造,不分派hash数组
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 省略部份代码
    // 随机hash种子
    h.hash0 = fastrand()

    // 2^h.B 为大于hint*6.5(扩容因子)的最小的2的幂
    B := uint8(0)
    // overLoadFactor(hint, B)只要一行代码:return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen)
    // 即B的大小应满足 hint <= (2^B) * 6.5
    // 一个桶能存8对key-value,所以这就示意B的初始值是保证这个map不须要扩容即可存下hint个元素对的最小的B值
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // 这里分派hash数组
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        // makeBucketArray()会在hash数组背面预分派一些溢出桶,
        // h.extra.nextOverflow用来保留上述溢出桶的首地点
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

// 分派hash数组
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b) // base代表用户预期的桶的数目,即hash数组的实在大小
    nbuckets := base // nbuckets示意现实分派的桶的数目,>= base,这就能够会追加一些溢出桶作为溢出的预留
    if b >= 4 {
        // 这里追加肯定数目的桶,并做内存对齐
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

    // 背面的代码就是请求内存空间了,此处省略
    // 这里人人能够思索下这个数组空间要怎样分派,实在就是n*sizeof(桶),所以:
        // 每一个桶前面是8字节的tophash数组,然后是8个key,再是8个value,末了放一个溢出指针
        // sizeof(桶) = 8 + 8*sizeof(key) + 8*sizeof(value) + 8
    
    return buckets, nextOverflow
}

3.2 插进去或更新

go map的插进去操纵,挪用mapassign()函数。
同砚们也许在某些材料上相识过:

  • go map须要初始化才运用,对空map插进去会panic。hmap指针通报的体式格局,决议了map在运用前必需初始化
  • go map不支撑并发读写,会panic。假如肯定要并发,请用sync.Map或本身处置惩罚争执

上述两个限定,在mapassign()函数开首能找到答案:

  1. 参数合法性检测,盘算hash值
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 不熟悉指针操纵的同砚,用指针传参往往会踩空指针的坑
    // 这里人人能够思索下,为何h要非空推断?
    // 假如肯定要在这里支撑空map并检测到map为空时自动初始化,应当怎样写?
    // 提醒:指针的指针
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    // 在这里做并发推断,检测到并发写时,抛非常
    // 注重:go map的并发检测是伪检测,并不保证一切的并发都邑被检测出来。而且这玩意是在运行期检测。
    // 所以对map有并发请求时,应运用sync.map来替代一般map,经由过程加锁来阻断并发争执
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    hash := alg.hash(key, uintptr(h.hash0)) // 这里获得uint32的hash值
    h.flags ^= hashWriting // 置Writing标志,key写入buckets后才会消灭标志
    if h.buckets == nil { // map不能为空,但hash数组能够初始是空的,这里会初始化
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
    
    ...
}
  1. 定位key在hash表中的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
again:
    bucket := hash & bucketMask(h.B) // 这里用hash值的低阶位定位hash数组的下标偏移量
    if h.growing() {
        growWork(t, h, bucket) // 这里是map的扩容缩容操纵,我们在第4章零丁讲
    }
    // 经由过程下标bucket,偏移定位到详细的桶
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    top := tophash(hash) // 这里取高8位用于在桶内定位键值对
    
    ...
}
  1. 进一步定位key能够插进去的桶及桶中的位置
  • 两轮轮回,外层轮回遍历hash桶及其指向的溢出链表,内层轮回则在桶内遍历(一个桶最多8个key-value对)
  • 有能够恰好链表上的桶都满了,这时候inserti为nil,第4步会链接一个新的溢出桶进来
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...

    var inserti *uint8          // tophash插进去位置
    var insertk unsafe.Pointer  // key插进去位置
    var val unsafe.Pointer      // value插进去位置
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if isEmpty(b.tophash[i]) && inserti == nil {
                    // 找到个空位,先纪录下tophash、key、value的插进去位置
                    // 但要遍历完才肯定要不要插进去到这个位置,因为背面有能够有反复的元素
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                }
                if b.tophash[i] == emptyRest {
                    break bucketloop // 遍历完悉数溢出链表,退出轮回
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if !alg.equal(key, k) {
                continue
            }
            // 走到这里申明map里找到一个反复的key,更新key-value,跳到第5步
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done // 更新Key后跳到第5步
        }
        ovf := b.overflow(t)
        if ovf == nil {
            break // 遍历完悉数溢出链表,没找到能插进去的空位,完毕轮回,下一步再追加一个溢出桶进来
        }
        b = ovf // 继承遍历下一个溢出桶
    }

    ...
}
  1. 插进去key
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    // 这里推断要不要扩容,我们第4章再讲
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }

    if inserti == nil { // inserti == nil申明上1步没找到空位,悉数链表是满的,这里增添一个新的溢出桶上去
        newb := h.newoverflow(t, b) // 分派新溢出桶,优先用3.1章节预留的溢出桶,用完了则分派一个新桶内存
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // 当key或value的范例大小凌驾肯定值时,桶只存储key或value的指针。这里分派空间并取指针
    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) // 在桶中对应位置插进去key
    *inserti = top // 插进去tophash,hash值高8位
    h.count++ // 插进去了新的键值对,h.count数目+1

    ...
}
  1. 完毕插进去
 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
 done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting // 开释hashWriting标志位
    if t.indirectvalue() {
        val = *((*unsafe.Pointer)(val))
    }
    return val // 返回value可插进去位置的指针,注重,value还没插进去
}
  • 只插进去了tophash和key,就完毕了吗?value还没插进去呢
  • 是的,mapassign()只插进去tophash和key,并返回val指针,编译器会在挪用mapassign()后用汇编往val插进去value
  • google大佬这么骚气的操纵,是为了削减value值通报的次数吗?

3.3 删除

  1. 删除与插进去相似,前面的步骤都是参数和状况推断、定位key-value位置,然后clear对应的内存。不展开说。以下是几个症结点:
  • 删除历程当中也会置hashWriting标志
  • 当key/value过大时,hash内外存储的是指针,这时候候用软删除,置指针为nil,数据交给gc去删。固然,这是map的内部处置惩罚,外层是无感知的,拿到的都是值拷贝
  • 不论Key/value是值范例照样指针范例,删除操纵都只影响hash表,外层已拿到的数据不受影响。尤其是指针范例,外层的指针还能继承运用
  1. 因为定位key位置的体式格局是查找tophash,所以删除操纵对tophash的处置惩罚是症结:
  • map起首将对应位置的tophash[i]置为emptyOne,示意该位置已被删除
  • 假如tophash[i]不是悉数链表的末了一个,则只置emptyOne标志,该位置被删除但未开释,后续插进去操纵不能运用此位置
  • 假如tophash[i]是链表末了一个有用节点了,则把链表最背面的一切标志为emptyOne的位置,都置为emptyRest。置为emptyRest的位置能够在后续的插进去操纵中被运用。
  • 这类删除体式格局,以少许空间来防备桶链表和桶内的数据挪动。事实上,go 数据一旦被插进去到桶的确实位置,map是不会再挪动该数据在桶中的位置了。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    ...

            b.tophash[i] = emptyOne // 先标记删除
            // 假如b.tophash[i]不是末了一个元素,则临时先占着坑。emptyOne标记的位置临时不能被插进去新元素(见3.2章节插进去函数)
            if i == bucketCnt-1 {
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    goto notLast
                }
            } else {
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }
            for { // 假如b.tophash[i]是末了一个元素,则把末端的emptyOne悉数消灭置为emptyRest
                b.tophash[i] = emptyRest
                if i == 0 {
                    if b == bOrig {
                        break // beginning of initial bucket, we're done.
                    }
                    // Find previous bucket, continue at its last entry.
                    c := b
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
                    }
                    i = bucketCnt - 1
                } else {
                    i--
                }
                if b.tophash[i] != emptyOne {
                    break
                }
            }

    ...
}

3.4 查找

查找操纵由mapaccess开首的一组函数完成。前面的章节在插进去和删除之前都得先定位查找到元素,逻辑是相似的,也比较简朴,就不细说了:

  • mapaccess1():经由过程Key查找,返回value指针,用于val := map[key]。未找到时返回value范例的0值。
  • mapaccess2():经由过程key查找,返回value指针,以及bool范例的是不是查找胜利的标志,用于val, ok := map[key]。未找到时返回value范例的0值。
  • mapaccessK():经由过程key查找,返回key和value指针,用于迭代器(range)。未找到时返回空指针
  • mapaccess1_fat(),对mapaccess1()的封装,区分是mapaccess1_fat()多了个zero参数,未找到时返回zero
  • mapaccess2_fat(),也是对mapaccess1()的封装。比拟mapaccess1_fat(),本函数增添一个是不是查找胜利的标志

3.5 range迭代

map的迭代是经由过程hiter构造和对应的两个辅佐函数完成的。hiter构造由编译器在挪用辅佐函数之前建立并传入,每次迭代效果也由hiter构造传回。下方的it等于hiter构造体的指针变量。

3.5.1 初始化迭代器mapiterinit()

mapiterinit()函数主如果决议我们从哪一个位置最先迭代,为何是从哪一个位置,而不是直接从hash数组头部最先呢?《go程序设计语言》彷佛提到过,hash表中数据每次插进去的位置是变化的(实在是因为完成的缘由,一方面hash种子是随机的,这致使雷同的数据在差别的map变量内的hash值差别;另一方面纵然同一个map变量内,数据删除再增添的位置也有能够变化,因为在同一个桶及溢出链表中数据的位置不分前后),所以为了防备用户毛病的依赖于每次迭代的递次,map作者痛快让雷同的map每次迭代的递次也是随机的。
迭代递次随机的完成体式格局也简朴,直接从随机的一个位置最先就好了:

  • it.startBucket:这个是hash数组的偏移量,示意遍历从这个桶最先
  • it.offset:这个是桶内的偏移量,示意每一个桶的遍历都从这个偏移量最先

因而,map的遍历历程以下:

  • 从hash数组中第it.startBucket个桶最先,先遍历hash桶,然后是这个桶的溢出链表。
  • 以后hash数组偏移量+1,继承前一步行动。
  • 遍历每一个桶,不论是hash桶照样溢出桶,都从it.offset偏移量最先。(假如只是随机一个最先的桶,range效果照样有序的;但每一个桶都加it.offset偏移,这个输出效果就有点虚无缥缈,人人能够亲手试下,对同一个map屡次range)
  • 当迭代器经由一轮轮回回到it.startBucket的位置,完毕遍历。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    ...
    
    // 随机一个偏移量来最先
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
        r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))
    
    ...
    
    mapiternext(it) // 初始化迭代器的同时也返回第1对key/value
}

3.5.2 迭代历程mapiternext()

上一节迭代轮回的历程很清楚了,这里我们申明几个重要的参数:

  • it.startBucket:最先的桶
  • it.offset:每一个桶最先的偏移量
  • it.bptr:当前遍历的桶
  • it.i:it.bptr已遍历的键值对数目,i初始为0,当i=8时示意这个桶遍历完了,将it.bptr移向下一个桶
  • it.key:每次迭代的效果
  • it.value:每次迭代的效果

另外,迭代还须要关注扩容缩容的状况:

  • 假如是在迭代最前后才growing,这类状况当前的逻辑没处置惩罚,迭代有能够非常。呃,go map不支撑并发。
  • 假如是先growing,再最先迭代,这是有能够的。这类状况下,会先到旧hash表中搜检key对应的桶有无被分散,未分散则遍历旧桶,已分散则遍历新hash内外对应的桶。

4. go map的扩容缩容

4.1 扩容缩容的基本道理

go map的扩容缩容都是grow相干的函数,这里扩容是真的,缩容是伪缩容,背面我会诠释。我们先看下触发前提:

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }
    
    ...
}

// overLoadFactor()返回true则触发扩容,即map的count大于hash桶数目(2^B)*6.5
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets(),望文生义,溢出桶太多了触发缩容
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B > 15 {
        B = 15
    }
    return noverflow >= uint16(1)<<(B&15)
}

map只在插进去元素即mapassign()函数中对是不是扩容缩容举行触发,前提等于上面这段代码:

  • 前提1:当前不处在growing状况
  • 前提2-1:触发扩容:map的数据量count大于hash桶数目(2^B)*6.5。注重这里的(2^B)只是hash数组大小,不包括溢出的桶
  • 前提2-2:触发缩容:溢出的桶数目noverflow>=32768(1<<15)或许>=hash数组大小。

仔细观察触发的代码,扩容和缩容是同一个函数,这是怎样做到的呢?在hashGrow()最先,会先推断是不是满足扩容前提,假如满足就表明此次是扩容,不满足就肯定是缩容前提触发了。扩容和缩容剩下的逻辑,重要区分就在于容量变化,就是hmap.B参数,扩容时B+1则hash表容量扩展1倍,缩容时hash表容量稳定。

  • h.oldbuckets:指向旧的hash数组,即当前的h.buckets
  • h.buckets:指向新建立的hash数组

到这里触发的重要事情已完成,接下来就是怎样把元素搬家到新hash内外了。假如如今就一次全量搬家过去,明显接下来会有比较长的一段时候map被占用(不支撑并发)。所以搬家的事情是异步增量搬家的。
在插进去和删除的函数内都有下面一段代码用于在每次插进去和删除操纵时,实行一次搬家事情:

    if h.growing() { // 当前处于搬家状况
        growWork(t, h, bucket) // 挪用搬家函数
    }
    
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // 将当前须要处置惩罚的桶搬家
    evacuate(t, h, bucket&h.oldbucketmask())

    if h.growing() { // 再多搬家一个桶
        evacuate(t, h, h.nevacuate)
    }
}
  • 每实行一次插进去或删除,都邑挪用growWork搬家0~2个hash桶(有能够此次须要搬家的2个桶在此之前都被搬过了)
  • 搬家是以hash桶为单元的,包括对应的hash桶和这个桶的溢出链表
  • 被delete掉的元素(emptyone标志)会被舍弃(这是缩容的症结)

4.2 为何叫“伪缩容”?怎样完成“真缩容”?

如今能够诠释为何我把map的缩容叫做伪缩容了:因为缩容仅仅针对溢出桶太多的状况,触发缩容时hash数组的大小稳定,即hash数组所占用的空间只增不减。也就是说,假如我们把一个已增进到很大的map的元素挨个悉数删撤除,hash表所占用的内存空间也不会被开释。

所以假如要完成“真缩容”,需本身完成缩容搬家,即建立一个较小的map,将须要缩容的map的元素挨个搬家过来:

// go map缩容代码示例
myMap := make(map[int]int, 1000000)

// 假定这里我们对bigMap做了许屡次插进去,以后又做了许屡次删除,此时bigMap的元素数目远小于hash表大小
// 接下来我们最先缩容
smallMap := make(map[int]int, len(myMap))
for k, v := range myMap {
    smallMap[k] = v
}
myMap = smallMap // 缩容完成,本来的map被我们抛弃,交给gc去清算

5 Q&A症结知识点

5.1 基本道理

  • 底层是hash完成,数据构造为hash数组 + 桶 + 溢出的桶链表,每一个桶存储最多8个key-value对
  • 查找和插进去的道理:key的hash值(低阶位)与桶数目相与,获得key地点的hash桶,再用key的高8位与桶中的tophash[i]对照,雷同则进一步对照key值,key值相称则找到
  • go map不支撑并发。插进去、删除、搬家等操纵会置writing标志,检测到并发直接panic
  • 每次扩容hash表增大1倍,hash表只增不减
  • 支撑有限缩容,delete操纵只置删除标志位,开释溢出桶的空间依托触发缩容来完成。
  • map在运用前必需初始化,不然panic:已初始化的map是make(map[key]value)或make(map[key]value, hint)这两种情势。而new或var xxx map[key]value这两种情势是未初始化的,直接运用会panic。

5.2 时候复杂度和空间复杂度剖析

时候复杂度,go map是hash完成,我们先不论详细道理,江湖套路hash完成的就叫它O(1)的时候复杂度:

  • 一般状况,且不斟酌扩容状况,复杂度O(1):经由过程hash值定位桶是O(1),一个桶最多8个元素,合理的hash算法应当能把元素相对匀称散列,所以溢出链表(假如有)也不会太长,所以虽然在桶和溢出链表上定位key是遍历,斟酌到数目小也能够以为是O(1)
  • 一般状况,处于扩容状况时,复杂度也是O(1):比拟于上一种状况,扩容会增添搬家最多2个桶和溢出链表的时候斲丧,当溢出链表不太长时,复杂度也能够以为是O(1)
  • 极度状况,散列极不匀称,大部份数据被集合在一条散列链表上,复杂度退化为O(n)。

go采纳的hash算法应是很成熟的算法,极度状况暂不斟酌。所以综合状况下go map的时候复杂度应为O(1)

空间复杂度剖析:
起首我们不斟酌因删除大批元素致使的空间糟蹋状况(这类状况如今go是留给程序员本身处置惩罚),只斟酌一个持续增进状况的map的一个空间运用率:
因为溢出桶数目凌驾hash桶数目时会触发缩容,所以最坏的状况是数据被集合在一条链上,hash表基本是空的,这时候空间糟蹋O(n)。
最好的状况下,数据匀称散列在hash表上,没有元素溢出,这时候最好的空间复杂度就是散布因子决议了,当前go的散布因子由全局变量决议,即loadFactorNum/loadFactorDen = 6.5。即均匀每一个hash桶被分派到6.5个元素以上时,最先扩容。所以最小的空间糟蹋是(8-6.5)/8 = 0.1875,即O(0.1875n)

结论:go map的空间复杂度(指撤除一般存储元素所需空间以外的空间糟蹋)是O(0.1875n) ~ O(n)之间。

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
go map数据结构和源码详解

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282102.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>