golang 1.24 引入的 Swiss map 算法原理理解

本文主要讲解 Go 1.24 中引入的 Swiss Map . 我们首先需要回顾一下之前的 map 是如何工作的。 然后讲解 Swiss Map 原理

1 Go 1.24 之前：传统的链式哈希表

在 1.24 版本之前，Go 的 map 实现是一种经典的链式哈希表。其核心思想如下：

1. 数据结构：一个 map 在底层是一个指向 hmap 结构体的指针。hmap 结构体中最重要的部分是一个桶（bucket）数组。

type hmap struct {
    count     int 
    flags     uint8
    B         uint8  
    noverflow uint16 
    hash0     uint32 
    buckets    unsafe.Pointer 
    oldbuckets unsafe.Pointer 
    nevacuate  uintptr       
    extra *mapextra 
}

（1）count：map 中的 key-value 总数；

（2）flags：map 状态标识，可以标识出 map 是否被 goroutine 并发读写；

（3）B：桶数组长度的指数，桶数组长度为 2^B；

（4）noverflow：map 中溢出桶的数量；

（5）hash0：hash 随机因子，生成 key 的 hash 值时会使用到；

（6）buckets：桶数组；

（7）oldbuckets：扩容过程中老的桶数组；

（8）nevacuate：扩容时的进度标识，index 小于 nevacuate 的桶都已经由老桶转移到新桶中；

（9）extra：预申请的溢出桶.

2. 桶（Bucket）：每个桶是一个固定大小的内存块，可以存放 8 个键值对。

实际的机构如下

type bmap struct {
    tophash [bucketCnt]uint8
    keys [bucketCnt]T
    values [bucketCnt]T
    overflow uint8
}

其中tophash 字段存储了键的哈希的高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能

3. 哈希与定位：

   • 当你要插入或查找一个键（key）时，Go 会计算该键的哈希值。

   • 哈希值的高位用于在桶数组中定位到一个“主桶”（primary bucket），这里通过 hash 值对桶数组取模，确定所在的桶。

   • 哈希值的高 8 位，存放在桶内一个专门的 tophash 数组中。这用于在桶内快速筛选，避免昂贵的键值直接比较。

4. 冲突处理（链式）：

   • 如果两个不同的键哈希到了同一个主桶，它们会被放在这个桶的不同槽位（slot）里。

   • 如果主桶的 8 个槽位全部被占满，Go 会创建一个“溢出桶”（overflow bucket），并用一个指针从主桶链接到这个溢出桶。

   • 如果溢出桶也满了，就会继续链接下一个溢出桶，形成一个链表。

传统实现的主要痛点：

• 缓存不友好：当哈希冲突严重，导致溢出桶链表很长时，查找一个元素需要通过指针进行多次跳转。这种随机内存访问会频繁导致CPU 缓存未命中（Cache Miss），严重拖慢查找速度。

• 内存开销：每个桶（包括溢出桶）都是一个独立的内存块，通过指针连接。大量的指针和潜在的内存碎片会增加额外的内存开销。

2 Go 1.24 及之后：Swiss Map (开放地址法)

这里主要依据 src/internal/runtime/maps/map.go的注释后面有时间再补充源码，感觉源码比以前的map乱一些 Go 新版 Swiss Map 的实现结合了 Swiss Table 和 可扩展哈希 (Extendible Hashing) 的思想，以支持高效的增量式扩容。

2.1 1. 核心架构：分层设计 (Map -> Directory -> Table -> Group)

2.1.1 全新的数据布局：

• 它不再有“溢出桶”和指针链表。整个哈希表是一个连续的、扁平的内存块。

• 这个内存块被划分为多个“组”（groups）。

  • 每个组包含：

    • 一个控制字节数组（Control Bytes Array），也叫元数据区。
    • 一个键值槽数组（Key-Value Slots Array）。

Go 的 Swiss Map 采用了一种分层的存储结构，以实现高效的并发访问和增量式扩容。

// ...
// Terminology:
// - Slot: A storage location of a single key/element pair.
// - Group: A group of abi.SwissMapGroupSlots (8) slots, plus a control word.
// - Table: A complete "Swiss Table" hash table. A table consists of one or
//   more groups for storage plus metadata...
// - Map: The top-level Map type consists of zero or more tables for storage.
// - Directory: Array of the tables used by the map.

层次关系图:

   Map (顶层结构)
     │
     ├─ dirPtr (指向目录)
     │
     └─ Directory (目录, 是一个 []*table 数组)
          │
          ├─ Table[0] ─┐
          ├─ Table[1] ─┤ (每个 Table 是一个独立的 Swiss Table)
          └─ Table[n] ─┘
               │
               └─ groups: []Group (一个 Table 包含多个 Group)
                    │
                    ├─ Group[0]: [ctrl][slots]
                    ├─ Group[1]: [ctrl][slots]
                    └─ Group[m]: [ctrl][slots]

2.1.2 冲突处理（开放地址法）

• 当插入一个新键值对时，如果根据哈希值计算出的理想槽位已经被占用，它不会创建溢出桶。

• 取而代之的是，它会使用一种探测序列（probing sequence）（一种经过优化的二次探测）来寻找下一个可用的空槽位，并将键值对放入其中。

• 因为整个表是连续内存，所以探测过程也是在连续内存上进行的，这同样是缓存友好的。

2.2 2. Swiss Table 的核心：控制字节 (Control Word)

• 这是 Swiss Map 高性能的核心。每个 Group (包含8个槽位) 都有一个8字节的控制字。
• 这个字节里存储的不是 tophash，而是哈希值的最低 7 位，我们称之为 h2。
• 最高位（第 8 位）则用作一个哨兵位，来标记槽位的状态（例如：空、已删除、满）。

// ...
// Each byte in the control word corresponds to one of the slots in the group.
// In each byte, 1 bit is used to indicate whether the slot is in use, or if it
// is empty/deleted. The other 7 bits contain the lower 7 bits of the hash for
// the key in that slot.

2.2.0.0.1 控制字节结构

// 每个 Group 包含控制字节数组
type Group struct {
    ctrl [GroupSize]int8  // 通常 GroupSize = 8
    // slots 存储实际的 key-value 对
}

// 控制字节的三种状态
const (
    Empty   = -128  // 0x80: 空槽位
    Deleted = -1    // 0xFF: 已删除槽位 (墓碑标记)
    // 0-127: 存储哈希值的低7位，表示有效数据
)

2.2.0.0.2 控制字节的具体组成

// 哈希值处理
func processHash(hash uint64) int8 {
    // 取哈希值的低7位作为控制字节
    h2 := int8(hash & 0x7F)  // 0x7F = 0111_1111
    
    // 确保结果在 0-127 范围内
    if h2 == Empty || h2 == Deleted {
        h2 = 0  // 避免与特殊状态冲突
    }
    
    return h2
}

    Control Byte (8 bits):
    +---+-----------------+
    | 1 |        7        |
    +---+-----------------+
    | M |       h2        |
    (MSB)               (LSB)
    
    M:   哨兵位 (e.g., 1 = 空/删除, 0 = 满)
    h2:  哈希值的低 7 位

2.2.0.0.3 控制字节查找与状态转换

状态转换图:
Empty(-128) ──插入──→ Hash[0-127] ──删除──→ Deleted(-1)
     ↑                                         │
     └──────────── 重用槽位 ←───────────────────┘

具体例子:
hash("hello") = 0x2D4F8A3B
h2 = 0x2D4F8A3B & 0x7F = 0x3B = 59

Group控制字节: [59, -128, 67, -1, 89, -128, -128, -128]
对应状态:     [Full,Empty,Full,Del,Full,Empty,Empty,Empty]

• 并行查找：通过这个控制字，CPU 可以使用 SIMD 指令（如 SSE/AVX）一次性比较8个槽位的状态和哈希片段，而不是逐个比较。这极大地提升了查找速度。
• 状态编码：
  • Empty (-128): 槽位为空。
  • Deleted (-1): 槽位已被删除（墓碑）。
  • Full (0-127): 槽位被占用，存储了哈希值的低7位。

2.3 3. 哈希值分割：H1 和 H2

为了服务于分层结构和并行查找，一个64位的哈希值被分为两部分：

// H1: Upper 57 bits of a hash.
// H2: Lower 7 bits of a hash.

• H1 (高57位)：用于在 Table 内部定位起始的 Group（组内探测）。
• H2 (低7位)：存储在控制字节中，用于在 Group 内部进行快速的并行匹配。
• 更高位：用于在 Directory 中选择使用哪个 Table（表间路由）。

2.4 4. 查找与探测 (Probing)

当需要查找一个 key 时：

1. 选择 Table：使用哈希值的最高几位（由 globalDepth 决定）从 Directory 中找到对应的 Table。

2. 选择起始 Group：使用 H1 在 Table 的 groups 数组中计算出一个起始索引。

3. 并行匹配 Group：在起始 Group 中，使用 H2 和 SIMD 指令并行匹配8个控制字节，快速找到所有可能的匹配项。

   • 计算 h2：提取哈希值的低 7 位，得到 h2 值。
   • SIMD 加速匹配：CPU 不再是一个一个地比较 tophash，而是使用 SIMD（单指令多数据流） 指令（如 x86 上的 SSE2/AVX2），将我们想查找的 h2 值同时与一个组（go里面是 8 个）的所有控制字节进行比较。
   • 生成位掩码（Bitmask）：这个 SIMD 比较指令的结果是一个 16 位的位掩码。如果第 i 个控制字节中的 h2 部分与我们要找的 h2 匹配，那么位掩码的第 i 位就是 1，否则是 0。
   • 快速筛选：现在，程序只需要处理这个位掩码。通常情况下，这个掩码里 1 的数量会非常少（大部分是 0）。通过 trailing_zeros (tzcnt) 这样的位运算指令，可以极快地定位到哪些槽位是潜在的匹配项。

4. 验证 Key：对于每个可能的匹配，再完整地比较一次 key，以处理哈希碰撞。

5. 二次探测 (Quadratic Probing)：如果当前 Group 没有找到，或者发生了哈希冲突，会按照一个固定的二次方序列（i*i + i / 2）探测下一个 Group，直到找到匹配或空槽位。

// Probing
//
// Probing is done using the upper 57 bits (H1) of the hash as an index into
// the groups array. Probing walks through the groups using quadratic probing
// until it finds a group with a match or a group with an empty slot. See
// [probeSeq] for specifics about the probe sequence. Note the probe
// invariants: the number of groups must be a power of two, and the end of a
// probe sequence must be a group with an empty slot (the table can never be
// 100% full).

2.4.1 查找流程伪代码

func (m *Map) Get(key unsafe.Pointer) (unsafe.Pointer, bool) {
    hash := m.hasher(key, m.seed)
    
    // 步骤1: Directory选择Table
    dir := (*Directory)(m.dirPtr)
    table := dir.selectTable(hash)
    
    // 步骤2: Table内选择Group  
    groupIndex := (hash >> 7) % uint64(len(table.groups))
    group := &table.groups[groupIndex]
    
    // 步骤3: 控制字节匹配
    h2 := int8(hash & 0x7F)  // 低7位作为控制字节
    
    // 步骤4: SIMD并行查找
    mask := group.matchH2(h2)
    
    for mask != 0 {
        slot := trailingZeros(mask)
        if m.keyEqual(key, group.keyAt(slot)) {
            return group.elemAt(slot), true
        }
        mask = mask & (mask - 1)
    }
    
    return nil, false
}

2.4.2 插入数据 (map[key] = value)

目标：找到一个合适的位置存放新的键值对。这个位置要么是键已存在的位置（执行更新），要么是一个空或已删除的槽位（执行插入）。

流程步骤：

1. 计算哈希：计算 key 的完整哈希值。

2. 分解哈希：

   • 高位：用于计算在哈希表中的起始“组”（group）的位置。

   • 低 7 位：作为 h2 值，用于在控制字节数组中进行快速匹配。

3. 启动探测循环 (Probing Loop)：从起始组开始，按照预设的探测序列（一种二次探测的变体）依次检查各个组，直到找到目标或确认键不存在。

4. 在每个组内执行 SIMD 搜索：这是最关键的一步。在一个组内（例如 16 个槽位），CPU 并行地执行两项任务：

   • 任务 A (查找匹配键)：用 SIMD 指令将待插入键的 h2 值与组内所有 16 个控制字节的 h2 部分进行比较。这会生成一个“匹配掩码”（match bitmask），标记出所有 h2 值相同的槽位。

   • 任务 B (查找空闲槽)：用 SIMD 指令检查组内所有 16 个控制字节的状态位。这会生成一个“空闲掩码”（empty/deleted bitmask），标记出所有状态为 空 或 已删除 的槽位。

5. 分析搜索结果并决策：

   • 情况一：键已存在 (更新操作)

     • 检查“匹配掩码”。如果掩码不为零，说明存在 h2 相同的潜在匹配项。

     • 遍历这些潜在匹配项，进行完整的键比较（因为 h2 相同不代表键一定相同）。

     • 如果找到完全相同的键，就在其对应的键值槽中更新 value。插入操作结束。

   • 情况二：键不存在 (插入操作)

     • 如果在探测过程中，一直没有找到匹配的键，那么就需要找到一个位置插入新数据。

     • Swiss Map 会使用在步骤 4 中找到的第一个 空 或 已删除 的槽位。

     • 将新的 key 和 value 放入该槽位。

     • 更新该槽位对应的控制字节：将其状态设置为 满 (full)，并将 h2 值写入。插入操作结束。

6. 扩容 (Grow)：如果在整个探测循环中都没有找到匹配的键，也没有找到任何 空 或 已删除 的槽位，这意味着哈希表已经满了。此时会触发扩容：

   • 创建一个体积更大的新哈希表。

   • 将旧表中的所有元素重新计算哈希并插入到新表中。

   • 然后在新表中重复执行一次插入新键值的流程。

2.4.3 读取数据 (value, ok := map[key])

目标：根据键找到对应的值。

流程步骤：

1. 计算并分解哈希：同插入操作，计算 key 的完整哈希和 h2 值，并定位到起始组。

2. 启动探测循环：从起始组开始，按与插入时完全相同的探测序列进行搜索。

3. SIMD 搜索：在每个组内，使用 SIMD 指令将待查找键的 h2 值与所有控制字节进行比较，生成一个“匹配掩码”。

4. 遍历与验证：

   • 遍历“匹配掩码”中标记的每一个潜在匹配槽位。

   • 对每个槽位，进行完整的键比较。

   • 如果键完全匹配，则从对应的键值槽中读取 value，返回 (value, true)。读取操作成功结束。

5. 处理探测终止条件：

   • 如果在探测过程中，遇到了一个状态为 空 (empty) 的控制字节，则立即停止搜索。因为如果键存在，它一定是在这个 空 槽位之前被插入的（否则这个空位会破坏探测链）。此时可以断定键不存在，返回 (zero_value, false)。

   • 注意：遇到 已删除 (deleted) 的槽位不能停止，必须继续探测。因为要找的键可能是在这个槽位被删除之前，因为哈希冲突而被放到了探测链的更后方。

6. 未找到：如果探测循环走完了所有可能的组（直到再次回到起点或探测次数达到上限）仍未找到匹配的键，则说明键不存在，返回 (zero_value, false)。

2.4.4 删除数据 (delete(map, key))

目标：找到指定的键，并将其移除。

流程步骤：

1. 查找目标键：这个过程与读取数据的前半部分完全一样。通过哈希、探测、SIMD 搜索和完整的键比较，精确定位到要删除的键所在的槽位。

2. 处理未找到的情况：如果在查找过程中确定键不存在（例如，遇到了 空 槽位），则 delete 操作直接结束，什么也不做。

3. 执行删除（设置墓碑）：

   • 如果成功找到了键所在的槽位，关键的操作来了：不能将该槽位的控制字节直接设置为 空 (empty)。

   • 原因：如果直接设置为空，会打断那些因为哈希冲突而越过此槽位、存储在后面的元素的探测链。这会导致这些元素在未来的查找中变得“不可见”。

   • 正确做法：将该槽位的控制字节的状态设置为 已删除 (deleted)。这个状态被称为**“墓碑” (Tombstone)**。

4. 清理数据（可选）：将键值槽中的 key 和 value 清零，以便垃圾回收器可以回收它们占用的内存（如果它们是指针类型）。

“墓碑”的作用：

• 对于插入操作：它告诉插入流程，“这个位置是空的，可以被复用”。

• 对于读取/删除操作：它告诉查找流程，“这里曾经有数据，但现在没了，请不要停下，继续沿着探测链向后搜索”。

2.5 5. 增量式扩容：可扩展哈希 (Extendible Hashing)

这是 Go 实现与标准 Swiss Table 的一个重要区别，它避免了传统哈希表扩容时需要一次性迁移所有数据的巨大开销。

• globalDepth 和 localDepth：

  • Map.globalDepth：全局深度，决定 Directory 的大小 (2^globalDepth) 和用于选择 Table 的哈希位数。
  • table.localDepth：局部深度，表示这个 Table 是由多深的 Directory 分裂而来的。

• 扩容流程：

  1. 当一个 Table 满了，它会触发扩容。
  2. 如果 localDepth < globalDepth：说明 Directory 中有多个条目指向这个 Table。此时只需将这个 Table 分裂成两个，并将其中一个旧的 Directory 指针指向新的 Table 即可。这个过程非常快，不影响其他 Table。
  3. 如果 localDepth == globalDepth：说明 Directory 已经没有空间容纳分裂出的新 Table。此时需要先将 Directory 的大小加倍（globalDepth++），然后再进行 Table 的分裂。

// Growth
//
// The probe sequence depends on the number of groups. Thus, when growing the
// group count all slots must be reordered to match the new probe sequence. In
// other words, an entire table must be grown at once.
//
// In order to support incremental growth, the map splits its contents across
// multiple tables. Each table is still a full hash table, but an individual
// table may only service a subset of the hash space. Growth occurs on
// individual tables, so while an entire table must grow at once, each of these
// grows is only a small portion of a map. The maximum size of a single grow is
// limited by limiting the maximum size of a table before it is split into
// multiple tables.
//
// A map starts with a single table. Up to [maxTableCapacity], growth simply
// replaces this table with a replacement with double capacity. Beyond this
// limit, growth splits the table into two.
//
// The map uses "extendible hashing" to select which table to use. In
// extendible hashing, we use the upper bits of the hash as an index into an
// array of tables (called the "directory"). The number of bits uses increases
// as the number of tables increases. For example, when there is only 1 table,
// we use 0 bits (no selection necessary). When there are 2 tables, we use 1
// bit to select either the 0th or 1st table. [Map.globalDepth] is the number
// of bits currently used for table selection, and by extension (1 <<
// globalDepth), the size of the directory.
//
// Note that each table has its own load factor and grows independently. If the
// 1st bucket grows, it will split. We'll need 2 bits to select tables, though
// we'll have 3 tables total rather than 4. We support this by allowing
// multiple indicies to point to the same table. This example:
//
//	directory (globalDepth=2)
//	+----+
//	| 00 | --\
//	+----+    +--> table (localDepth=1)
//	| 01 | --/
//	+----+
//	| 10 | ------> table (localDepth=2)
//	+----+
//	| 11 | ------> table (localDepth=2)
//	+----+
//
// Tables track the depth they were created at (localDepth). It is necessary to
// grow the directory when splitting a table where globalDepth == localDepth.
//

2.5.1 扩容原理（转载）

这个原理写的很好 原文见参考

由于Go map是原生类型，且有了第一版实现，考虑到Go1兼容性，新版基于swiss table的实现也要继承已有的语义约束。同时，也要尽量避免swiss table自身的短板，Go团队在swiss table之上做了局部改进。比如为了将扩容带来的开销降到最低，Go引入了多table的设计，以支持渐进式扩容。也就是说一个map实际上是多个swiss table，而不是像上面说的一个map就是一个swiss table。每个table拥有自己的load factor，可以独立扩容(table的扩容是一次性扩容)，这样就可以将扩容的开销从全部数据变为局部少量数据，减少扩容带来的影响。

Go swiss-table based map的逻辑结构大致如下：

我们可以看出与C++ swisstable的最直观不同之处除了有多个table外，每个group包含8个slot和一个control word，而不是16个slot。此外，Go使用了二次探测(quadratic probing), 探测序列必须以空slot结束。

为了实现渐进式扩容，数据分散在多个table中；单个table容量有上限(maxTableCapacity)，超过上限时分裂成两个table；使用可扩展哈希(extendible hashing)根据hash高位选择table，且每个table可以独立增长。

Go使用Directory管理多个table，Directory是Table的数组，大小为2^globalDepth。如果globalDepth=2，那Directory最多有4个表，分为0×00、0×01、0×10、0×11。Go通过key的hash值的前globalDepth个bit来选择table。这是一种“extendible hashing”，这是一种动态哈希技术，其核心特点是通过动态调整使用的哈希位数(比如上面提到的globalDepth)来实现渐进式扩容。比如：初始可能只用1位哈希值来区分，需要时可以扩展到用2位，再需要时可以扩展到用3位，以此类推。

举个例子，假设我们用二进制表示哈希值的高位，来看一个渐进式扩容的过程：

• 初始状态 (Global Depth = 1):

directory
hash前缀  指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)

• 当table1满了需要分裂时，增加一位哈希值 (Global Depth = 2):

directory
hash前缀  指向的table
00** --> table3 (Local Depth = 2)  // 由table1扩容而成
01** --> table4 (Local Depth = 2)  // 由table1扩容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1)  // 复用table2因为它的Local Depth还是1

• 如果table2也满了，需要分裂：

directory
hash前缀  指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2扩容而成
11** --> table6 (Local Depth = 2) // 由table2扩容而成

通过extendible hashing实现的渐进式扩容，每次只处理一部分数据，扩容过程对其他操作影响小，空间利用更灵活。

对于新版go map实现而言，单个Table达到负载因子阈值时触发Table扩容。当需要分裂的Table的localDepth等于map的globalDepth时触发Directory扩容，这就好理解了。

除此之外，Go版本对small map也有特定优化，比如少量元素(<=8)时直接使用单个group，避免或尽量降低swiss table天生在少量元素情况下的性能回退问题。

2.6 6. 删除：墓碑机制 (Tombstones)

当一个元素被删除时，如果它所在的 Group 没有其他空槽位，那么这个槽位不会被标记为 Empty，而是被标记为 Deleted（墓碑）。

• 目的：防止探测序列中断。如果直接标记为 Empty，可能会导致后续的查找操作提前终止，从而找不到本应存在的元素。
• 回收：插入新元素时，会优先重用这些 Deleted 的槽位。只有在 Table 扩容时，这些墓碑才会被完全清理掉。

2.6.1 删除时通过控制字节状态 “立碑”

标记为删除

const (
    Empty   = -128  // 0x80: 空槽位
    Deleted = -1    // 0xFF: 已删除槽位 (墓碑标记)
    // 0-127: 存储哈希值的低7位，表示有效数据
)

2.6.2 通过墓碑避免数据迁移

传统开放寻址删除问题：
Hash Table: [A] [B] [C] [Empty] [E]
                ↑
            删除B后需要迁移C，因为查找C会在Empty处停止

Swiss Map墓碑机制：
Group: [A] [Deleted] [C] [Empty] [E]  
           ↑
       墓碎标记保持探测连续性

2.6.3 墓碑回收示例

删除前的状态

Group控制字节: [45, 67, 89, 12, 34, -128, -128, -128]
对应状态:     [Full,Full,Full,Full,Full,Empty,Empty,Empty]
Key-Value:    [k1,k2,k3,k4,k5,  ,  ,  ]

删除k2后的状态

Group控制字节: [45, -1, 89, 12, 34, -128, -128, -128]
对应状态:     [Full,Del,Full,Full,Full,Empty,Empty,Empty] 
Key-Value:    [k1, ∅ ,k3,k4,k5,  ,  ,  ]  // ∅表示已清理但保留槽位

插入新元素k6时回收墓碑

hash(k6) & 0x7F = 78

Group控制字节: [45, 78, 89, 12, 34, -128, -128, -128]
对应状态:     [Full,Full,Full,Full,Full,Empty,Empty,Empty]
Key-Value:    [k1,k6,k3,k4,k5,  ,  ,  ]  // 墓碑槽位被回收重用

2.6.4 墓碑清理机制

扩容时候不会复制墓碑

2.6.5 优势

• 性能优势

1. O(1)删除：无需数据迁移，直接标记即可
2. 保持探测连续性：不会破坏开放寻址的探测链
3. 延迟回收：在插入时自然重用，无额外开销

• 内存管理

1. 槽位重用：避免内存碎片化
2. 批量清理：扩容时统一清理，效率高
3. 动态平衡：根据墓碑比例决定是否清理

• 算法简洁性

1. 统一处理：Empty 和 Deleted 都被视为可用槽位
2. 无需回填：传统开放寻址删除需要复杂的元素迁移
3. SIMD友好：墓碑查找也可以并行化处理

2.7 总结

Go 新版 Swiss Map 的原理可以概括为：

1. 宏观上，使用可扩展哈希的思想，通过一个 Directory 管理多个独立的 Table，实现了增量式扩容，避免了全局STW（Stop-The-World）式的扩容。
2. 微观上，每个 Table 内部都是一个高性能的 Swiss Table，利用控制字节和 SIMD 指令实现了组内的并行查找，极大地提升了性能。
3. 通过哈希值分割（高位选 Table，H1选 Group，H2组内匹配）和二次探测，高效地组织和查找数据。
4. 使用墓碑机制优雅地处理删除操作，保证了数据结构的一致性。

3 参考

https://tonybai.com/2024/11/14/go-map-use-swiss-table/

4 其他

Swiss Map 层次结构:

Map
 │
 ├─ Directory (dirPtr)
 │   │
 │   ├─ globalDepth: 2
 │   ├─ localDepth: [2, 2, 1, 2]  
 │   └─ tables: []*Table
 │       │
 │       ├─ Table[0] ──┐
 │       ├─ Table[1]   │
 │       ├─ Table[2]   │ 每个Table包含多个Group
 │       └─ Table[3] ──┘
 │           │
 │           └─ groups: []Group
 │               │
 │               ├─ Group[0]: [ctrl][slots]
 │               ├─ Group[1]: [ctrl][slots]
 │               └─ Group[n]: [ctrl][slots]
 │
 └─ 其他字段 (seed, used, etc.)

small table 查找的流程，没有多个表

Map → Groups[] → Group[i] → [ctrl][slots]