本文目录如下，浏览本文后，将一网打尽上面 Golang Map 相干面试题

面试题

1. map 的底层实现原理
2. 为什么遍历 map 是无序的？
3. 如何实现有序遍历 map？
4. 为什么 Go map 是非线程平安的？
5. 线程平安的 map 如何实现?
6. Go sync.map 和原生 map 谁的性能好，为什么？
7. 为什么 Go map 的负载因子是 6.5？
8. map 扩容策略是什么?

实现原理

Go 中的 map 是一个指针，占用 8 个字节，指向 hmap 构造体; 源码 src/runtime/map.go 中能够看到 map 的底层构造

每个 map 的底层构造是 hmap，hmap 蕴含若干个构造为 bmap 的 bucket 数组。每个 bucket 底层都采纳链表构造。接下来，咱们来具体看下 map 的构造

hmap 构造体

// A header for a Go map.
type hmap struct {
    count     int 
    // 代表哈希表中的元素个数，调用 len(map)时，返回的就是该字段值。flags     uint8 
    // 状态标记，下文常量中会解释四种状态位含意。B         uint8  
    // buckets（桶）的对数 log_2
    // 如果 B =5，则 buckets 数组的长度 = 2^5=32，意味着有 32 个桶
    noverflow uint16 
    // 溢出桶的大略数量
    hash0     uint32 
    // 哈希种子

    buckets    unsafe.Pointer 
    // 指向 buckets 数组的指针，数组大小为 2^B，如果元素个数为 0，它为 nil。oldbuckets unsafe.Pointer 
    // 如果产生扩容，oldbuckets 是指向老的 buckets 数组的指针，老的 buckets 数组大小是新的 buckets 的 1 /2; 非扩容状态下，它为 nil。nevacuate  uintptr        
    // 示意扩容进度，小于此地址的 buckets 代表已搬迁实现。extra *mapextra 
    // 这个字段是为了优化 GC 扫描而设计的。当 key 和 value 均不蕴含指针，并且都能够 inline 时应用。extra 是指向 mapextra 类型的指针。}

bmap 构造体

bmap 就是咱们常说的“桶”，一个桶外面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们通过哈希计算后，哈希后果是“一类”的，对于 key 的定位咱们在 map 的查问和插入中具体阐明。在桶内，又会依据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个地位（一个桶内最多有 8 个地位)。

// A bucket for a Go map.
type bmap struct {tophash [bucketCnt]uint8        
    // len 为 8 的数组
    // 用来疾速定位 key 是否在这个 bmap 中
    // 桶的槽位数组，一个桶最多 8 个槽位，如果 key 所在的槽位在 tophash 中，则代表该 key 在这个桶中
}
// 底层定义的常量 
const (
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits
    // 一个桶最多 8 个地位）但这只是外表 (src/runtime/hashmap.go) 的构造，编译期间会给它加料，动静地创立一个新的构造：type bmap struct {topbits  [8]uint8
  keys     [8]keytype
  values   [8]valuetype
  pad      uintptr
  overflow uintptr
  // 溢出桶
}

bucket 内存数据结构可视化如下：

留神到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的模式。源码里阐明这样的益处是在某些状况下能够省略掉 padding 字段，节俭内存空间。

mapextra 构造体

当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的状况下，会把 bmap 标记为不含指针，这样能够防止 gc 时扫描整个 hmap。然而，咱们看 bmap 其实有一个 overflow 的字段，是指针类型的，毁坏了 bmap 不含指针的构想，这时会把 overflow 挪动到 extra 字段来。

// mapextra holds fields that are not present on all maps.
type mapextra struct {// 如果 key 和 value 都不蕴含指针，并且能够被 inline(<=128 字节)
    // 就应用 hmap 的 extra 字段 来存储 overflow buckets，这样能够防止 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针。这时候咱们只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 蕴含的是 hmap.buckets 的 overflow 的 buckets
    // oldoverflow 蕴含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    overflow    *[]*bmap
    oldoverflow *[]*bmap

        nextOverflow *bmap    
    // 指向闲暇的 overflow bucket 的指针
}

次要个性

援用类型

map 是个指针，底层指向 hmap，所以是个援用类型

golang 有三个罕用的高级类型 slice、map、channel, 它们都是 援用类型，当援用类型作为函数参数时，可能会批改原内容数据。

golang 中没有援用传递，只有值和指针传递。所以 map 作为函数实参传递时实质上也是值传递，只不过因为 map 底层数据结构是通过指针指向理论的元素存储空间，在被调函数中批改 map，对调用者同样可见，所以 map 作为函数实参传递时体现出了援用传递的成果。

因而，传递 map 时，如果想批改 map 的内容而不是 map 自身，函数形参无需应用指针

func TestSliceFn(t *testing.T) {m := map[string]int{}
    t.Log(m, len(m))
    // map[a:1]
    mapAppend(m, "b", 2)
    t.Log(m, len(m))
    // map[a:1 b:2] 2
}

func mapAppend(m map[string]int, key string, val int) {m[key] = val
}

共享存储空间

map 底层数据结构是通过指针指向理论的元素 存储空间，这种状况下，对其中一个 map 的更改，会影响到其余 map

func TestMapShareMemory(t *testing.T) {m1 := map[string]int{}
    m2 := m1
    m1["a"] = 1
    t.Log(m1, len(m1))
    // map[a:1] 1
    t.Log(m2, len(m2))
    // map[a:1]
}

遍历程序随机

map 在没有被批改的状况下，应用 range 屡次遍历 map 时输入的 key 和 value 的程序可能不同。这是 Go 语言的设计者们无意为之，在每次 range 时的程序被随机化，旨在提醒开发者们，Go 底层实现并不保障 map 遍历程序稳固，请大家不要依赖 range 遍历后果程序。

map 自身是无序的，且遍历时程序还会被随机化，如果想程序遍历 map，须要对 map key 先排序，再依照 key 的程序遍历 map。

func TestMapRange(t *testing.T) {m := map[int]string{1: "a", 2: "b", 3: "c"}
    t.Log("first range:")
    // 默认无序遍历
    for i, v := range m {t.Logf("m[%v]=%v", i, v)
    }
    t.Log("\nsecond range:")
    for i, v := range m {t.Logf("m[%v]=%v", i, v)
    }

    // 实现有序遍历
    var sl []int
    // 把 key 独自取出放到切片
    for k := range m {sl = append(sl, k)
    }
    // 排序切片
    sort.Ints(sl)
    // 以切片中的 key 程序遍历 map 就是有序的了
    for _, k := range sl {t.Log(k, m[k])
    }
}

非线程平安

map 默认是并发不平安的，起因如下：

Go 官网在通过了长时间的探讨后，认为 Go map 更应适配典型应用场景（不须要从多个 goroutine 中进行平安拜访），而不是为了小局部状况（并发拜访），导致大部分程序付出加锁代价（性能），决定了不反对。

场景: 2 个协程同时读和写，以下程序会呈现致命谬误：fatal error: concurrent map writes

func main() {m := make(map[int]int)
    go func() {
                    // 开一个协程写 map
        for i := 0; i < 10000; i++ {m[i] = i
        }
    }()

    go func() {
                    // 开一个协程读 map
        for i := 0; i < 10000; i++ {fmt.Println(m[i])
        }
    }()

    //time.Sleep(time.Second * 20)
    for {;}
}

如果想实现 map 线程平安，有两种形式：

形式一：应用读写锁 map + sync.RWMutex

func BenchmarkMapConcurrencySafeByMutex(b *testing.B) {
    var lock sync.Mutex // 互斥锁
    m := make(map[int]int, 0)
    var wg sync.WaitGroup
    for i := 0; i < b.N; i++ {wg.Add(1)
        go func(i int) {defer wg.Done()
            lock.Lock()
            defer lock.Unlock()
            m[i] = i
        }(i)
    }
    wg.Wait()
    b.Log(len(m), b.N)
}

形式二：应用 golang 提供的 sync.Map

sync.map 是用读写拆散实现的，其思维是空间换工夫。和 map+RWLock 的实现形式相比，它做了一些优化：能够无锁拜访 read map，而且会优先操作 read map，假使只操作 read map 就能够满足要求(增删改查遍历)，那就不必去操作 write map(它的读写都要加锁)，所以在某些特定场景中它产生锁竞争的频率会远远小于 map+RWLock 的实现形式。

func BenchmarkMapConcurrencySafeBySyncMap(b *testing.B) {var m sync.Map    var wg sync.WaitGroup    for i := 0; i < b.N; i++ {        wg.Add(1)        go func(i int) {defer wg.Done()            m.Store(i, i)        }(i)    }    wg.Wait()    b.Log(b.N)}

哈希抵触

golang 中 map 是一个 kv 对汇合。底层应用 hash table，用链表来解决抵触，呈现抵触时，不是每一个 key 都申请一个构造通过链表串起来，而是以 bmap 为最小粒度挂载，一个 bmap 能够放 8 个 kv。在哈希函数的抉择上，会在程序启动时，检测 cpu 是否反对 aes，如果反对，则应用 aes hash，否则应用 memhash。

罕用操作

创立

map 有 3 钟初始化形式，个别通过 make 形式创立

func TestMapInit(t *testing.T) {// 初始化形式 1：间接申明    // var m1 map[string]int    // m1["a"] = 1    // t.Log(m1, unsafe.Sizeof(m1))    // panic: assignment to entry in nil map    // 向 map 写入要十分小心，因为向未初始化的 map（值为 nil）写入会引发 panic，所以向 map 写入时需先进行判空操作    // 初始化形式 2：应用字面量    m2 := map[string]int{}    m2["a"] = 2    t.Log(m2, unsafe.Sizeof(m2))    // map[a:2] 8    // 初始化形式 3：应用 make 创立    m3 := make(map[string]int)    m3["a"] = 3    t.Log(m3, unsafe.Sizeof(m3))    // map[a:3] 8}

map 的创立通过生成汇编码能够晓得，make 创立 map 时调用的底层函数是 runtime.makemap。如果你的 map 初始容量小于等于 8 会发现走的是runtime.fastrand 是因为容量小于 8 时不须要生成多个桶，一个桶的容量就能够满足

创立流程

makemap 函数会通过 fastrand 创立一个随机的哈希种子，而后依据传入的 hint 计算出须要的最小须要的桶的数量，最初再应用 makeBucketArray创立用于保留桶的数组，这个办法其实就是依据传入的 B 计算出的须要创立的桶数量在内存中调配一片间断的空间用于存储数据，在创立桶的过程中还会额定创立一些用于保留溢出数据的桶，数量是 2^(B-4) 个。初始化实现返回 hmap 指针。

计算 B 的初始值

找到一个 B，使得 map 的装载因子在失常范畴内

B := uint8(0)for overLoadFactor(hint, B) {B++}h.B = B// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}

查找

Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查问的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提醒 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。

// 不带 comma 用法 value := m["name"]fmt.Printf("value:%s", value)// 带 comma 用法 value, ok := m["name"]if ok {fmt.Printf("value:%s", value)}

map 的查找通过生成汇编码能够晓得，依据 key 的不同类型，编译器会将查找函数用更具体的函数替换，以优化效率：

查找流程

写爱护监测

函数首先会查看 map 的标记位 flags。如果 flags 的写标记位此时被置 1 了，阐明有其余协程在执行“写”操作，进而导致程序 panic。这也阐明了 map 对协程是不平安的。

if h.flags&hashWriting != 0 {throw("concurrent map read and map write")}

计算 hash 值

hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))

key 通过哈希函数计算后，失去的哈希值如下（支流 64 位机下共 64 个 bit 位）：

 10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

找到 hash 对应的 bucket

m: 桶的个数

从 buckets 通过 hash & m 失去对应的 bucket，如果 bucket 正在扩容，并且没有扩容实现，则从 oldbuckets 失去对应的 bucket

m := bucketMask(h.B)b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))// m 个桶对应 B 个位 if c := h.oldbuckets; c != nil {if !h.sameSizeGrow() {// 扩容前 m 是之前的一半      m >>= 1}  oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))  if !evacuated(oldb) {b = oldb}}

计算 hash 所在桶编号：

用上一步哈希值最初的 5 个 bit 位，也就是 01010，值为 10，也就是 10 号桶（范畴是 0~31 号桶）

遍历 bucket

计算 hash 所在的槽位:

top := tophash(hash)func tophash(hash uintptr) uint8 {top := uint8(hash >> (goarch.PtrSize*8 - 8))    if top < minTopHash {top += minTopHash}    return top}

用上一步哈希值哈希值的高 8 个 bit 位，也就是10010111，转化为十进制，也就是 151，在 10 号 bucket 中寻找 tophash 值（HOB hash）为 151* 的 槽位，即为 key 所在位置，找到了 2 号槽位，这样整个查找过程就完结了。

如果在 bucket 中没找到，并且 overflow 不为空，还要持续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包含所有的 overflow bucket。

返回 key 对应的指针

通过下面找到了对应的槽位，这里咱们再详细分析下 key/value 值是如何获取的：

// key 定位公式 k :=add(unsafe.Pointer(b),dataOffset+i*uintptr(t.keysize))// value 定位公式 v:= add(unsafe.Pointer(b),dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))// 对于 bmap 起始地址的偏移：dataOffset = unsafe.Offsetof(struct{  b bmap  v int64}{}.v)

bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大小；而咱们又晓得，value 的地址是在所有 key 之后，因而第 i 个 value 的地址还须要加上所有 key 的偏移。

赋值

通过汇编语言能够看到，向 map 中插入或者批改 key，最终调用的是 mapassign 函数。

实际上插入或批改 key 的语法是一样的，只不过前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。

mapassign 有一个系列的函数，依据 key 类型的不同，编译器会将其优化为相应的“疾速函数”。

咱们只用钻研最个别的赋值函数 mapassign。

赋值流程

map 的赋值会附带着 map 的扩容和迁徙，map 的扩容只是将底层数组扩充了一倍，并没有进行数据的转移，数据的转移是在扩容后逐渐进行的，在迁徙的过程中每进行一次赋值（access 或者 delete）会至多做一次迁徙工作。

校验和初始化

1. 判断 map 是否为 nil

2. 判断是否并发读写 map，若是则抛出异样
3. 判断 buckets 是否为 nil，若是则调用 newobject 依据以后 bucket 大小进行调配

迁徙

每一次进行赋值 / 删除操作时，只有 oldbuckets != nil 则认为正在扩容，会做一次迁徙工作，上面会具体说下迁徙过程

查找 & 更新

依据下面查找过程，查找 key 所在位置，如果找到则更新，没找到则找空位插入即可

扩容

通过后面迭代寻找动作，若没有找到可插入的地位，意味着须要扩容进行插入，上面会具体说下扩容过程

删除

通过汇编语言能够看到，向 map 中删除 key，最终调用的是 mapdelete 函数

func mapdelete(t \*maptype, h _hmap, key unsafe.Pointer)

删除的逻辑绝对比较简单，大多函数在赋值操作中曾经用到过，外围还是找到 key 的具体位置。寻找过程都是相似的，在 bucket 中挨个 cell 寻找。找到对应地位后，对 key 或者 value 进行“清零”操作，将 count 值减 1，将对应地位的 tophash 值置成 Empty

e := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*goarch.PtrSize+i*uintptr(t.elemsize))if t.elem.ptrdata != 0 {memclrHasPointers(e, t.elem.size)} else {memclrNoHeapPointers(e, t.elem.size)}b.tophash[i] = emptyOne

扩容

扩容机会

再来说触发 map 扩容的机会：在向 map 插入新 key 的时候，会进行条件检测，合乎上面这 2 个条件，就会触发扩容：

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    }

1、装载因子超过阈值

源码里定义的阈值是 6.5 (loadFactorNum/loadFactorDen)，是通过测试后取出的一个比拟正当的因子

咱们晓得，每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的状况下，装载因子算进去的后果是 8。因而当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。

对于条件 1，元素太多，而 bucket 数量太少，很简略：将 B 加 1，bucket 最大数量 (2^B) 间接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。留神，这时候元素都在老 bucket 里，还没迁徙到新的 bucket 来。新 bucket 只是最大数量变为原来最大数量的 2 倍(2^B * 2)。

2、overflow 的 bucket 数量过多

在装载因子比拟小的状况下，这时候 map 的查找和插入效率也很低，而第 1 点辨认不进去这种状况。表面现象就是计算装载因子的分子比拟小，即 map 里元素总数少，然而 bucket 数量多（实在调配的 bucket 数量多，包含大量的 overflow bucket）

不难想像造成这种状况的起因：不停地插入、删除元素。先插入很多元素，导致创立了很多 bucket，然而装载因子达不到第 1 点的临界值，未触发扩容来缓解这种状况。之后，删除元素升高元素总数量，再插入很多元素，导致创立很多的 overflow bucket，但就是不会触发第 1 点的规定，你能拿我怎么办？overflow bucket 数量太多，导致 key 会很扩散，查找插入效率低得吓人，因而出台第 2 点规定。这就像是一座空城，房子很多，然而住户很少，都扩散了，找起人来很艰难

对于条件 2，其实元素没那么多，然而 overflow bucket 数特地多，阐明很多 bucket 都没装满。解决办法就是开拓一个新 bucket 空间，将老 bucket 中的元素挪动到新 bucket，使得同一个 bucket 中的 key 排列地更严密。这样，原来，在 overflow bucket 中的 key 能够挪动到 bucket 中来。后果是节俭空间，进步 bucket 利用率，map 的查找和插入效率天然就会晋升。

扩容函数

func hashGrow(t *maptype, h *hmap) {bigger := uint8(1)    if !overLoadFactor(h.count+1, h.B) {bigger = 0        h.flags |= sameSizeGrow}    oldbuckets := h.buckets    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)    flags := h.flags &^ (iterator | oldIterator)    if h.flags&iterator != 0 {flags |= oldIterator}    // commit the grow (atomic wrt gc)    h.B += bigger    h.flags = flags    h.oldbuckets = oldbuckets    h.buckets = newbuckets    h.nevacuate = 0    h.noverflow = 0    if h.extra != nil && h.extra.overflow != nil {// Promote current overflow buckets to the old generation.        if h.extra.oldoverflow != nil {            throw("oldoverflow is not nil")        }        h.extra.oldoverflow = h.extra.overflow        h.extra.overflow = nil    }    if nextOverflow != nil {if h.extra == nil {            h.extra = new(mapextra)        }        h.extra.nextOverflow = nextOverflow    }    // the actual copying of the hash table data is done incrementally    // by growWork() and evacuate().}

因为 map 扩容须要将原有的 key/value 从新搬迁到新的内存地址，如果有大量的 key/value 须要搬迁，会十分影响性能。因而 Go map 的扩容采取了一种称为“渐进式”的形式，原有的 key 并不会一次性搬迁结束，每次最多只会搬迁 2 个 bucket。

下面说的 hashGrow() 函数实际上并没有真正地“搬迁”，它只是调配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或批改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。先查看 oldbuckets 是否搬迁结束，具体来说就是查看 oldbuckets 是否为 nil。

迁徙

迁徙机会

如果未迁徙结束，赋值 / 删除的时候，扩容结束后（预分配内存），不会马上就进行迁徙。而是采取 增量扩容 的形式，当有拜访到具体 bukcet 时，才会逐步的进行迁徙（将 oldbucket 迁徙到 bucket）

if h.growing() {        growWork(t, h, bucket)}

迁徙函数

func growWork(t *maptype, h *hmap, bucket uintptr) {// 首先把须要操作的 bucket 搬迁    evacuate(t, h, bucket&h.oldbucketmask())     // 再顺带搬迁一个 bucket    if h.growing() {        evacuate(t, h, h.nevacuate)    }}

nevacuate 标识的是以后的进度，如果都搬迁完，应该和 2^B 的长度是一样的

在 evacuate 办法实现是把这个地位对应的 bucket，以及其抵触链上的数据都转移到新的 buckets 上。

1. 先要判断以后 bucket 是不是曾经转移。(oldbucket 标识须要搬迁的 bucket 对应的地位)

b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))// 判断 if !evacuated(b) {// 做转移操作}

转移的判断间接通过 tophash 就能够，判断 tophash 中第一个 hash 值即可

func evacuated(b *bmap) bool {h := b.tophash[0]  // 这个区间的 flag 均是已被转移  return h > emptyOne && h < minTopHash // 1 ~ 5}

2. 如果没有被转移，那就要迁徙数据了。数据迁徙时，可能是迁徙到大小雷同的 buckets 上，也可能迁徙到 2 倍大的 buckets 上。这里 xy 都是标记指标迁徙地位的标记：x 标识的是迁徙到雷同的地位，y 标识的是迁徙到 2 倍大的地位上。咱们先看下指标地位的确定：

var xy [2]evacDstx := &xy[0]x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))x.k = add(unsafe.Pointer(x.b), dataOffset)x.v = add(x.k, bucketCnt*uintptr(t.keysize))if !h.sameSizeGrow() {  // 如果是 2 倍的大小，就得算一次 y 的值  y := &xy[1]  y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))  y.k = add(unsafe.Pointer(y.b), dataOffset)  y.v = add(y.k, bucketCnt*uintptr(t.keysize))}

3. 确定 bucket 地位后，须要依照 kv 一条一条做迁徙。
4. 如果以后搬迁的 bucket 和 总体搬迁的 bucket 的地位是一样的，咱们须要更新总体进度的标记 nevacuate

// newbit 是 oldbuckets 的长度，也是 nevacuate 的重点 func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {// 首先更新标记  h.nevacuate++  // 最多查看 2^10 个 bucket  stop := h.nevacuate + 1024  if stop > newbit {    stop = newbit}  // 如果没有搬迁就进行了，等下次搬迁  for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {h.nevacuate++}  // 如果都曾经搬迁完了，oldbukets 齐全搬迁胜利，清空 oldbuckets  if h.nevacuate == newbit {h.oldbuckets = nil    if h.extra != nil {      h.extra.oldoverflow = nil}    h.flags &^= sameSizeGrow  }

遍历

遍历的过程，就是按程序遍历 bucket，同时按程序遍历 bucket 中的 key。

map 遍历是无序的，如果想实现有序遍历，能够先对 key 进行排序

为什么遍历 map 是无序的？

如果产生过迁徙，key 的地位产生了重大的变动，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的后果就不可能按原来的程序了。

如果就一个写死的 map，不会向 map 进行插入删除的操作，按理说每次遍历这样的 map 都会返回一个固定程序的 key/value 序列吧。然而 Go 杜绝了这种做法，因为这样会给老手程序员带来误会，认为这是肯定会产生的事件，在某些状况下，可能会酿成大错。

Go 做得更绝，当咱们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个 随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个 随机序号的 cell 开始遍历。这样，即便你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。

//runtime.mapiterinit 遍历时选用初始桶的函数 func mapiterinit(t *maptype, h *hmap, it *hiter) {...  it.t = t  it.h = h  it.B = h.B  it.buckets = h.buckets  if t.bucket.kind&kindNoPointers != 0 {    h.createOverflow()    it.overflow = h.extra.overflow    it.oldoverflow = h.extra.oldoverflow  }  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))  it.bucket = it.startBucket    ...  mapiternext(it)}

总结

1. map 是援用类型
2. map 遍历是无序的
3. map 是非线程平安的
4. map 的哈希抵触解决形式是链表法
5. map 的扩容不是肯定会新增空间，也有可能是只是做了内存整理
6. map 的迁徙是逐渐进行的，在每次赋值时，会做至多一次迁徙工作

7. map 中删除 key，有可能导致呈现很多空的 kv，这会导致迁徙操作，如果能够防止，尽量避免

   本文由博客一文多发平台 OpenWrite 公布！