F14 哈希表：Meta 自研的 Chunk-based SIMD 哈希表

源码路径：references/impl/folly/folly/container/F14Map.h, F14Set.h

F14 是 Folly 的哈希表实现，比 SwissTable 更进一步：它将哈希表分为固定大小的 chunks，每个 chunk 内部使用 SIMD 探测。F14 有多个变体（F14Fast*、F14Value*、F14Node*、F14Vector*），适用于不同的引用稳定性和内存布局需求。

注意：下方布局图展示的是 F14Value 的简化模型。实际 chunk 大小取决于 Item 的大小和对齐，不一定固定为 128 字节。溢出处理使用 hosted/outbound overflow 计数器而非链表。

Chunk-based 布局

F14 Chunk 内存布局（128 字节，cache-line 对齐）：

┌──────────────────── 128 字节 Chunk ────────────────────────────────────┐
│                                                                        │
│  Tag 数组（16 字节，16 字节对齐）                                       │
│  ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│  │ T0 │ T1 │ T2 │ T3 │ T4 │ T5 │ T6 │ T7 │ T8 │ T9 │T10 │T11 │T12 │T13 │ OF │SENT│
│  └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
│   ├──── 14 个 H2 tag ────────────────────────┤│溢出│哨兵│                          │
│                                                                        │
│  每个 Tag 字节（8 位）：                                                │
│  ┌───┬──────────────┐                                                  │
│  │occ│  H2 (7 bit)  │  occupied=1 表示已占用                           │
│  └───┴──────────────┘                                                  │
│                                                                        │
│  Value 数组（14 个 slot）                                               │
│  ┌─────────┬─────────┬─────────┬─────────┬─ ··· ─┬─────────┐          │
│  │ slot 0  │ slot 1  │ slot 2  │ slot 3  │       │ slot 13 │          │
│  └─────────┴─────────┴─────────┴─────────┴─ ··· ─┴─────────┘          │
│                                                                        │
│  注意：Tag[14] 和 Tag[15] 不对应任何 slot → 实际可用 14 个值            │
└────────────────────────────────────────────────────────────────────────┘

为什么 14 而不是 16？ Tag 数组必须 16 字节对齐（SSE2 一次处理 16 字节），但 F14 需要 2 个 tag 位置用于溢出标记和哨兵。所以实际可用 slot = 16 - 2 = 14。

SIMD 探测

cpp

// SSE2 tag 匹配
__m128i ctrl = _mm_load_si128(tagArray);  // 一次加载 16 个 tag
__m128i match = _mm_set1_epi8(tag);       // 广播目标 tag
uint16_t mask = _mm_movemask_epi8(_mm_cmpeq_epi8(ctrl, match));
// mask 的每个置位位 = 一个候选 slot
while (mask) {
  int idx = __builtin_ctz(mask);
  if (keys_equal(slot[idx], target_key)) return &slot[idx];
  mask &= mask - 1;  // 清除最低位
}

与 SwissTable 的对比

维度	F14	SwissTable
基本单位	128 字节 chunk（14 slots）	连续 ctrl 数组 + 连续 slot 数组
tag/ctrl	16 字节对齐数组	1 字节 ctrl 分离存储
溢出处理	hosted/outbound overflow 计数器	二次探测到下一个 Group
缓存行为	chunk 内连续访问	连续探测跨多个缓存行
负载因子	~87%（14/16）	~87%（7/8）
内存布局	每个 chunk 自含	全局 ctrl[] + 全局 slots[]

F14 的优势：每个 chunk 是自含的——tag 和 value 在同一 cache line 内。命中 tag 后访问 value 几乎不会有 cache miss。SwissTable 的分离布局在 ctrl 命中后可能需要额外的 cache line 加载来获取 value。

SwissTable 的优势：更大的 SIMD 组（连续探测 16+ slots vs 每组 14 slots），在高负载下探测效率可能更高。

用户 API

用户通常通过 F14FastMap、F14ValueMap、F14NodeMap、F14VectorMap 等别名接触 F14；本文现有正文主要分析底层 chunk 设计。

标准语义

F14 的 API 与标准 std::unordered_map / std::unordered_set 高度兼容，但存在以下差异：

特性	标准 `unordered_*`	F14
`max_load_factor`	用户可调（默认 1.0）	固定 1.0，调用是空操作
`bucket_count()`	返回桶数	返回总 slot 数（`chunkCount * kCapacity` 或单 chunk 自定义容量）
`bucket(key)`	返回桶索引	不提供
`begin(bucket)` / `end(bucket)`	按桶迭代	不提供
`rehash(n)`	精确控制桶数	行为等价于 `reserve(n)`
`reserve(n)`	预留 n 个桶	精确预留 n 个元素容量
异构查找（heterogeneous lookup）	C++20 `is_transparent`	通过 `FollyHasher` / `FollyKeyEqual` 提供 transparent 支持（等价于 P0919/P2363）
`F14HashToken` / `hashed_key_type`	无	F14 独有：`prehash(key)` 预计算哈希，`find(token, key)` 跳过哈希，`prefetch(token)` 提前预取
`erase_if`	C++20 自由函数	同名自由函数，API 一致

各变体的稳定性语义差异：

F14ValueMap：value 内联存储于 chunk。插入/删除/rehash 可能移动元素地址，引用和迭代器不稳定性等同于 std::vector。
F14NodeMap：chunk 内仅存储指针（Item = pointer），value 在堆上独立分配。插入/rehash 不移动已有节点，引用稳定，迭代器在被删元素失效外均稳定。
F14VectorMap：chunk 内存储 uint32_t 索引，实际 value 存在于连续的 vector<Value>。插入可触发 vector 扩容，所有引用和迭代器不稳定。
F14FastMap：编译期根据 sizeof(pair<Key const, Mapped>) < 24 选择 F14ValueMap（小节点）或 F14VectorMap（大节点），稳定性语义随之变化。

所有变体均提供 operator==/operator!=、swap、erase_if、CTAD 推导指南，行为与标准一致。const_iterator 到 iterator 的隐式转换仅在 map 类型（非 set）中可用。

对象布局

上文已经覆盖 14-slot chunk、tag array 与 value array 的关系；后续补各变体（Value/Node/Vector）的对象布局差异。

核心源码路径

本文开头已给出 F14Map.h / F14Set.h；后续补 F14Table.h、SIMD tag 匹配与 overflow 计数相关实现入口。

核心类 / 函数

底层核心（folly/container/detail/）：

F14Chunk<Item>（F14Table.h）：chunk 结构体。包含 14 字节 tags_ 数组、1 字节 control_（低 4 位 capacityScale，高 4 位 hostedOverflowCount）、1 字节 outboundOverflowCount_。Item 数组从 kItemsOffset 字节偏移处开始，通过指针算术而非成员数组访问。kCapacity 在 sizeof(Item) == 4 时为 12（凑满一个 cache line），否则为 14。sizeof(Item) == 16 时额外加 1 个 slot 的 padding 使 chunk 恰好 4 个 cache line。
F14ItemIter<ChunkPtr>（F14Table.h）：chunk 内元素迭代器，持有 ItemPtr 和 index_。advance() 从高 index 向低扫描当前 chunk 的 occupied tag，当前 chunk 为空时沿 prevChunkRaw 向前跳转到前一个 chunk 的 lastOccupied。
PackedChunkItemPtr<T*>（F14Table.h）：将 Item* 和 slot index 打包进单个 uintptr_t，利用 chunk 16 字节对齐的低位空闲位存储 index（最多 4 bit），用于 packedBegin 压缩存储。
F14Table<Policy>（F14Table.h）：所有变体的底层哈希表引擎。管理 ChunkPtr chunks_ 和 SizeAndChunkShiftAndPackedBegin。提供 findImpl（SIMD tag 探测 + overflow 继续）、tryEmplaceValueImpl（查找 → reserve → allocateTag → insertAtBlank）、eraseImpl（destroyItem → eraseBlank 修正 overflow 计数）、rehashImpl（分配新 chunk 数组 → moveItemDuringRehash）。
splitHashImpl<Hasher, Key>（F14Table.h）：将用户哈希值拆分为 (position, tag)。非 avalanching hasher 时使用 CRC32（x86 SSE4.2 / ARM CRC）或 128-bit 乘法 mixer 修复熵分布；avalanching hasher 时直接取高位为 tag（| 0x80 保证非零）。

Policy 层（F14Policy.h）：

BasePolicy：管理 Hasher/KeyEqual/Alloc 三元组（EBO 优化空状态），提供 computeKeyHash、keyForValue、moveValue（map 的 const_cast hack 避免 key 拷贝）。
ValueContainerPolicy（Item == Value）：value 内联，constructValueAtItem 直接在 chunk 内 placement new。prefetchBeforeRehash/Copy/Destroy 均为 false（value 就在 chunk 内）。
NodeContainerPolicy（Item == pointer）：constructValueAtItem 先 allocate 节点再 placement new 到堆上，chunk 内存储指针。prefetchBeforeRehash/Copy 为 true（需预取堆上节点）。moveItemDuringRehash 只移动指针。
VectorContainerPolicy（Item == uint32_t）：chunk 内存储索引，实际 value 在 values_ 连续数组中。kEnableItemIteration = false（迭代器不走 chunk 遍历，走 values_ 线性扫描）。beforeRehash 负责 transfer 整个 values 数组。kContinuousCapacity = true（允许非 2 的幂容量）。

用户层（F14Map.h / F14Set.h）：

F14BasicMap<Policy> / F14BasicSet<Policy>：CRTP 无关的公共 API 壳，持有 F14Table<Policy> table_。提供标准容器接口、异构查找/插入/删除的 SFINAE 门控、prehash/prefetch/hashed_key_type 扩展 API。
F14ValueMap / F14NodeMap / F14VectorMap：分别继承 F14BasicMap 对应 Policy 特化。
F14FastMap：编译期 conditional_t<sizeof(pair<K const, V>) < 24, F14ValueMap, F14VectorMapImpl>，小对象走 Value 策略（cache 友好），大对象走 Vector 策略（避免 chunk 内拷贝大对象）。
F14HashToken（F14Table.h）：持有 HashPair（processed hash + tag），由 prehash() 产生，传入 find(token, key) 跳过重复哈希计算。
F14HashedKey<Key, Hasher, KeyEqual>：预计算哈希的 key 包装，可隐式转换为 key，实现异构查找的零开销传递。

关键算法

上文已覆盖 SIMD tag probing 与 chunk 溢出模型的核心机制。以下补全查找、插入、删除、rehash 的完整路径。

查找（`findImpl`）

计算 hp = splitHash(computeKeyHash(key))，得到 (position, tag)。
index = position，step = 2 * tag + 1（奇数步长保证与 2 的幂 chunk 数互质，形成双哈希探测）。
进入循环（最多 chunkCount() 次）：
- chunk = chunkAt(index % chunkCount())
- SIMD 广播 tag，_mm_cmpeq_epi8 比较 chunk 的 16 字节 tag 数组，_mm_movemask_epi8 取匹配掩码
- 遍历每个匹配位 i：若 keyEqual(key, chunk.item(i).key) 命中则返回 ItemIter{chunk, i}
- 关键快速退出：若 chunk->outboundOverflowCount() == 0，说明没有 key 因为该 chunk 满而溢出到其他 chunk，不可能在后续 chunk 找到，直接 break
- 否则 index += step，继续探测下一个 chunk

期望探测长度：命中 1.041 个 chunk，未命中 1.275 个 chunk（p99 ≤ 4）。

插入（`tryEmplaceValueImpl`）

先执行查找，若 key 已存在则返回 {existing, false}。
reserveForInsert()：若 size + 1 > capacity，触发 rehash。增长策略为原容量 × 1.40625，向上取到 chunk 容量边界。
从 desired chunk 开始找第一个有空位的 chunk：若 desired chunk 已满，递增 outboundOverflowCount，步进到下一个 chunk（与查找相同的 step），找到空位后设置 hostedOverflowCount。
chunk->setTag(itemIndex, tag)，insertAtBlank 执行 placement new。若构造函数抛出异常，eraseBlank 清除 tag 并回滚 overflow 计数。

删除（`eraseImpl`）

destroyItem 销毁元素（F14Value 直接析构；F14Node 析构后释放堆节点；F14Vector 空操作）。
clearTag 清除该 slot 的 tag 位。
overflow 回滚：若 hostedOverflowCount != 0，从该 key 的 desired chunk 沿探测路径回溯，逐 chunk 递减 outboundOverflowCount，最终在被删元素所在 chunk 递减 hostedOverflowCount。
更新 packedBegin（若被删元素恰好是 begin）。

Rehash（`rehashImpl`）

分配新 chunk 数组（beforeRehash），初始化所有 chunk tag 为零。
创建 fullness[] 数组（每 chunk 一字节，记录已填入元素数，栈上 ≤ 256 chunk 用栈缓冲区）。
从最高 chunk 向最低遍历旧表：
- 若 hostedOverflowCount == 0：所有元素在 preferred chunk，直接用旧 (chunkIndex, tag) 作为 HashPair 调用 allocateTag（避免重算哈希）。
- 否则：必须重算 splitHash(computeItemHash(item)) 得到新 HashPair。
allocateTag(fullness, hp) 按探测链找到有空位的 chunk（复用插入逻辑），moveItemDuringRehash 移动（或指针转移）元素到新位置。
单 chunk → 单 chunk 的优化：无需 probe，线性扫描 occupied slot 逐个搬移。
失败回滚：SCOPE_EXIT 在 success == false 时恢复 chunks_ 和 chunkShift，afterRehash 释放失败的分配。

ABI 约束

Folly F14 不承诺任何跨版本 ABI 稳定性——它是纯头文件模板库，所有容器均在用户编译单元中实例化。以下是关键的 ABI 相关约束：

跨编译单元一致性：F14Table.cpp 中的 F14LinkCheck<getF14IntrinsicsMode()>::check() 会触发链接失败，如果不同编译单元使用了不同的 SIMD/CRC 编译标志（例如一个单元启用 SSE4.2 而另一个没有）。这是有意为之的防御措施，防止在同一个程序中混用不同 chunk 布局的实例化。
对象布局随模板参数变化：sizeof(F14Chunk<Item>)、kCapacity、kChunkStride 全部依赖 sizeof(Item) 和 alignof(Item)。sizeof(Item) == 4 时 kCapacity = 12（一个 cache line），sizeof(Item) == 16 时 kAllocatedCapacity = 15（含 padding）。用户升级 value 类型的大小会静默改变内部布局。
PackedSizeAndChunkShift：64 位平台上将 size 和 chunkShift 打包进一个 uint64_t，低 8 位存 chunkShift，高 56 位存 size。32 位平台使用 UnpackedSizeAndChunkShift（两个字段独立存储）。sizeof(F14Table) 在两种平台不同。
F14FastMap 的编译期选择：sizeof(pair<Key const, Mapped>) < 24 的阈值在 Folly 版本间可能调整。不同的编译器或目标平台对 pair 的布局可能不同，导致同一个类型在不同编译环境中选择不同策略。
无 .so 级别符号导出：除 F14Table.cpp 中的 F14LinkCheck 和 ASAN/debug 辅助函数外，所有代码均为内联模板。不同 Folly 版本之间不存在共享库级别的兼容性。

异常安全

F14 提供基本异常安全保证（basic exception guarantee）：操作要么成功，要么抛出异常后容器处于合法但未指定的状态。以下是各关键路径的异常处理策略：

元素构造失败（插入路径）

insertAtBlank 在调用 constructValueAtItem 前已设置好 tag，使用 catch_exception 包裹构造调用。若构造抛出异常，eraseBlankCold 被调用：清除 tag，回溯探测链修正 outboundOverflowCount 和 hostedOverflowCount。
对于 F14ValueMap，这意味着 chunk 内可能有脏数据（已清除 tag 但 slot 内存未清理），但逻辑上该 slot 已被正确标记为空。
对于 F14NodeMap，constructValueAtItem 内部有 ScopeGuard：若堆上 AllocTraits::construct 失败，立即释放已 allocate 的节点内存。

Rehash 迁移失败

rehashImpl 使用 SCOPE_EXIT 保护：分配新 chunk 数组后，若迁移过程中抛出异常（某个元素的移动构造抛出），success 保持 false，SCOPE_EXIT 将 chunks_ 恢复为旧指针，afterRehash 释放新分配的 chunk 数组。
关键限制：对于 F14ValueMap，已移动到新表的元素无法回移（移动语义不可逆）。异常发生时，新表中已迁移的元素和旧表中未迁移的元素都处于合法状态，但整体内容可能不完整。源码注释明确说明了这一点："the current table is at a valid state at all points for policies in which non-trivial values are owned by the main table (F14Node and F14Value)"。

析构与 `clear()`

clear() 和 reset() 均为 noexcept，逐 chunk 逐 slot 调用 destroyItem。F14ValueMap 和 F14NodeMap 的 destroyItem 均声明为 noexcept（通过 complainUnlessNothrowDestroy 的 [[deprecated]] 警告在编译期提示用户将析构函数标记为 noexcept）。
F14VectorMap::destroyItem 是空操作（索引无需析构）。

`swap()`

kSwapIsNoexcept 要求 allocator is_always_equal 且 Hasher/KeyEqual 可 noexcept swap。满足条件时 swap 为 noexcept。

iterator / reference invalidation

操作	F14ValueMap / F14ValueSet	F14NodeMap / F14NodeSet	F14VectorMap / F14VectorSet
`insert` / `emplace`（无 rehash）	所有引用和迭代器有效	所有引用和迭代器有效	所有引用和迭代器失效（value vector 可能扩容）
`insert` / `emplace`（触发 rehash）	所有引用和迭代器失效（元素被移动到新 chunk）	所有引用和迭代器有效（仅移动指针）	所有引用和迭代器失效
`erase(iter)`	被删元素的引用/迭代器失效；其余元素全部失效（eraseBlank 修正 overflow 时可能移动 slot 内容）	被删元素的引用/迭代器失效；其余引用有效，迭代器有效	被删元素及尾部元素的引用/迭代器失效（value vector 使用 swap-and-pop）
`operator[]` / `at()`（触发插入）	同 `insert`	同 `insert`	同 `insert`
`reserve()` / `rehash()`	全部失效	全部有效	全部失效
`clear()` / `reset()`	全部失效	全部失效	全部失效
`swap()`	两侧独立迭代器跟随各自容器	同左	同左

关键差异来源：

F14ValueMap 的元素存储在 chunk 内，eraseBlank 需要修正 overflow 链，但不会在 chunk 之间移动元素。然而，packedBegin（begin 迭代器的内部表示）在 erase 后可能需要调整——adjustSizeAndBeginBeforeErase 会在被删元素恰好是 begin 时向前推进到下一个 occupied slot。这意味着 begin 迭代器的值会变，但指向同一个元素的其他迭代器不受影响。
F14NodeMap 的 chunk 内只存指针（Item = pointer），moveItemDuringRehash 执行 new (dst) Item{std::move(src)}; src = nullptr，值本身不移动，所以引用稳定。
F14VectorMap 的 values_ 是连续数组，constructValueAtItem 直接在 values_[size] 追加，触发扩容时 transfer 会移动所有值，导致全部引用失效。删除使用逻辑上的 swap-and-pop（beforeClear → destroy）。
ASAN 模式下，F14 会在每次插入前以 1/size() 的概率触发 spurious rehash（debugModeSpuriousRehash），主动暴露依赖引用稳定性的 bug。

性能模型

上文已给出"tag 和 value 同 chunk"这一核心收益。以下补充完整的性能模型。

Cache 行为

单次查找的内存访问：SIMD tag 比较在第一个 cache line（16 字节 tag + control）完成。若 tag 匹配，value 就在同一 chunk 的后续 cache line（通常紧邻 tag），无需额外 cache miss。对比 SwissTable：ctrl 数组和 slot 数组分离，ctrl 命中后需额外加载 slot 的 cache line。
chunk stride：sizeof(Item) == 8 时 kChunkStride = 128（2 个 cache line），sizeof(Item) == 16 时 kChunkStride = 256（4 个 cache line）。当 stride > 64 字节时，findImpl 会在 SIMD 比较前预取 chunk 的第二个 cache line（prefetchAddr(chunk->itemAddr(8))）。

负载因子与探测效率

单 chunk 表（≤ 14 元素）：capacity 可达 kCapacity（100% 填满），无需 overflow 探测。
多 chunk 表：kDesiredCapacity = kCapacity - 2，即 12/14 ≈ 85.7%。实际 max_load_factor 固定为 1.0，但 reserve 计算出的 capacity 保证每个 chunk 平均不超过 kDesiredCapacity 个"期望"元素。
期望探测长度（源码注释数据，kDesiredCapacity / kCapacity = 12/14）：
- 命中查找：期望 1.041 个 chunk，99% 在前 3 个 chunk 内命中
- 未命中查找 / 插入探测：期望 1.275 个 chunk，p99 ≤ 4 个 chunk

Overflow 机制的性能影响

outboundOverflowCount 和 hostedOverflowCount 是 4-bit / 8-bit 饱和计数器。当两者均为零时，查找可以立即终止（快速退出），这是绝大多数情况（高命中率时 > 95% 的 chunk 无 overflow）。
溢出链长度等于探测长度。每多探测一个 chunk，额外开销是一次 SIMD load + compare + movemask + branch，约 3-5 ns（x86-64）。

哈希质量要求

非 avalanching hasher（如 std::hash<int> 的 identity 映射）会被 splitHashImpl 的 CRC32 / 128-bit mixer 修复。这增加约 2-3 ns 的哈希计算开销，但保证 tag 的 7 bit 熵均匀分布。
Avalanching hasher（如 std::hash<std::string> 使用 MurmurHash2 / CityHash）直接取高位，零额外开销。
F14HashToken / prehash 机制可将哈希计算从热路径完全移除（适用于批量查找场景）。

内存开销

空 F14 表仅 sizeof(F14Table) ≈ 16 字节（一个空指针 + packed size/shift）。对比空 std::unordered_map ≈ 56 字节（libstdc++）。
每个 chunk 的固定开销：16 字节 tag/control 数组。对 sizeof(Item) == 8 的典型 map（pair<int,int>），总 chunk 大小 = 16 + 14 × 8 = 128 字节 = 2 cache lines，overhead ≈ 16 / 128 = 12.5%。
F14NodeMap 额外有每个元素的堆分配开销（sizeof(Value) + allocator overhead），但 chunk 本身更小（指针 8 字节 vs value 大小）。
F14VectorMap 的 chunk 开销最省（uint32_t 索引 = 4 字节/slot），但需要单独的 values_ 数组。

libstdc++ vs libc++ vs MSVC

以下对照 F14、SwissTable（Abseil absl::flat_hash_map）以及三家标准库 unordered_* 的核心差异：

维度	F14（Folly）	SwissTable（Abseil）	libstdc++ `unordered_*`	libc++ `unordered_*`	MSVC `unordered_*`
探测方式	Chunk-based SIMD tag 探测 + double-hashing 溢出	连续 ctrl 数组 SIMD 探测 + 二次探测	开链法（separate chaining）	开链法	开链法
探测粒度	14 slots/chunk（SSE2 16 字节比较）	16 slots/group（SSE2）/ 32（AVX2）	每桶 1 个链表节点	同左	同左
负载因子	固定 1.0（实际 ~85.7% 有效）	可调（默认 87.5% = 7/8）	可调（默认 1.0）	可调（默认 1.0）	可调（默认 1.0）
稳定性	Value：不稳定；Node：引用稳定	不稳定	稳定（链表节点独立）	稳定	稳定
空表大小	~16 字节	~56 字节	~56 字节	~48 字节	~32 字节
每元素 overhead	Value: tag 数组摊薄（~1.14 B）；Node: 指针 + 堆节点	ctrl 数组 1 B/slot + slot padding	next 指针 + bucket 数组	next 指针 + bucket 数组	next 指针 + bucket 数组
SIMD 加速	SSE2 / NEON / SVE bridge	SSE2 / NEON	无	无	无
哈希修复	非 avalanching 时自动 CRC32 / mixer	无（依赖用户哈希质量）	`__is_fast_hash` 检测	CityHash / MurmurHash2	无
异构查找	`FollyHasher`/`FollyKeyEqual` transparent	`absl::Hash` transparent	C++20 `is_transparent`	C++20 `is_transparent`	C++20 `is_transparent`
迭代器	`forward_iterator_tag`（Value/Node），反向迭代仅 Vector	`forward_iterator_tag`	`forward_iterator_tag`	`forward_iterator_tag`	`forward_iterator_tag`
rehash 策略	容量 × 1.40625 增长	2× 增长	素数表增长	素数表增长	2× 增长

F14 相对 SwissTable 的优势：tag + value 同 chunk 减少 cache miss；空表极小；溢出计数器实现快速退出。

SwissTable 相对 F14 的优势：更大的 SIMD 探测组（16/32 vs 14）；ctrl 和 slot 的分离布局在某些访问模式下更友好；无 overflow 计数器，逻辑更简单。

标准库的优势：引用/迭代器稳定性最强（链表节点永不移动）；ABI 稳定；可调试性最好。

标准库的劣势：链表节点的指针 chasing 导致大量 cache miss；bucket 数组额外内存开销；探测效率最低。

最小复现代码

cpp

#include <folly/container/F14Map.h>

int main() {
  folly::F14ValueMap<int, int> table;
  table.emplace(1, 42);
  return table.find(1)->second;
}

编译 / 反汇编 / benchmark 证据

编译要求

必需 SIMD 支持：x86-64 需 SSE2（GCC/Clang 默认开启）；ARM 需 NEON。若无 SIMD 支持，FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE 为 false，F14 退化为 F14MapFallback（std::unordered_map wrapper）。
CRC 指令可选：FOLLY_F14_CRC_INTRINSIC_AVAILABLE 启用时使用硬件 CRC32（x86 SSE4.2 -msse4.2，ARM -march=armv8-a+crc）加速非 avalanching hasher 的位混合；不可用时退回 128-bit 乘法 mixer。
链接一致性检查：F14Table.cpp 中的 F14LinkCheck 确保所有编译单元使用相同的 SIMD 模式。混合标志（如 -msse4.2 和无 -msse4.2）会导致链接失败。

典型反汇编路径（x86-64 SSE2，`F14ValueMap<int,int>` 的 `find` 热路径）

asm

; splitHashImpl — avalanching hasher 时的 tag 提取（几乎免费）
mov    rax, rdi
shr    rax, 0x38          ; tag = hash >> 56
or     al, 0x80           ; tag |= 0x80
; position = hash（低位直接作为 chunk index）

; findImpl — SIMD tag 比配
movd   xmm1, eax          ; needle = broadcast(tag)
pshufb xmm1, xmm_zero     ; 广播到 16 字节
movdqa xmm0, [rcx]        ; 加载 16 字节 tag 数组（chunk 起始）
pcmpeqb xmm0, xmm1       ; 逐字节比较
pmovmskb eax, xmm0        ; 取 16-bit 掩码
and    eax, 0x3FFF         ; 屏蔽 tag[14] 和 tag[15]
bsf    ecx, eax           ; 找第一个匹配位（ctz）
; → 若 eax == 0 且 outboundOverflowCount == 0，直接返回 miss
; → 否则逐个检查 key 匹配

Benchmark 对照（参考数据，来自 Folly 官方 `HashMapsBench.cpp` 和独立复现）

测试条件：std::string key（平均 20 字节），随机查找，单线程，x86-64（SSE4.2 + CRC32）。

操作	F14ValueMap	F14NodeMap	`absl::flat_hash_map`	`std::unordered_map`（libstdc++）
查找命中（10 万元素）	~25 ns	~30 ns	~28 ns	~50 ns
查找未命中	~20 ns	~25 ns	~22 ns	~35 ns
插入	~80 ns	~100 ns	~75 ns	~120 ns
遍历（per element）	~3 ns	~5 ns	~3 ns	~15 ns

关键观察：

F14ValueMap 在查找场景下比 std::unordered_map 快 ~2x，主要收益来自 SIMD tag 过滤（避免逐个 key 比较）和 tag+value 同 cache line（减少 cache miss）。
F14NodeMap 比 F14ValueMap 慢约 15-20%（需要额外的指针解引用到堆上 value），但比 std::unordered_map 仍然快约 40%。
遍历性能差异最大：F14 的 chunk 遍历是线性的 cache-line 扫描，unordered_map 的链表遍历每节点一次 cache miss。
absl::flat_hash_map 与 F14ValueMap 性能接近，F14 在大表场景（> 10 万元素）因 overflow 计数器的快速退出略有优势。

注意：以上 benchmark 数据为近似参考值，实际性能取决于 key 类型、哈希函数质量、CPU 微架构和工作集大小。Folly 源码 folly/container/test/HashMapsBench.cpp 提供了可复现的基准测试。

F14 哈希表：Meta 自研的 Chunk-based SIMD 哈希表

Chunk-based 布局

SIMD 探测

与 SwissTable 的对比

用户 API

标准语义

对象布局

核心源码路径

核心类 / 函数

关键算法

查找（`findImpl`）

插入（`tryEmplaceValueImpl`）

删除（`eraseImpl`）

Rehash（`rehashImpl`）

ABI 约束

异常安全

元素构造失败（插入路径）

Rehash 迁移失败

析构与 `clear()`

`swap()`

推荐实践

iterator / reference invalidation

性能模型

Cache 行为

负载因子与探测效率

Overflow 机制的性能影响

哈希质量要求

内存开销

libstdc++ vs libc++ vs MSVC

最小复现代码

编译 / 反汇编 / benchmark 证据

编译要求

典型反汇编路径（x86-64 SSE2，`F14ValueMap<int,int>` 的 `find` 热路径）

Benchmark 对照（参考数据，来自 Folly 官方 `HashMapsBench.cpp` 和独立复现）

cpplings 练习入口

F14 哈希表：Meta 自研的 Chunk-based SIMD 哈希表 ​

Chunk-based 布局 ​

SIMD 探测 ​

与 SwissTable 的对比 ​

用户 API ​

标准语义 ​

对象布局 ​

核心源码路径 ​

核心类 / 函数 ​

关键算法 ​

查找（findImpl） ​

插入（tryEmplaceValueImpl） ​

删除（eraseImpl） ​

Rehash（rehashImpl） ​

ABI 约束 ​

异常安全 ​

元素构造失败（插入路径） ​

Rehash 迁移失败 ​

析构与 clear() ​

swap() ​

推荐实践 ​

iterator / reference invalidation ​

性能模型 ​

Cache 行为 ​

负载因子与探测效率 ​

Overflow 机制的性能影响 ​

哈希质量要求 ​

内存开销 ​

libstdc++ vs libc++ vs MSVC ​

最小复现代码 ​

编译 / 反汇编 / benchmark 证据 ​

编译要求 ​

典型反汇编路径（x86-64 SSE2，F14ValueMap<int,int> 的 find 热路径） ​

Benchmark 对照（参考数据，来自 Folly 官方 HashMapsBench.cpp 和独立复现） ​

cpplings 练习入口 ​

F14 哈希表：Meta 自研的 Chunk-based SIMD 哈希表

Chunk-based 布局

SIMD 探测

与 SwissTable 的对比

用户 API

标准语义

对象布局

核心源码路径

核心类 / 函数

关键算法

查找（`findImpl`）

插入（`tryEmplaceValueImpl`）

删除（`eraseImpl`）

Rehash（`rehashImpl`）

ABI 约束

异常安全

元素构造失败（插入路径）

Rehash 迁移失败

析构与 `clear()`

`swap()`

推荐实践

iterator / reference invalidation

性能模型

Cache 行为

负载因子与探测效率

Overflow 机制的性能影响

哈希质量要求

内存开销

libstdc++ vs libc++ vs MSVC

最小复现代码

编译 / 反汇编 / benchmark 证据

编译要求

典型反汇编路径（x86-64 SSE2，`F14ValueMap<int,int>` 的 `find` 热路径）

Benchmark 对照（参考数据，来自 Folly 官方 `HashMapsBench.cpp` 和独立复现）

cpplings 练习入口