Facebook 开放 F14 哈希表的实现

脸书公司 宣布了 关于哈希表的开源实现 F14，针对高效内存消耗进行了优化。 F14 在 Facebook 基础设施中用作大多数类型哈希表的替代品，可以在不牺牲性能的情况下减少内存消耗。 F14 明显优于 google::sparse_hash_map 哈希表，迄今为止，后者在内存消耗方面被认为是最有效的。 项目代码用C++编写并包含在库中 蠢事.

F14 是指具有基于双散列的冲突解决系统的算法，具有 14 样本序列 （14个槽的链存储在一个哈希表单元中，单元之间的间隔使用辅助哈希函数计算）。 为了加速单元过滤操作，该实现使用用于 x2_86 系统的向量指令 SSE64 和用于 Aarch64 的 NEON，这允许并行执行用于选择带有密钥链的插槽并筛选链内密钥的操作。 一次处理14个槽的块，这是处理器缓存使用效率和冲突次数之间的最佳平衡。

F14 的一个特点是能够选择不同的数据存储策略：

• F14NodeMap - 对于大中型键消耗最少的内存。 确保在每次插入时调用 malloc 来间接存储元素；
• F14ValueMap - 为小键提供最小的内存消耗。 元素存储在单元格本身中（内联）。 对于中型和大型密钥，这种方法会导致显着的内存开销；
• F14VectorMap - 对于大型表和复杂键，工作速度更快，但对于简单键和小表，速度较慢。 元素被打包到一个连续填充的数组中，并通过 32 位索引指针进行寻址；
• F14FastMap是一个组合策略。 如果key小于24字节，则选择F14ValueMap，如果大于14字节，则选择FXNUMXVectorMap。

来源： opennet.ru