使用向量实现unordered_map、unordered_set、映射和设置

Question

这更像是一种智力练习，但是是否有经过实战考验的C++库使用std::vector实现哈希映射/集合(std::unordered_map，std::unordered_set)，红背树(std::map，std::set)？

以std::unordered_set为例。我的想法是使用 3 个向量，X(存储链头)、Y(存储集合元素)Z(临时容器)。

粗略地说，给定一个集合元素12345，

1. 让i = X[hash(12345) % X.size()].然后Y[i]是12345赖以生存的链条的负责人。

2. Y[i]是一对(val, j)。val是某个元素值。Y[j]是链上的下一个项目。

3. 找到12345后，删除它可能会在Y中留下"漏洞"。

4. 新元素将被推回YX并相应地进行调整。

5. 如果Y中的"孔"数量超过(例如Y.size()的50%)，请调整X并全局Y以擦除所有"孔"，在此期间可能需要Z作为临时存储。

这个想法适用于std::set和std::map的树木。当然，许多其他细节需要仔细照顾。

有人尝试过这样的事情吗？动机是保持数据结构尽可能紧凑，并尽可能避免内存分配。我想这将为中小型应用程序带来一些良好的加速 - 或者也许我错了？

谢谢！

Answer 1

是的，有。谷歌dense_hash_map就是这样一个例子。

有各种各样的哈希映射和表，这些哈希映射和表是根据特定于目的的要求构建的，例如缓存位置、大小、读取速度、写入速度。由于速度高度依赖于缓存局部性，因此这些实现通常使用向量作为后端存储。

看看哈希图之间的这场枪战，并浏览它们中的每一个。