Fulongのblog

go之map

2019/09/11 Go 共 5548 字，约 16 分钟

map的实现

Go中的map在底层是用哈希表实现的，你可以在 $GOROOT/src/pkg/runtime/hashmap.goc 找到它的实现。

数据结构

map由结构体hmap构成

hmap 基本的map

type hmap struct {
  // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
  // Make sure this stays in sync with the compiler's definition.
  count     int // 哈希表中元素个数，即len(map)的返回值
  flags     uint8
  B         uint8  // 线性表中桶个数的的对数log_2(哈希表元素数量最大可达到装载因子*2^B)
  noverflow uint16 // 溢出桶的大概数字;详情见incrnoverflow
  hash0     uint32 // 哈希种子

  buckets    unsafe.Pointer // 指向线性表的指针，数组大小为2^B，如果元素个数为0，它为nil.
  oldbuckets unsafe.Pointer // 指向扩容后的老线性表地址
  nevacuate  uintptr        // 表示扩容进度

  extra *mapextra // 垃圾回收用
}

bmap结构体 是一个bucket

// A bucket for a Go map.
type bmap struct {
  // tophash包含此桶中每个键的哈希值最高字节（高8位）信息（也就是前面所述的high-order bits）。
  // 如果tophash[0] < minTopHash，tophash[0]则代表桶的搬迁（evacuation）状态。
    tophash [bucketCnt]uint8
}

为了便于理解，示意图如下所示

img

在顺序遍历时会用随机种子产生一个随机数，表示开始遍历的桶位置，因为随机数每次产生的数字可能都是不同的，所以每次for range得到的结果也是不同的。

每个bmap是keys一起，values一起，方便字节对齐，节省空间。

哈希函数

map 的一个关键点在于，哈希函数的选择。在程序启动时，会检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。

扩容

负载因子过大引起增量扩容

扩容hash表的时候每次都增大2倍，hash表大小始终为2的整数倍，有(hash mod 2^B) == (hash & (2^B-1))，方便于简化运算，避免取余操作

扩容后需要将old pair重新hash到新的hash表上（就是一个evacuate的过程）。这个过程不是一次性完成的，在每次insert、remove的时候会搬移1-2个pair。就是使用的是增量扩容

负载因子：填入表中的元素个数 / 散列表的长度。表示hash冲突机会大小。如果负载因子越大，则说明空间使用率越高，但产生哈希冲突的可能性更高。而负载因子越小，说明空间使用率低，产生哈希冲突的可能性更低

在go语言中如果载荷因子大于6.5就需要扩容了。每次扩容2倍

为什么要使用增量扩容

主要是缩短map容器的响应时间。如果不用增量扩容，当一个map存储很多元素后进行扩容，会阻塞很长时间无法响应请求。增量扩容的本质其实就是将总的扩容时间分摊到了每一次hash操作上

在搬数据的时候，并不会把旧的bucket从oldbucket中删除，只是加上了一个已删除的标记

扩容期间一部分数据在oldbucket中，一部分在bucket中，会对hash表的insert，remove，lookup操作的处理逻辑产生影响，如耗时更长等

只有当oldbucket中所有bucket移动到新表后，才会将oldbucket释放掉

等量扩容

溢出桶 overflow buckets 过多引起

如果负载因子没有超标，但是使用的溢出桶较多，也会触发扩容。但是是等量扩容

判断溢出桶是否太多，当桶总数 < 2 ^ 15 时，如果溢出桶总数 >= 桶总数，则认为溢出桶过多。当桶总数 >= 2 ^ 15 时，直接与 2 ^ 15 比较，当溢出桶总数 >= 2 ^ 15 时，即认为溢出桶太多了。buckets数量维持不变，该方法我们称之为等量扩容。

原因是原桶中有太多的键值对被删除，等量扩容可以使得剩余的键值对排列更加紧凑，节省空间

渐进式扩容

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”地方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。1-2个每次

所以如果触发了扩容操作，那么在很长时间里，map 的状态都是处于一个中间态：有些 bucket 已经搬迁到新家，而有些 bucket 还待在老地方。

map 遍历的核心在于理解 2 倍扩容时，老 bucket 会分裂到 2 个新 bucket 中去。而遍历操作，会按照新 bucket 的序号顺序进行，碰到老 bucket 未搬迁的情况时，要在老 bucket 中找到将来要搬迁到新 bucket 来的 key。

缩容 释放删除标志位对应空间

缩容是伪缩容。缩容时hash表容量不变。因为缩容仅仅针对溢出桶太多的情况，触发缩容时hash数组的大小不变，即hash数组所占用的空间只增不减。也就是说，如果我们把一个已经增长到很大的map的元素挨个全部删除掉，hash表所占用的内存空间也不会被释放。

触发缩容：溢出的桶数量noverflow>=32768(1«15)或者>=hash数组大小。

何时发生：delete操作只置删除标志位，释放溢出桶的空间依靠触发缩容来实现。

如果要实现“真缩容”，需自己实现缩容搬迁，即创建一个较小的map，将需要缩容的map的元素挨个搬迁过来。 目前没有。

查找过程

  1. 根据key计算出hash值。
  2. 如果存在old table, 首先在old table中查找，如果找到的bucket已经evacuated，转到步骤3。 反之，返回其对应的value。
  3. 在new table中查找对应的value。

这里一个细节需要注意一下。不认真看可能会以为低位用于定位bucket在数组的index，那么高位就是用于key/valule在bucket内部的offset。事实上高8位不是用作offset的，而是用于加快key的比较的。

do { //对每个桶b
    //依次比较桶内的每一项存放的tophash与所求的hash值高位是否相等
    for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {
        if(b->tophash[i] == top) {
            k2 = IK(h, k);
            t->key->alg->equal(&eq, t->key->size, key, k2);
            if(eq) { //相等的情况下再去做key比较...
                *keyp = k2;
                return IV(h, v);
            }
        }
    }
    b = b->overflow; //b设置为它的下一下溢出链
} while(b != nil);

插入过程

  1. 根据key算出hash值，进而得出对应的bucket。
  2. 如果bucket在old table中，将其重新散列到new table中。
  3. 在bucket中，查找空闲的位置，如果已经存在需要插入的key，更新其对应的value。
  4. 根据table中元素的个数，判断是否grow table。
  5. 如果对应的bucket已经full，重新申请新的bucket作为overbucket。
  6. 将key/value pair插入到bucket中。

这里也有几个细节需要注意一下。

在扩容过程中，oldbucket是被冻结的，查找时会在oldbucket中查找，但不会在oldbucket中插入数据。如果在oldbucket是找到了相应的key，做法是将它迁移到新bucket后加入evalucated标记。并且还会额外的迁移另一个pair。

然后就是只要在某个bucket中找到第一个空位，就会将key/value插入到这个位置。也就是位置位于bucket前面的会覆盖后面的(类似于存储系统设计中做删除时的常用的技巧之一，直接用新数据追加方式写，新版本数据覆盖老版本数据)。找到了相同的key或者找到第一个空位就可以结束遍历了。不过这也意味着做删除时必须完全的遍历bucket所有溢出链，将所有的相同key数据都删除。所以目前map的设计是为插入而优化的，删除效率会比插入低一些。

删除

  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是不会再移动该数据在桶中的位置了。
  • 删除操作本身不会触发搬移，但删除后的插入可能触发扩容或搬移。

map设计中的性能优化

HMap中是Bucket的数组，而不是Bucket指针的数组。好的方面是可以一次分配较大内存，减少了分配次数，避免多次调用mallocgc。但相应的缺点，其一是可扩展哈希的算法并没有发生作用，扩容时会造成对整个数组的值拷贝(如果实现上用Bucket指针的数组就是指针拷贝了，代价小很多)。其二是首个bucket与后面产生了不一致性。这个会使删除逻辑变得复杂一点。比如删除后面的溢出链可以直接删除，而对于首个bucket，要等到evalucated完毕后，整个oldbucket删除时进行。

bucket存8个key/value对。查找时进行顺序比较。第一次发现高位居然不是用作offset，而是用于加快比较的。定位到bucket之后，居然是一个顺序比较的查找过程。后面仔细想了想，觉得还行。由于bucket只有8个，顺序比较下来也不算过分。仍然是O(1)只不过前面系数大一点点罢了。相当于hash到一个小范围之后，在这个小范围内顺序查找。

插入删除的优化。前面已经提过了，插入只要找到相同的key或者第一个空位，bucket中如果存在一个以上的相同key，前面覆盖后面的(只是如果，实际上不会发生)。而删除就需要遍历完所有bucket溢出链了。这样map的设计就是为插入优化的。考虑到一般的应用场景，这个应该算是很合理的。

将多个几乎要empty的bucket合并；如果table中元素很少，考虑shrink table。

Key Points

参考

  • 在使用 range 遍历时的顺序时是乱序的，不能确定输出顺序。遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。扩容后顺序会变。Go 做得更绝，当我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。
  • map 作为参数传递时是传递的指针，所以修改 map 参数时等于修改原始变量。比如传参后map[k] = newv，是生效的
  • 在 使用 range 迭代器对 map 进行遍历时，range 会复制对象，如果value是指针，那么*v或者v.XX等操作是有效的，v的地址和value是两个元素，但指向了相同地址
  • 在 使用 range 迭代器对 map 进行遍历时，range 会复制对象，并且会重用迭代对象。 for _, v:= range map, 如果&v的话其实都是一个取的一个值。遍历时&v都是一样的，其实是把v 取的对应value的地址。

参考

  • float 类型可以作为 map 的 key， Go 语言中只要是可比较的类型都可以作为 key。除开 slice，map，functions 这几种类型，其他类型都是 OK 的。顺便说一句，任何类型都可以作为 value，包括 map 类型

  • map 不是线程安全的。在查找、赋值、遍历、删除的过程中都会检测写标志，一旦发现写标志置位（等于1），则直接 panic。赋值和删除函数在检测完写标志是复位之后，先将写标志位置位，才会进行之后的操作。

  • 无法对 map 的 key 或 value 进行取址，会无法编译成功。map存的是指针，不可以取址，扩容时会发生变化。

  • 非并发的同一个协程内边遍历边删除，并不会检测到同时读写，但是，遍历的结果就可能不会是相同的了，有可能结果遍历结果集中包含了删除的 key，也有可能不包含，这取决于删除 key 的时间：是在遍历到 key 所在的 bucket 时刻前或者后。

  • map 深度相等的条件：

    1. 都为 ni
2. 非空、长度相等，指向同一个 map 实体对象
3. 相应的 key 指向的 value “深度”相等

Search

    Table of Contents

    Popular Posts