基于连续数组存储池的均摊O(1)增删数据结构有专属名称吗？

你描述的这类数据结构业内有多个通用命名，最常用的是紧凑哈希集合（Compact Hash Set），也有部分资料将其称为索引哈希集合（Indexed HashSet） 或无序连续哈希集合，部分语言的实现库中会直接命名为ArrayHashSet。

核心设计完全匹配你的需求 #

• 不要求元素有序：删除时直接交换待删元素与数组尾部元素再截断长度的操作，不需要维护排序逻辑，完全符合无顺序要求的场景
• 均摊O(1)增删：插入直接追加到动态数组尾部，删除通过额外维护的哈希表快速获取元素下标，单次操作复杂度为常量级，动态数组扩容的开销被均摊到多次插入操作中
• 内存连续排布：底层存储完全基于可扩容数组实现，所有元素在内存中连续存放，遍历场景下的CPU缓存命中率远高于传统链式存储的哈希表。

和相近概念的区别 #

你提到的对象池、slab分配器和该数据结构的定位完全不同：

• 对象池是设计模式，核心目标是复用已分配的对象内存，避免频繁的系统内存申请/释放操作，本身不要求元素去重、也不要求支持快速的按值查找删除
• slab是底层内存分配机制，属于内存分配器的实现逻辑，用于减少内存碎片，不属于上层业务使用的通用集合数据结构范畴。

常见实现参考 #

这类数据结构因为缓存友好的特性，在性能敏感场景应用非常广泛：

• C++ Abseil库的absl::flat_hash_set、Folly库的folly::F14ValueSet均采用类似的连续存储设计
• Rust生态的hashbrown库提供的HashSet默认就是紧凑连续存储实现
• 游戏开发领域大量自研引擎都会定制实现该类集合，用来存储高频访问的游戏对象，充分利用CPU缓存提升性能。

内容的提问来源于stack exchange，提问作者jwezorek