从面试题开始的Golang map#

问题：假设有一个golang的 map[int64]int64 存储了10亿（可以认为是）个用户的信息，key是用户的user id（唯一），估算至少需要多少内存？如果value无意义，退化为集合类型，又可以有什么优化？

理论最小值的估算非常简单，即16GB。但这个 16GB 只是纯粹的数据大小，完全忽略了 Go 为了实现 map 这个高效的哈希表结构而引入的巨大开销（Overhead）。

golang map的真实内存#

要精确计算，我们必须先了解 Go map 的底层结构。其核心是 hmap 和 bmap 两个结构体（源码位于 runtime/map.go）。

1
// A header for a Go map.
2
type hmap struct {
3
    count     int    // map中的元素个数，即 len()
4
    flags     uint8
5
    B         uint8  // buckets 数量的对数，即 buckets 数组的长度 = 2^B
6
    noverflow uint16 // 溢出桶的大约数量
7
    hash0     uint32 // 哈希种子
8

9
    buckets    unsafe.Pointer // 指向 bucket 数组的指针，数组大小为 2^B
10
    oldbuckets unsafe.Pointer // 扩容时，指向旧的 bucket 数组
11
    nevacuate  uintptr        // 扩容进度计数器
12

13
    extra *mapextra // 指向溢出桶等额外信息
14
}
15

16
// A bucket for a Go map.
17
type bmap struct {
18
    // tophash 存储了每个 key 哈希值的高8位
19
    // 用于在 bucket 中快速筛选，避免逐一比较 key
20
    tophash [8]uint8
21
    // tophash 后面紧跟着 8 个 key 和 8 个 value
22
    // keys    [8]keytype
23
    // values  [8]valuetype
24
    // ...
25
    overflow uintptr // 指向下一个溢出桶
26
}

map 的核心是一个 bucket 数组。
每个 bucket 通常可以存放 8 个 键值对。
为了保证查询效率，当 map 的负载因子（Load Factor） 超过 6.5 时，就会触发扩容。负载因子即 map元素总数 / bucket总数。

现在，我们可以根据数据结构计算存储 10 亿个元素所需的内存。

Bucket 数量

根据负载因子 6.5，我们需要的最小 Bucket 数为：
Buckets=6.5109 个元素≈153,846,154
由于 Bucket 数量必须是 2 的幂（2B），我们需要找到大于该值的最小 2 的幂。
- 227=134,217,728 (不够)
- 228=268,435,456 (足够)
因此，Go 运行时会为这个 map 分配 228 个 Bucket。

计算各部分内存占用

map 的总内存由 Keys、Values 和结构开销三部分组成。由于 map 预分配了 228 个 bucket，每个 bucket 有 8 个槽位，所以总槽位数为。

存储 Keys 的总空间:
2.147×109 个槽位×8 字节/key≈17.18×109 字节≈16.0 GB
存储 Values 的总空间:
2.147×109 个槽位×8 字节/value≈17.18×109 字节≈16.0 GB
结构开销:
- tophash: 每个槽位 1 字节。
  2.147×109 个槽位×1 字节≈2.15×109 字节≈2.0 GB
- 溢出指针 (overflow pointers): 每个 Bucket 1 个指针（64位系统占8字节）。
  228 个 buckets×8 字节/指针≈2.15×109 字节≈2.0 GB

‍

将以上各项相加：

结论：一个存储 10 亿 int64:int64 的 map，实际需要 36GB 的内存，是理论最小值的 2.5 倍以上。

如果改成集合呢？#

在很多场景中，我们只关心 Key 是否存在，而 Value 本身没有意义，比如用 map 来去重。这时，问题就从一个键值映射（Map）退化成了一个集合（Set） 。

map[int64]struct{}#

你可能会想用 map[int64]bool，但这是一个陷阱。bool 类型虽只占 1 字节，但因内存对齐，在 map 的 bucket 中仍会占据 8 字节的槽位，几乎没有优化效果。正确的姿势是使用空结构体 struct{}。

采用这种方法后，我们之前计算中的 Values 部分（16.0 GB）的开销就直接消失了。

总 内 存

更优解：bitmap#

其实我们还有一个条件没用到，即key是int64类型，并非普通的哈希表key，那么对于“整数集合”这个特定的问题，存在一种效率极高的数据结构——位图（Bitmap） 。其原理非常简单：用一个 bit 的状态（0 或 1）来表示一个整数是否存在。

如果使用 bitmap，则内存为：

但 bitmap 的问题是，如果user id分布不均衡，或者非常稀疏，在 int64 空间下需要分配非常大的内存：

Roaring Bitmap#

为了解决传统位图的稀疏数据难题，Roaring Bitmap 横空出世。它是一种高度优化的压缩位图，专门为高效存储大量整数集合而设计，早已成为许多大数据框架（如 Spark, Druid）的内置组件。

Roaring Bitmap 将整数空间按高16位和低16位分成不同的chunk块，每个chunk存储个整数。

根据chunk的稀疏程度：

如果整数非常稀疏，就用一个有序数组存储
如果整数非常密集，则使用bitmap

扩展阅读：Consistently faster and smaller compressed bitmaps with Roaring

golang Roaring Bitmap实现：roaring

‍

音乐