1.24以前使用的是hmap, 在1.24及之后使用的是swisstable
先看一下老版本的hmap

hmap

1
2
3
4
5
6
7
8
9
10
11
12
13
type hmap struct {
    count     int
    flags     uint8
    B         uint8
    noverflow uint16
    hash0     uint32

    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr

    extra *mapextra
}

可以理解成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
map 变量
   |
   v
 hmap
   |
   +--> buckets ------> 当前 bucket 数组
   |
   +--> oldbuckets ---> 扩容前的 bucket 数组
   |
   +--> count          元素数量
   |
   +--> B              bucket 数量指数
   |
   +--> hash0          hash 随机种子
   |
   +--> nevacuate      扩容迁移进度

B代表的不是bucket的数量, 而是bucket指数, bucket = 2 ^ B

bmap

buckets 指向 bucket数组, 每一个bucket的类型是bmap

1
2
3
4
5
6
7
8
9
10
11
12
13
hmap
 |
 | buckets
 v
+---------+
| bucket0 |
+---------+
| bucket1 |
+---------+
| bucket2 |
+---------+
| bucket3 |
+---------+

bmap里面实际的布局是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
+-------------------------+
| tophash0                |
| tophash1                |
| ...                     |
| tophash7                |
+-------------------------+

| key0 |
| key1 |
| key2 |
| ...  |
| key7 |

| val0 |
| val1 |
| val2 |
| ...  |
| val7 |

+-------------------------+
| overflow *bmap          |
+-------------------------+

这里看起来比较奇怪, 为什么key放在一起, value放在一起

先看如果在一起

1
2
3
4
type Entry struct {
    key   int64 // 8 字节
    value int8  // 1 字节
}

看起来可能是占用9个字节, 但是CPU存在对数据的 内存对齐 要求, int64在内存中的理想起始位置是以8为分界的, 这个value占用了1, 但是下一个key的分布还是要以8为单位的, 实际上这个结构体要占用16个字节, 有7个字节是填充的, 如果像这样放在一起, 空间就存在较大的浪费, 所以就把key, value分开放, 可以减少填充

tophash
1
m["hello"]

首先会计算hash(“hello”), 得到一个64位的hash

这64位会分为两部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
低位 hash
   |
   v
决定 bucket


高 8 位 hash
   |
   v
tophash

例如
hash(key) =
10110110 ................ 0011
^^^^^^^^                   ^^^^
tophash                    bucket

假设B = 3, bucket 数量 = 8, 就需要hash的低3位bit, 011, 那么就进入bucket3

那tophash呢, 都到bucket了, 还要tophash干什么

进入一个bucket里面了, 要比较key和已经有的key是否相等, 最直接最笨的方法就是

1
2
3
4
key == keyA?
key == keyB?
key == keyC?
key == keyD?

直接进行字符串比较比较贵, 所以go先比较一个便宜的东西, tophash

只有tophash匹配了, 才去进行真正的 == 比较

hash0

每个map上都随机hash seed, 作用就是降低碰撞风险

overflow bucket

一个bucket正常里面只有8个slot, 如果大量的key都到这个bucket里面
满了怎么处理?

分配overflow bucket, 执行别的bucket, 有点像数组➕链表, 一个bucket链

noverflow

overflow bucket 大致数量, 为什么说“大致”？

因为在大 map 中，runtime 不一定精确计数，它主要用于判断：overflow bucket 是否太多了？

oldbuckets

原本

1
2
3
4
5
hmap
 |
 +-- buckets ---> 当前 bucket
 |
 +-- oldbuckets = nil

如果触发扩容, 创建新的buckets

但是不是立刻全部copy, 而是新旧两套暂时共存, 渐进式搬迁

1
2
3
4
5
hmap

buckets -> [new buckets]

oldbuckets ->[old buckets]
nevacuate

记录旧的bucket搬迁到哪了
比如旧的有 0, 1, 2,3, 4, 5, 6, 7
nevacuate = 3, 那就表示已经搬迁了0, 1, 2, bucket3下一批处理

搬迁也不是把旧bucket直接放在新bucket的对应位置, 而是根据新bucket的数量, 重新分位置

QA

为什么不是一次性搬

因为如果map比较大, 可能会非常耗时

扩容触发条件

hmap实现里面有两个触发条件

  1. 负载因子太高, 阈值是6.5
    因为每个bucket里面有8个slot, 如果平均达到了6.5, 说明碰撞概率明显上升, 于是进行2倍扩容

  2. overflow太多
    总数量没有很多, 但是因为频繁的插入/删除某个元素, 或者是hash分布问题, 导致出现大量overflow, 这是就会触发 same-size grow,
    bucket数量不变, 但是重新整理

为什么map元素不能取地址

1
2
3
4
5
m := map[string]int{
    "a": 10,
}

p := &m["a"] //会编译失败

因为扩容时, 原来可能是old bucket 2 slot4, 但是新的可能是new bucket 5 slot1
地址出现变化, 如果取地址, 然后发生扩容后, 值就不是代表原来的元素了, 所以go直接禁止了这种做法

swisstable

整体结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
                  Go Map
                    │
         ┌──────────▼───────────┐
         │      Directory       │
         └──────────┬───────────┘
                    │
         hash 高位选择 Table
     ┌──────────────┼──────────────┐
     │              │              │
     ▼              ▼              ▼
 Table 0        Table 1        Table 2
SwissTable     SwissTable     SwissTable
   │               │              │
Groups           Groups          Groups

整体分成了三层, 分别是Directory, table. group, 一个键进入map后计算出hash
通过高位前缀选择出table, 然后在table中, h分成高57位的h1和低7位h2, h1用来生成开放寻址的探测序列, h2用来匹配slot

核心源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type Map struct {
    used uint64
    seed uintptr

    dirPtr unsafe.Pointer
    dirLen int

    globalDepth uint8
    globalShift uint8

    writing uint8

    tombstonePossible bool

    clearSeq uint64
}

hmap的时候, 一个bucket放8个k, v, 发生冲突的时候, bucket -> overflow bucket -> overflowbucket 这样指针跳来跳去导致chache miss比较多(有点像1.26的GC优化, 也是优化了cache miss), 而swisstable 使用了开放寻址

group

swisstable的核心数据结构, 也是最基本的存储单位, 一个group有8个slot, 每个slot = key + value

Group = 8 slots + 8-byte control word

控制区ctrl一共8byte, 每个byte对应一个slot

1
2
3
4
5
6
7
8
9
10
             一个 Group
┌─────────────────────────────────────┐
│ control bytes                       │
│                                     │
│ c0 c1 c2 c3 c4 c5 c6 c7             │
├─────────────────────────────────────┤
│ slot0 slot1 slot2 ... slot7         │
│                                     │
│ K V   K V   K V       K V           │
└─────────────────────────────────────┘

这上面的c1, c2, c3 …, 他们能让swisstable能一次筛选8个slot

hash

hash被拆成H1, H2

1
2
3
4
5
6
7
hash
┌─────────────────────────────────────────────────────────────┐
│                    64 bits                                  │
├──────────────────────────────────────────────┬──────────────┤
│                    H1                        │      H2      │
│                  57 bits                     │     7 bits   │
└──────────────────────────────────────────────┴──────────────┘

H1是导航, 到哪找, H2是指纹, 怎么比较

普通hash表可能要每个slot hash和H2进行比较,但是swisstable可以一次比较得到H2符合的slot, 怎么做的呢

并行匹配的实现

1
2
3
4
5
6
7
8
9
10
bitsetLSB = 01 01 01 01 01 01 01 01
bitsetMSB = 80 80 80 80 80 80 80 80

func (g ctrlGroup) matchH2(h uintptr) bitset {
	return ctrlGroupMatchH2(g, h)
}
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset {
	v := uint64(g) ^ (bitsetLSB * uint64(h))
	return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)
}

bitsetLSB * uint64(h):把1-byte的h2复制成hhhhhhhh, 也就是复制八粉
uint64(g) ^ (bitsetLSB * uint64(h)): 异或让相等的字节变成0x00

(v - bitsetLSB) &^ v) & bitsetMSB) = ((v-0x0101010101010101) & ^v) & 0x8080808080808080

这个64-bit数字里哪些byte等于0, 哪些ctrl就等于H2

这是一个先把 8 个 slot 对应的 8 个 control byte 一次性装进一个 uint64，然后用位运算或 SIMD 一次判断“哪些 byte 等于 H2”的过程。

control word

一个 ctrl 是8bit

大致有三种状态：

1
2
3
empty
deleted
full + H2

当前源码定义：

1
2
ctrlEmpty   = 0b10000000
ctrlDeleted = 0b11111110

如果 slot 已被使用：

1
0hhhhhhh

后面的：

1
hhhhhhh

就是 7-bit H2。

所以可以想成：

1
2
3
4
5
6
7
8
9
full:
0 x x x x x x x
  └──── H2 ────┘

empty:
1 0 0 0 0 0 0 0

deleted:
1 1 1 1 1 1 1 0

为什么 full 最高位是 0？

因为这样可以非常容易批量判断：

1
2
哪些是 full
哪些是 empty/deleted

当前group找不到怎么办

会去下一个group找

为什么设计了一个empty状态

假设probe: group3 -> 没有key -> group4 -> 没有key, 但是有empty
就可以立刻终止: key不存在

因为如果这个key插入过, 在probe的过程中, 就肯定不会跨国一个没有使用的empty slot

为什么有deleted / tombstone

A hash 到 group3
B 也 hash 到 group3

但 A 占位，所以 B 最终被放到后面

现在delete(m, A), A的位置变成empty, 那查B的时候看到empty就会直接终止, 永远找不到group4里面的B, 所以需要标记deleted

Directory

为什么还需要快成而Directory, 而不是直接

1
2
3
4
5
6
7
8
9
10
Map
 |
 v
Swiss Table
 |
 +--> Group
 +--> Group
 +--> Group
 +--> Group
 ...

因为如果一个map非常巨大, 那发生扩容的时候, 代价也会非常大

Go 当前源码里：const maxTableCapacity = 1024, 一个 Swiss Table最多管理 1024 个 slot, 超过以后不是把整个 map 翻倍

而是：

1
只 split 当前这个 table

官方 Go Blog 也专门解释了这一点：这样单次插入触发扩容时，需要搬迁的数据量被限制在一个 table 的量级，而不是整个 map。Go程序设计语言
例如：

1
2
3
4
5
6
Directory

00 ──────> Table A
01 ──────> Table B
10 ──────> Table C
11 ──────> Table D

假设：

1
Table C 满了

只做：

1
2
3
4
5
6
Table C

        split
       /     \
      v       v
   Table C0 Table C1

其它：

1
A B D

完全不动。

Directory怎么选择table

这里会使用hash的高位, 假设globalDepth = 2, 那么hash最前面2bit就决定是哪个

globalDepth和localDepth

globalDepth表示Dorectory使用多少位bit
localDepth表示这个table根据多少位hash分裂过

这里会出现一种情况, 多个directory entry指向同一个Table

1
2
3
4
5
6
7
8
9
globalDepth = 2

00 ──┐
     ├──> Table A (localDepth=1)
01 ──┘

10 ─────> Table B (localDepth=2)

11 ─────> Table C (localDepth=2)

因为A只分裂到1, 所以它不关心第二位, 00, 01都指向A

扩容

  1. Table grow
    容量小于1024的时候, 并且插入元素 / 容量 = 7/8, 也就是达到负载因子, 就进行翻倍扩容, 128->256->512->1024, table大小不超过1024, 所以容量达到1024的table在进行扩容就使用方法2

    旧table插入新table, 元素位置要重新计算, 这里与hmap不同, 不是渐进式的搬迁, 因为table比较小,所以是一次完成, 旧table被回收

  2. split
    达到1024后不能进行grow, 使用拆分
    原来Table A, localDepth = 2, 因为它只区分了前两位hash, 现在满了, 那就增加一位
    例如 hash = 101011...
    前两位10, 进入tableA, split后再看第三位, 1进入A1, 0进入A0

    split时, Directory不一定增加(参见上面globalDepth, localDepth的图)

    原来globalDepth = 2, localDepth = 1, split后, localDepth = 2, 本来Directory只查看两位, 所以有4个入口, 而tableA只查看第一位, 所以00, 01都是A, 10, 11属于B, C, 分裂后A也要查看两位, 所以就要拆分成A0, A1两个表, 此时还不用扩大

    什么时候Directory需要扩大

    当globalDepth == localDepth的时候, 再进行split扩容, 就需要进行扩大了
    此时说明diorectory已经没有更多的table可以拆分了, Directory需要翻倍

map怎么实现并发安全
  1. sync.Mutex: 实现起来简单
  2. sync.RWMutex: 允许并发读, 不允许并发写, 明显读多写少的时候用
  3. sync.Map
    • key 相对稳定，读很多、写很少
    • 或不同 goroutine 操作的 key 集合相对独立
    • 希望减少大量显式锁竞争
map里面的key为什么必须可比较

它不光需要计算hash, hash值匹配到对应的位置之后还要进行== 比较