Map

map底层

数据结构有两种：哈希查找表（Hash table）、搜索树（Search tree）

哈希查找表用一个哈希函数将 key 分配到不同的桶（bucket，也就是数组的不同 index）。这样，开销主要在哈希函数的计算以及数组的常数访问时间。在很多场景下，哈希查找表的性能很高。
哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。一般有两种应对方法：链表法和开放地址法。链表法将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表。开放地址法则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key。
搜索树法一般采用自平衡搜索树，包括：AVL 树，红黑树
Go 语言采用的是哈希查找表，并且使用链表解决哈希冲突。

底层结构

type hmap struct {
  count     int              // 存储的键值对数目
  flags     uint8            // 状态标志（是否处于正在写入的状态等）
  B         uint8            // 桶的数目 2^B
  noverflow uint16           // 使用的溢出桶的数量
  hash0     uint32           // 生成hash的随机数种子

  buckets    unsafe.Pointer  // bucket数组指针，数组的大小为2^B（桶）
  oldbuckets unsafe.Pointer  // 扩容阶段用于记录旧桶用到的那些溢出桶的地址
  nevacuate  uintptr         // 记录渐进式扩容阶段下一个要迁移的旧桶编号
  extra *mapextra            // 指向mapextra结构体里边记录的都是溢出桶相关的信息
}

map扩容时使用渐进式扩容

原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。只有在插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。

翻倍扩容

count/(2^B) > 6.5：当负载因子超过6.5时就会触发翻倍扩容。

等量扩容

虽然没有超过负载因子限制，但是使用溢出桶过多，就会触发等量扩容，创建和旧桶数目一样多的新桶，然后把原来的键值对迁移到新桶中。

map 遍历无序

一个随机值序号的bucket，再从其中随机的cell开始遍历。
map在扩容后，会发生key的搬迁。

key 定位过程

key 经过哈希计算后得到哈希值，共 64 个 bit 位，计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。

# 最后的 5 个 bit 位,确定放到那个桶，哈希值的高 8 位，找到此 key 在 bucket 中的位置。
 10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

learning_notes

学习笔记

Map