面向推荐系统参数服务器的稀疏哈希表:设计空间与训练、推理场景下的取舍分析
#摘要
推荐模型的 sparse 参数以 FID -> embedding 的形式存放在参数服务器(Parameter Server,PS)的哈希表中,大模型的 key 数达数百亿至数千亿。已有讨论往往把"哪种哈希表最好"当作与场景无关的问题,但训练 PS 与推理 PS 的负载几乎相反:前者写密集、key 集合持续变化,后者读密集、对尾延迟敏感且数据按副本复制。本文首先刻画两类场景的负载差异;随后提出一组八个评价维度,并据此对九类哈希表结构及十余个常用 C++ 库进行归类;接着给出索引内存占比、批量查找延迟与指纹误命中率三个简单的分析模型;最后分别对训练 PS 与推理 PS 给出候选方案与选型建议。分析表明:训练侧的首要约束是并发原地更新、不停服扩容与 dump,索引内存仅占总内存的约 1%~3%;推理侧的首要约束是 P99 延迟与跨分片版本一致,且由于 payload 量化与副本复制,压缩索引的收益显著高于训练侧。
关键词:参数服务器;embedding 表;哈希表;推荐系统;并发数据结构
#1 引言
在工业推荐系统中,sparse 特征(用户 ID、物品 ID、交叉特征等)经哈希后得到 64 位特征 ID(FID),每个 FID 对应一个 embedding 向量。大模型的 key 数达数百亿至数千亿,参数总量可达数 TB 至数十 TB,存放在参数服务器中,由哈希表完成从 FID 到参数的映射。哈希表的内存开销、查找延迟和并发能力因此直接决定了 PS 的成本与性能。
通用哈希表的研究与工程实现已相当成熟,例如 Swiss Table [4]、F14 [5]、Cuckoo 哈希 [6][7] 和最小完美哈希 [9][10][11]。然而,这些结构的评测通常基于通用负载,其结论不能直接迁移到 PS:PS 的 value 远大于 key,写入模式与一致性要求也与通用 KV 场景不同。更重要的是,训练 PS 与推理 PS 对同一张表提出了几乎相反的要求,脱离场景讨论"最优哈希表"容易得出误导性的结论。
本文的贡献如下:
- 负载刻画:从读写比例、key 集合动态性、value 构成、更新方式、延迟、一致性、内存与持久化八个方面,对比训练 PS 与推理 PS 的负载特征(第 3 节)。
- 设计空间:提出八个评价维度,并将常见哈希表结构归为九类,同时给出主流 C++ 库的归类(第 4 节与附录 A)。
- 分析模型:给出索引内存占比、批量查找延迟和指纹误命中率的简单模型,用于定量说明不同场景下的取舍(第 5 节)。
- 选型建议:分别对训练 PS 与推理 PS 给出候选方案与选型建议,并以 Monolith [1] 和 NeighborHash [2] 作为两个场景的案例(第 6、7、8 节)。
需要说明的是,本文是基于公开文献与开源实现的分析性综述,未进行系统性实验评测;文中数字均为量级估计,实际选型应结合具体负载实测。
#2 背景与问题定义
#2.1 参数服务器中的 sparse 参数
PS 通常按 FID 的哈希值将参数分片到多台服务器上。训练时,worker 按 mini-batch 向 PS 拉取(pull)所需的 embedding,完成前向和反向计算后推送(push)梯度,由 PS 端的 optimizer 原地更新参数。推理时,在线服务按请求从推理 PS 批量查询 embedding;推理 PS 的数据来自训练 PS 的增量同步或全量快照。
#2.2 问题定义
设某分片上的 key 集合为,。每个 key 对应的参数占 字节,索引结构为每个 key 平均分摊 字节(包括空槽开销)。哈希表需要支持以下操作:
- :查找 key,返回参数或 miss;
- :插入或覆盖;
- :在互斥保护下对参数原地执行读改写,例如 optimizer 更新;
- :删除,用于淘汰;
- :遍历全部条目,用于 dump 与迁移。
对于一次包含 个 key 的批量查询,我们关注其总延迟,尤其是尾延迟。
#3 负载刻画:训练 PS 与推理 PS
两类场景共有的约束是:大模型的 key 数达数百亿至数千亿(单个分片上也有数亿至数十亿);value 远大于 key,总内存以 payload 为主;查询以批量点查为主;miss 必须有明确语义,误把一个 key 当作另一个会读到错误的参数。在此之上,两者的差异见表 1。
表 1 训练 PS 与推理 PS 的负载特征对比
| 维度 | 训练 PS | 推理 PS |
|---|---|---|
| 读写比例 | 每个 step 都有 pull 和 push,写和读一样多 | 读远多于写,写只来自训练侧的同步 |
| key 集合 | 新 key 持续出现,要准入过滤;不活跃的 key 要淘汰 | 跟随训练侧变化;冷冻模型的 key 集合完全固定 |
| value 内容 | embedding + optimizer 状态(如 Adagrad、Adam 的累积量) | 只有 embedding,常做量化(FP16、INT8) |
| 更新方式 | optimizer 原地读改写,同一个 key 可能被并发写 | 分钟级增量原地写入,或者小时级、天级整版切换 |
| 延迟要求 | 看吞吐,单次 pull 的延迟可被流水线掩盖 | 看 P99,直接影响线上请求 |
| 一致性 | 异步训练本身容忍一定的陈旧和不一致 | 同一请求最好读到同一代数据,否则效果下降 |
| 内存 | 每个 key 只存一份,optimizer 状态使 payload 更大 | 每份数据要乘上副本数;payload 小,索引占比反而更高 |
| 持久化 | 要定期 dump checkpoint,最好不停训练 | 从 checkpoint 或增量流加载,扩副本要快 |
由表 1 可以得到两个观察:
- 观察 1:索引内存在两类场景中的分量不同。训练侧 payload 包含 optimizer 状态,索引占比很小;推理侧 payload 经量化后变小,且总内存随副本数线性增长,压缩索引的绝对收益更大(定量分析见第 5.1 节)。
- 观察 2:"写"在两类场景中的含义不同。训练侧是高频、细粒度、可能并发的原地更新;推理侧的写可以批量化,甚至可以不在原表上写,而以整表替换的方式完成。后者使只读结构成为可行选项。
#4 设计空间
#4.1 评价维度
我们用以下八个维度评价一种哈希表结构或实现:
- C1 索引内存:每个 key 分摊的索引开销,包括空槽。
- C2 查找跳数:一次查找所需的相互依赖的随机访存次数。
- C3 并发模型:不支持并发、分段加锁、细粒度锁,或读者无锁。
- C4 原地修改:能否在互斥保护下直接修改 value。有的并发表只允许整体替换 value,对大 value 不友好。
- C5 指针稳定:插入或扩容后,已取得的 value 指针是否仍然有效。
- C6 扩容方式:整表重建、按分片重建或渐进迁移。
- C7 erase 与遍历:是否支持并发 erase,以及能否在并发写入下稳定遍历。
- C8 key 判定:存储完整 key,或只存储指纹。后者存在误命中。
#4.2 结构分类
表 2 按结构将常见方案归为九类。
表 2 哈希表结构分类
| 结构 | 代表实现 | C1 索引内存 | C2 查找跳数 | 写入与扩容 |
|---|---|---|---|---|
| 链式桶 | std::unordered_map、tbb::concurrent_hash_map | 高,每个元素一个节点 | 2~3 跳,cache 不友好 | 插入简单,指针稳定 |
| 扁平开放寻址 | absl Swiss Table、folly F14、Boost flat、tsl::robin_map | 中,空槽按整个槽计 | 通常 1 次 cache miss | 扩容整表搬迁,指针不稳定 |
| 稀疏分组 | Google sparsehash、tsl::sparse_map | 低,空槽约 1~3 bit | 组头 → 元素,约 2 跳 | 插入需在组内搬移元素,难以并发 |
| Cuckoo | libcuckoo [6]、Monolith [1] | 负载可达 90% 以上 | 最多 2 个位置,延迟稳定 | 踢出链带来插入尾延迟,表满时重建 |
| 数组内链接 | NeighborHash [2]、ska::bytell_hash_map [20]、emhash7 [21] | 无独立节点;NeighborHash 为 16 B 槽,负载 80% 以上 | 沿数组内的链跳转;NeighborHash 约 1.1 条 cache line | 不支持并发写(NeighborHash 开源版支持单写者,容量固定) |
| 邻域哈希 | Hopscotch [23]、tsl::hopscotch_map [22] | 每个桶附带一个邻域 bitmap | 只扫描 home 桶附近的一个邻域,通常 1 条 cache line | 插入时可能要把空位"跳"进邻域;跳不进时扩容 |
| 路由与数据分离 | 两级表 | 一级每槽数字节,只存指纹 | 路由 → 数据 → 向量,最多 3 跳 | 追加写;扩容只重建路由 |
| 静态完美哈希 | CHD [9]、PTHash [10]、RecSplit [11] | 每个 key 2~4 bit | 1~2 次访存 | 不能插入,只能整体重建 |
| GPU 表 | HierarchicalKV [12] | 受显存限制 | warp 并行,吞吐极高 | 批量插入,内建淘汰 |
下面简述其中四类在推荐场景下特点鲜明的结构。
扁平开放寻址。 Swiss Table [4]、F14 [5] 与 Boost 的 unordered_flat_map 采用相同的思路:槽位分组,每组附带一小块元数据,每个槽存 1 字节的哈希片段;查找时以 SIMD 一次比较整组,仅对片段匹配的槽比较完整 key。该类结构通常只需 1 次 cache miss。其节点变体(absl::node_hash_map、F14NodeMap)以多一次分配和一跳为代价换取指针稳定;数组变体(F14VectorMap、ankerl::unordered_dense)将 value 连续存放,遍历效率高,适合 dump。该类结构本身不支持并发,在 PS 中通常以分片加锁的形式使用,或作为推理侧的只读表。
稀疏分组。 底层数组被划分为若干组,每组以一个 64 位 bitmap 标记被占用的槽,仅为存在的元素分配紧凑数组;第 个槽在紧凑数组中的偏移为。空槽几乎不占内存,因而可以在低负载下运行以缩短探测链;代价是插入与删除需要在组内搬移元素,迭代器和引用随之失效,难以支持并发原地更新。
数组内链接。 这一类把冲突的元素串成链,但链节点就是表数组里的槽,而不是单独分配的节点,因此兼有链式桶"只沿链查找"和开放寻址"无额外分配"的优点。ska::bytell_hash_map [20] 每个槽配 1 字节元数据,其中记录到链上下一个元素的跳转距离(取自一张预设的距离表);emhash7 [21] 在槽内存储链上下一个元素的下标,无需墓碑,删除频繁时性能也稳定,并支持很高的负载因子;NeighborHash [2] 采用 coalesced chaining,并通过把占用他人 home 桶的记录迁走、在 cache line 内双向探测,让一条链尽量落在同一条 cache line 内(第 7.3 节)。与之相近的还有 Hopscotch 哈希 [23]:它不维护链,而是保证每个 key 都位于其 home 桶附近 个槽的"邻域"内,每个桶用一个 bitmap 标记邻域中哪些槽属于自己,查找只需扫描一个邻域。这几种结构的出发点都是把一次查找限制在很少的 cache line 内,但都不支持并发写。
路由与数据分离。 两级表将热路径上的路由信息压缩到极小:一级表按 key 的哈希做开放寻址,只存短指纹与二级位置,每槽仅数字节;二级表按 block 追加写入,参数内联,大向量再经指针指向内存池或 SSD。扩容时只需重建一级路由,二级数据不动;为此完整 key 需另行保存,可置于更廉价的存储中。该结构的优点是索引极省、插入路径稳定、扩容几乎不中断服务;代价是指纹误命中(第 5.3 节)和更多的依赖访存(第 5.2 节)。
#5 分析模型
#5.1 索引内存占比
每个 key 的总内存为,索引占比为
训练侧的 payload 为,其中 为向量维度, 为每个元素的字节数, 为 optimizer 状态的倍数(Adagrad 取,Adam 取)。取、FP32、Adagrad,得 字节。此时 字节对应, 字节对应。即使把索引压缩到原来的五分之一,总内存也只减少约 2.4%。
推理侧去掉 optimizer 状态并量化到 FP16,同样 时 字节, 字节对应。此外,推理侧总内存为,其中 为副本数。以 key 数(一千亿)的大模型为例,把 从 16 字节降到 3 字节,每份完整数据可节省 字节,约 1.3 TB;若,总计约 13 TB。这与观察 1 一致:压缩索引在推理侧的收益显著高于训练侧。
#5.2 批量查找延迟
设一次批量查询包含 个 key,每个 key 需要 次相互依赖的随机访存,单次访存延迟为。若逐个 key 串行查找,总延迟约为
若采用 AMAC [3] 或协程方式交错执行多个 key 的查找,使至多 个访存同时在途,则总延迟受限于内存级并行度(memory-level parallelism,MLP):
由此可见:(1) 在不做交错的情况下,延迟与 成正比,多跳结构(如两级表的)显著慢于单跳结构;(2) 交错可以按 的倍数掩盖延迟,但总访存次数 不变,因此 仍决定了吞吐上限。仅对下一个 key 的首跳做预取,只能掩盖依赖链的第一跳;对多跳结构,需要为每一跳都发出预取。
#5.3 指纹误命中率
设内存中只存储 位指纹,一次查询需要与 个候选条目比较指纹。假设指纹均匀分布,一次查询中出现误命中的概率约为
若每天有 次查询的目标 key 不在表中,期望误命中次数约为。以、、 为例,期望约为 次。也就是说,在数百亿至数千亿 key、高查询量的条件下,31 位指纹每天仍可能产生数十次误命中。误命中会使查询返回另一个 key 的参数,若下游按 key 的配置解释该参数(例如向量长度不同),还可能引发更严重的错误。存储完整 key 可以使;若坚持只存指纹,至少应选择足够大的,并在读取 payload 时增加校验。
#6 训练 PS 的分析
#6.1 核心约束
- 并发原地更新:同一 key 可能被多个 worker 同时 push,optimizer 需在互斥保护下原地读改写(C3、C4)。由于写与读一样频繁,RCU、双 buffer 等读者无锁方案的收益有限。
- 不停服扩容:新 key 持续进入,扩容不可避免(C6)。可选做法包括:分片后逐片扩容;渐进式 rehash,新旧两表同时查询,后台迁移;或者将索引与数据分离,扩容只重建索引。
- erase 与遍历:淘汰需要 erase,checkpoint 需要在训练进行中 dump(C7)。常见做法包括:fork 进程利用写时复制获取快照;逐分片加锁 dump;或者为条目附带版本号,只取不晚于快照版本的值。
- 索引内存为次要因素:由第 5.1 节, 仅约 1%~3%;准入过滤、淘汰、下沉 SSD 对总内存的影响要大一个数量级。
#6.2 候选方案
表 3 训练 PS 的候选方案
| 方案 | 并发与原地修改 | 扩容 | 评价 |
|---|---|---|---|
phmap::parallel_flat_hash_map [15] | 每片一把锁,modify_if 等接口在锁内修改 | 每片单独扩容 | 推荐:将"分片 + 锁"实现为现成组件 |
boost::concurrent_flat_map [16] | 每组一把读写锁,只能用 visit 传 lambda 在锁内访问 | 整表扩容 | 推荐:visit 接口契合 optimizer 更新 |
| libcuckoo [6] / Monolith [1] | 桶级细粒度锁,update_fn 在锁内修改 | 表满时扩容 | 推荐:成熟,存完整 key;高负载时有插入尾延迟 |
| 两级表 | 1 bit 锁嵌在槽与条目中,锁粒度到单个 key | 只重建路由,几乎不停 | 内存紧张、扩容频繁时适用;需处理指纹误命中 |
tbb::concurrent_hash_map [17] | accessor 获取元素级写锁,语义合适 | 按桶渐进分裂 | 可用,但每个元素一个节点加一把锁,数百亿至数千亿 key 时内存开销过大 |
| HierarchicalKV [12](GPU) | 批量插入与更新 | 内建淘汰 | GPU 训练的首选 |
folly::ConcurrentHashMap [5] | 更新为整体替换 value,不能原地修改 | 分段扩容 | 不适用:大 value 每次更新都需复制 |
folly::AtomicHashMap、tbb::concurrent_unordered_map | 插入与查找无锁,value 的线程安全需自行保证 | — | 不适用:erase 不回收空间或不是并发安全的,难以淘汰 |
| sparse_map、NeighborHash、静态完美哈希 | 不支持并发写,或不支持插入 | — | 不适用 |
#6.3 案例:Monolith 的无冲突 embedding 表
Monolith [1] 指出,许多早期系统先将 ID 哈希到固定大小的表中,使不同 ID 共享同一 embedding,这种冲突会损害模型质量,在热门 ID 与长尾 ID 混杂时尤为明显。为此,Monolith 为每个 ID 分配独立的 embedding,并采用以下设计:
- Cuckoo HashMap:两张子表、,各对应一个哈希函数;插入时若目标位置被占用,则将原 key 踢到其在另一张表中的位置,直至放下为止;查找最多访问 2 个位置。
- 准入过滤:ID 出现足够多次后才分配 embedding,以概率过滤器计数,过滤只出现一两次的长尾 ID。
- 过期淘汰:记录每个 embedding 的最近更新时间,删除长期不活跃的 ID。
- 训练与推理同步:训练 PS 周期性地把有变化的 sparse 参数增量同步到推理 PS,可实现分钟级更新。
后两项设计对应训练侧 key 集合持续变化的需求。Monolith 的重点在于证明"无冲突加实时训练"对模型效果的收益,哈希表本身采用成熟的 Cuckoo 结构,并未在内存上做极致优化。与两级表相比,Cuckoo 存完整 key、判定精确、跳数少,但表满时需重建,插入存在尾延迟;两级表索引更省、扩容只需重建路由,但只存指纹且多一跳。
#7 推理 PS 的分析
#7.1 核心约束
- P99 延迟:一次请求需查询数百至上千个 key。由第 5.2 节,可通过减少(单层扁平表加完整 key,每个 key 约 1 条 cache line 加 1 次 value 解引用)或通过交错执行掩盖延迟;对多跳结构,后者几乎是必需的。
- 更新模式决定表的形态:
- 分钟级原地增量:表需支持边读边写,可采用读者无锁的动态表,或"只读基础表 + 小的动态增量表"的分层结构,查询时先查增量再查基础。
- 小时级或天级整版切换:表可完全只读,按副本滚动切换,读路径无锁且内存最省。
- 跨分片版本一致:一次请求的 key 分布在多个分片上,若各分片不是同一代数据,请求会混用新旧 embedding。整版切换只需在查询协议中携带版本号;原地增量则需要额外的版本机制。
- 索引内存随副本数放大:由第 5.1 节,推理侧压缩索引的收益更大;但正确性优先,只存指纹的方案需要按第 5.3 节选择足够长的指纹并增加校验。
#7.2 候选方案
表 4 推理 PS 的候选方案
| 方案 | 读路径 | 更新方式 | 评价 |
|---|---|---|---|
absl::flat_hash_map、F14、Boost flat、unordered_dense、bytell、emhash7、hopscotch | 无锁(只读) | 整版构建后原子切换指针 | 推荐用于整版切换:实现简单、查找快 |
| NeighborHash [2] | 无锁,配合 AMAC 与 SIMD | 整版切换;开源版支持单写者 | 推荐用于批量只读点查 |
folly::ConcurrentHashMap [5] | 无锁(hazard pointer) | 原地增量,整体替换 value | 推荐用于读多写少的分钟级增量;value 较小时复制代价可接受 |
| 静态完美哈希 + 指纹 | 无锁 | 只能整体重建 | 适用于冷冻模型、内存极紧的场景 |
| sparse_map / sparsehash | 无锁(只读) | 单线程加载 | 适用于 value 很小、内存极紧的场景 |
folly::AtomicUnorderedInsertMap [5] | 无锁 | 只能插入,不能 erase | 适用于一次性构建后只读的表 |
| libcuckoo、phmap、两级表 | 有轻量锁 | 原地增量 | 可用;两级表需补充多跳预取与更长的校验 |
| HierarchicalKV [12](GPU) | warp 并行 | 批量更新 | GPU 推理 |
#7.3 案例:NeighborHash 的批量只读查询
NeighborHash [2] 将索引置于单层扁平数组中,采用 coalesced chaining,并将占用他人 home bucket 的记录迁走,使一个 key 的探测尽量落在同一条 cache line 内。查询侧结合 AMAC [3](为每个 key 维护一个状态机,发出预取后切换到下一个 key)与 SIMD 多 key 并行,以掩盖随机访存延迟。
其开源实现的 benchmark 将 NeighborHash 与 std::unordered_map、absl::flat_hash_map、ankerl::unordered_dense、ska::bytell_hash_map、emhash7、tsl::hopscotch_map,以及作者实现的线性探测与 SIMD 分桶(16×16)两个基线进行了对比,覆盖标量、向量化与多线程几类场景。
该系统完全按推理侧设计:训练 PS 与推理 PS 分离,查询集群不承担训练时的 push 与 optimizer 计算。更新以按副本滚动切换整个版本的方式完成(论文实验中的更新间隔为 15 分钟至 4 小时),查询协议携带分片与版本信息,保证同一请求读到同一代数据。论文报告,不施加一致性约束时约 3% 的结果混用了多个版本的 embedding。这一设计以部分新鲜度为代价,换取了读路径无锁、读写隔离与版本一致。
#8 讨论
#8.1 选型建议
表 5 不同场景下的选型建议
| 场景 | 建议 |
|---|---|
| 训练 PS(CPU) | phmap::parallel_flat_hash_map、boost::concurrent_flat_map 或 libcuckoo,存完整 key;内存紧张时用两级表 |
| 训练 PS(GPU) | HierarchicalKV 一类的 GPU 表 |
| 推理 PS,分钟级增量 | folly::ConcurrentHashMap 等读者无锁的动态表,或"只读基础表 + 动态增量表",配合批量预取 |
| 推理 PS,小时级或天级整版切换 | absl::flat_hash_map、F14 或 NeighborHash 作为只读表,按副本滚动切换,查询携带版本号 |
| 推理 PS,冷冻模型、内存极紧 | 静态完美哈希 + 指纹,或稀疏分组结构 |
#8.2 开放问题
- 分层结构:将不可变的基础表(完美哈希或 NeighborHash)与小型动态增量表组合,有望同时获得只读表的内存与延迟优势和动态表的新鲜度,但增量表的合并策略与一致性语义仍需设计。
- 多跳结构的批量预取:路由与数据分离的结构在扩容与内存上有优势,其查找延迟能否通过 AMAC 式多跳预取逼近单层扁平表,有待实测。
- 正确性与内存的权衡:第 5.3 节表明短指纹在大规模下会产生可观的误命中。如何以最小的内存代价获得可接受的误命中率(例如只在推理侧加长指纹),值得进一步研究。
#8.3 局限性
本文未进行系统性实验,第 5 节的模型忽略了 cache 命中、TLB、NUMA 与内存带宽等因素;各库的特性基于其公开文档与源码的一般描述,可能随版本变化。实际选型应以目标负载下的实测为准。
#9 相关工作
通用哈希表。 Cuckoo 哈希 [7] 以多个候选位置换取最坏情况下常数次的查找,libcuckoo [6] 在其基础上实现了高并发写入。Robin Hood 哈希 [8] 通过平衡探测距离降低查找方差;Hopscotch 哈希 [23] 将每个 key 限制在 home 桶附近的邻域内,使查找只需扫描固定范围。Swiss Table [4] 与 F14 [5] 以分组元数据和 SIMD 比较大幅提升了开放寻址的查找速度。最小完美哈希方面,CHD [9]、RecSplit [11] 与 PTHash [10] 在每个 key 仅数 bit 的空间下支持常数时间查找,但只适用于静态 key 集合。
推荐系统的 embedding 存储。 Monolith [1] 采用无冲突的 Cuckoo 表并结合准入与淘汰,支持实时训练;TFRA [19] 在 TensorFlow 中提供了基于哈希表的动态 embedding;HierarchicalKV [12] 面向 GPU 提供带淘汰的多级哈希表;NeighborHash [2] 针对推理侧的批量只读查询优化了 cache 局部性与访存并行。
访存延迟掩盖。 AMAC [3] 通过为每个查询维护状态机并交错执行,掩盖指针追逐类操作的访存延迟,适用于哈希表探测与链表遍历等场景。
#10 结论
本文从训练 PS 与推理 PS 的负载差异出发,分析了推荐系统 embedding 哈希表的设计空间。结论是:训练侧应优先解决并发原地更新、不停服扩容与 dump,索引内存是次要因素;推理侧应优先解决 P99 延迟与跨分片版本一致,且由于 payload 量化与副本复制,索引内存比训练侧更值得压缩。无论哪一侧,在数百亿至数千亿 key 的规模下,只存短指纹带来的误命中都不可忽视。
#附录 A 常见库速查
表 A1 常见 C++ 哈希表库
| 库 / 类型 | 结构类别 | 并发 | 原地修改 | 指针稳定 | 备注 |
|---|---|---|---|---|---|
std::unordered_map | 链式桶 | 无 | 是 | 是 | 基线 |
absl::flat_hash_map | 扁平开放寻址 | 无 | 是 | 否 | 最大负载 7/8 |
absl::node_hash_map | 扁平开放寻址(存指针) | 无 | 是 | 是 | 每个元素多一次分配 |
folly::F14ValueMap / F14NodeMap | 扁平开放寻址 | 无 | 是 | Node 是 | 每个 chunk 14 个槽 |
folly::F14VectorMap | 扁平索引 + 连续数组 | 无 | 是 | 否 | 遍历快;erase 用最后一个元素填洞 |
boost::unordered_flat_map | 扁平开放寻址 | 无 | 是 | 否 | 15 槽一组 |
ankerl::unordered_dense | Robin Hood 索引 + 连续数组 | 无 | 是 | 否 | 遍历快,代码量小 |
tsl::robin_map | Robin Hood 开放寻址 | 无 | 是 | 否 | |
tsl::sparse_map、sparsehash | 稀疏分组 | 无 | 是 | 否 | 空槽约 1 bit |
phmap::parallel_flat_hash_map | 分片扁平开放寻址 | 每片一把锁 | 是(modify_if 等) | 否 | 可插入自定义 mutex |
boost::concurrent_flat_map | 扁平开放寻址 | 每组读写锁 | 是(visit) | — | 无迭代器,用 visit_all 遍历 |
tbb::concurrent_hash_map | 链式桶 | 元素级读写锁 | 是(accessor) | 是 | 支持并发 erase;内存开销大 |
tbb::concurrent_unordered_map | split-ordered list | 插入与查找无锁 | 自行保证 | 是 | erase 不是并发安全的 |
folly::ConcurrentHashMap | 分段 | 读者无锁,写者每段加锁 | 否,整体替换 | — | 迭代器在并发修改下安全 |
folly::AtomicHashMap | 开放寻址 | 插入与查找无锁 | 自行用原子操作 | 是 | key 只能是整数;erase 不回收空间 |
folly::AtomicUnorderedInsertMap | 开放寻址 | 插入与查找无锁 | 自行用原子操作 | 是 | 固定容量,不能 erase |
libcuckoo cuckoohash_map | Cuckoo | 桶级细粒度锁 | 是(update_fn) | 否 | lock_table 后遍历 |
ska::bytell_hash_map | 数组内链接 | 无 | 是 | 否 | 1 字节元数据记录跳转距离 |
emhash7::HashMap | 数组内链接 | 无 | 是 | 否 | 无墓碑,支持高负载因子 |
tsl::hopscotch_map | 邻域哈希(Hopscotch) | 无 | 是 | 否 | 每桶一个邻域 bitmap |
#参考文献
[1] Z. Liu, L. Zou, X. Zou, C. Wang, B. Zhang, D. Tang, B. Zhu, Y. Zhu, P. Wu, K. Wang, Y. Cheng. Monolith: Real Time Recommendation System With Collisionless Embedding Table. In ORSUM Workshop at ACM RecSys, 2022. arXiv:2209.07663.
[2] Q. Zhang, Z. Teng, D. Wu, J. Wang. An Enhanced Batch Query Architecture in Real-time Recommendation. In Proceedings of CIKM, pp. 5078–5085, 2024. doi:10.1145/3627673.3680034. arXiv:2409.00400. 开源实现:NeighborHash。
[3] O. Kocberber, B. Falsafi, B. Grot. Asynchronous Memory Access Chaining. Proceedings of the VLDB Endowment, 9(4): 252–263, 2015. doi:10.14778/2856318.2856321.
[4] Abseil. Swiss Tables Design Notes.
[5] Facebook. Folly: F14 Hash Table、ConcurrentHashMap、AtomicHashMap。
[6] X. Li, D. G. Andersen, M. Kaminsky, M. J. Freedman. Algorithmic Improvements for Fast Concurrent Cuckoo Hashing. In Proceedings of EuroSys, 2014. doi:10.1145/2592798.2592820. 开源实现:libcuckoo。
[7] R. Pagh, F. F. Rodler. Cuckoo Hashing. Journal of Algorithms, 51(2): 122–144, 2004. doi:10.1016/j.jalgor.2003.12.002.
[8] P. Celis, P.-Å. Larson, J. I. Munro. Robin Hood Hashing. In Proceedings of FOCS, pp. 281–288, 1985. doi:10.1109/SFCS.1985.48.
[9] D. Belazzougui, F. C. Botelho, M. Dietzfelbinger. Hash, Displace, and Compress. In Proceedings of ESA, LNCS, pp. 682–693, 2009. doi:10.1007/978-3-642-04128-0_61.
[10] G. E. Pibiri, R. Trani. PTHash: Revisiting FCH Minimal Perfect Hashing. In Proceedings of SIGIR, pp. 1339–1348, 2021. doi:10.1145/3404835.3462849.
[11] E. Esposito, T. Mueller Graf, S. Vigna. RecSplit: Minimal Perfect Hashing via Recursive Splitting. In Proceedings of ALENEX, pp. 175–185, 2020. doi:10.1137/1.9781611976007.14.
[12] NVIDIA. HierarchicalKV.
[13] Google. sparsehash.
[14] T. Goetghebuer-Planchon (Tessil). sparse-map.
[15] G. Popovitch (greg7mdp). parallel-hashmap.
[16] Boost.Unordered. unordered_flat_map / concurrent_flat_map.
[17] UXL Foundation. oneTBB.
[18] M. Leitner-Ankerl. unordered_dense.
[19] TensorFlow. Recommenders Addons (TFRA).
[20] M. Skarupke. flat_hash_map / bytell_hash_map;设计说明:A new fast hash table in response to Google’s new fast hash table, 2018.
[21] ktprime. emhash.
[22] T. Goetghebuer-Planchon (Tessil). hopscotch-map.
[23] M. Herlihy, N. Shavit, M. Tzafrir. Hopscotch Hashing. In Proceedings of DISC, LNCS, pp. 350–364, 2008. doi:10.1007/978-3-540-87779-0_24.