sparsepp

现在我建议使用 并行哈希表 来代替 sparsepp,除非你使用的是不兼容 C++11 的编译器,或者使用更多内存是不可接受的。我个人会转而使用 并行哈希表,我认为它提供了明显更好的平衡(内存使用略高,速度更快)。

• 这是一个替代了 unordered_map 和 unordered_set 的插入式实现。 - 内存占用极低（通常每个元素的开销约为 1 字节），而且最重要的是 重新调整大小时的内存开销非常小。 - 效率非常高，通常比编译器的 unordered map/set 或者 Boost 更快。 - 支持 C++11（如果编译器支持）。 - 单个头文件 不再

我们认为 Sparsepp 具有无与伦比的性能和内存使用率组合,在两方面都会优于您的编译器的 unordered_map。只有 Google 的 dense_hash_map 更为快速,但其内存使用率要高得多(尤其是当地图的最终大小事先未知,且插入操作导致重新调整时)。

这种哈希映射类似于 Google 的 dense_hash_map，使用开放式寻址（意味着哈希表项在概念上存储在一个大数组中，碰撞不会使用链表解决，而是通过探测来解决）。开放式寻址的一个大缺点是，当数组需要扩大时，内存使用的高限通常是当前映射大小的 3 倍（因为我们分配了比当前数组大两倍的新数组，并从旧数组中复制到新数组）。Sparsepp 的实现解决了这个内存使用问题，并且在扩容时，内存使用的高限只会略微增加。