抽丝剥茧—Go哈希Map的鬼魅神功

• Go语言中的哈希Map是江湖上极厉害的一门武功,其入门简单，即便是掌握到了2、3层也具有四两拨千斤的神奇功效.因此成为江湖人士竞相研习的技艺，风头一时无两.

• 但即便是成名已久的高手,也鲜有能修炼到最高层的.

• 本文不仅介绍了哈希Map基本的使用方式,还深入源码介绍了哈希Map的至高心法.希望本文有助于你对Go哈希Map的使用臻于化境.

哈希表

• Go语言中的Map,又称为Hash map(哈希表)是使用频率极高的一种数据结构，重要程度高到令人发指。

• 哈希表的原理是将多个key/value对分散存储在buckets(桶)中。给定一个key，哈希算法会计算出键值对存储的位置。时常会通过两步完成,伪代码如图所示:

hash = hashfunc(key)
index = hash % array_size

• 在此伪代码中,第一步计算通过hash算法计算key的hash值,其结果与桶的数量无关。

• 接着通过执行取模运算得到 0 - array_size−1 之间的index序号。

• 在实践中，我们时常将Map看做o(1)时间复杂度的操作,通过一个键key快速寻找其唯一对应的value。

Map基本操作

Map的声明与初始化

首先，来看一看map的基本使用方式。map声明的第一种方式如下

var hash  map[T]T

其并未对map进行初始化的操作,其值为nil,因此一旦进行 hash[key]=alue 这样的赋值操作就会报错。

panic(plainError("assignment to entry in nil map"))

比较意外的是Go语言允许对为nil的map进行访问: hash["Go"] ,虽然其结果显然毫无意义.

map的第二种声明方式通过make进行。make的第二个参数中代表初始化创建map的长度。当NUMBER为空时，代表默认长度为0.

var hash = make(map[T]T,NUMBER)

此种方式可以正常的对map进行访问与赋值

在map初始化时，还具有字面量形式初始化的方式。其在创建map时即在其中添加了元素。

    var country = map[string]string{
        "China":  "Beijing",
        "Japan":  "Tokyo",
        "India":  "New Delhi",
        "France": "Paris",
        "Italy":  "Rome",
    }

    rating := map[string]float64{"c": 5, "Go": 4.5, "Python": 4.5, "C++": 3}

Map的访问

map可以进行两种形式的访问:

 v  := hash[key]

以及

 v,ok := map[key]

当返回2个参数时，第2个参数代表当前key在map中是否存在。

不用惊讶于为什么同样的访问可以即返回一个值又返回两个值，这是在编译时做到的，后面会介绍。

Map的赋值

map的赋值语法相对简单

hash[key] = value

其代表将value与哈希表中的key绑定在一起

Map的删除

map的删除需要用到delete，其是Go语言中的关键字，用于进行map的删除操作，形如:

delete(hash,key)

可以对相同的key进行多次的删除操作，而不会报错

关于map中的key

布尔值是可比较的
整数值可比较的
浮点值是可比较的
复数值是可比较的
字符串值是可比较
指针值是可比较的。如果两个指针值指向相同的变量，或者两个指针的值均为nil，则它们相等。
通道值是可比较的。如果两个通道值是由相同的make调用创建的，或者两个值都为nil。
接口值是可比较的。如果两个接口值具有相同的动态类型和相等的动态值，或者两个接口值都为nil，则它们相等。
如果结构的所有字段都是可比较的，则它们的值是可比较的。
如果数组元素类型的值可比较，则数组值可比较。如果两个数组的对应元素相等，则它们相等。
切片、函数、map是不可比较的。

关于map并发冲突问题

• 和其他语言有些不同的是，map并不支持并发的读写,因此下面的操作是错误的

    aa := make(map[int]int)
    go func() {
        for{
            aa[0] = 5
        }
    }()
    go func() {
        for{
            _ = aa[1]
        }
    }()

报错:

fatal error: concurrent map read and map write

• Go语言只支持并发的读取Map.因此下面的函数是没有问题的

    aa := make(map[int]int)
    go func() {
        for{
            _ = aa[2]
        }
    }()
    go func() {
        for{
            _ = aa[1]
        }
    }()

Go语言为什么不支持并发的读写，是一个频繁被提起的问题。我们可以在Go官方文档 Frequently Asked Questions 找到问题的答案（https://golang.org/doc/faq#atomic_maps）

Map被设计为不需要从多个goroutine安全访问，在实际情况下，Map可能是某些已经同步的较大数据结构或计算的一部分。
因此，要求所有Map操作都互斥将减慢大多数程序的速度，而只会增加少数程序的安全性。

即这样做的目的是为了大多数情况下的效率。

Map在运行时

• 介绍了Map的基本操作,本节介绍一下Map在运行时的行为，以便能够深入Map内部的实现机制。

• 明白了Map的实现机制，有助于更加灵活的使用Map和进行深层次的调优过程。由于代码里面的逻辑关系关联比较复杂。本节会首先用多张图片帮助读者有一个抽象的理解。

  Go语言Map的底层实现如下所示:

// A header for a Go map.
type hmap struct {
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

其中：

• count 代表Map中元素的数量.

• flags 代表当前Map的状态（是否处于正在写入的状态等).

• B 对数形式表示的当前Map中桶的数量, 2^B = Buckets size.

• noverflow 为Map中溢出桶的数量.当溢出桶太多的时候，Map会进行 same-size map growth .其实质是为了避免溢出桶过大导致的内存泄露问题.

• hash0 代表生成hash的随机数种子.

• buckets 指向了当前Map对应的桶的指针.

• oldbuckets 是在Map进行扩容的时候存储旧桶的.当所有的旧桶中的数据都已经转移到了新桶,则清空。

• nevacuate 在扩容的时候使用。用于标记当前旧桶中小于nevacuate的桶都已经转移到了新桶.

• extra存储Map中的溢出桶

代表桶的 bmap 结构在运行时只列出了其首个字段: 即一个固定长度为8的数组。此字段顺序存储key的哈希值的前8位.

type bmap struct {
    tophash [bucketCnt]uint8
}

可能会有疑问，桶中存储的key和value值哪里去了？这是因为Map在编译时即确定了map中key,value,桶的大小。因此在运行时仅仅通过指针操作即可找到特定位置的元素。

桶本身在存储的tophash字段之后，会存储key数组以及value数组

type bmap struct {
    tophash [bucketCnt]uint8
    key   [bucketCnt]T
    value [bucketCnt]T
    ....
}

Go语言选择将key与value分开存储而不是key/value/key/value的形式，是为了在字节对齐的时候能够压缩空间。

在进行 hash[key] 此类的的Map访问操作时，会首先找到桶的位置，如下为伪代码操作.

hash = hashfunc(key)
index = hash % array_size

接着遍历tophash数组,如果数组中找到了相同的hash,那么就可以接着通过指针的寻址操作找到key与value值

• 在Go语言中还有一个溢出桶的概念,在执行 hash[key] = value 赋值操作时,当指定桶中的数据超过了8个，并不会直接就新开辟一个新桶,而是会将数据放置到溢出桶中每个桶的最后还存储了 overflow 即溢出桶的指针

  在正常情况下，数据是很少会跑到溢出桶里面去的。同理，我们也可以知道，在Map的查找操作时，如果key的hash在指定桶的tophash数组中不存在，还会遍历溢出桶中的数据。

  

• 后面我们会看到，如果一开始初始化map的数量比较大。则map提前创建好一些溢出桶存储在 extra *mapextra 字段.

type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

这样当出现溢出现象时，就可以用提前创建好的桶而不用申请额外的内存空间。当预分配的溢出桶使用完了，溢出桶才会新建。

当发生以下两种情况之一，map会进行重建：

• 当Map超过了负载因子大小

• 当溢出桶的数量过多

在哈希表中都有负载因子的概念

负载因子 = 哈希表中元素数量 / 桶的数量

• 因此随着负载因子的增大，意味着越多的元素会分配到同一个桶中。此时其效率会减慢。

• 试想如果桶的数量只有1个，此时负载因子到达最大,此时的搜索效率就成了遍历数组。在Go语言中的负载因子为6.5。

• 当超过了其大小后，Mpa会进行扩容，增大两倍于旧表的大小。

• 旧桶的数据会首先存到 oldbuckets 字段，并想办法分散的转移到新桶中。

• 当旧桶的数据全部转移到新桶之后,旧桶数据即会被清空。

• map的重建还存在第二种情况，即溢出桶的数量太多。这时只会新建和原来的map具有相同大小的桶。进行这样 same size 的重建为了是防止溢出桶的数量可能缓慢增长导致的内存泄露.

• 当进行map的delete操作时, 和赋值操作类似，会找到指定的桶，如果存在指定的key,那么就释放掉key与value引用的内存。同时tophash中指定位置会存储 emptyOne ,代表当前位置是空的。

• 同时在删除操作时，会探测到是否当前要删除的元素之后都是空的。如果是，tophash会存储为 emptyRest . 这样做的好处是在做查找操作时，遇到emptyRest 可以直接退出，因为后面的元素都是空的。