c++ - 需要将字符串存储为某些快速数据结构中的对象的 id

Question

我正在为网络服务器实现 session 存储。键是字符串存储的对象是指针。我尝试使用 map 但需要一些东西快点。我会查找一个物体 5-20 次与插入一样频繁。

我尝试使用 HashMap 但失败了。我觉得我受到的限制多于空闲时间。

我正在 Linux 下编写 c/c++ 代码。我不想致力于提升，因为我的网络服务器将比提升更长久。 :)

这是一个高度相关的问题，因为硬件(SSD 磁盘)是变化迅速。什么是正确的解决方案，两年后就不再是正确的解决方案。

Answer 1

我本来打算建议一张 map ，但我发现你已经排除了这一点。

I tried using map but need something faster.

这些是 std::map 性能界限，由 Wikipedia page 提供。 :

• 搜索元素需要 O(log n) 时间
• 插入新元素需要 O(log n) 时间
• 递增/递减迭代器需要 O(log n) 时间
• 迭代映射的每个元素需要 O(n) 时间
• 删除单个 map 元素需要 O(log n) 时间
• 复制整个 map 需要 O(n log n) 时间。

您如何衡量并确定 map 没有为您充分优化？您看到的任何瓶颈很可能都在代码的其他部分，而 map 就完全足够了。

上述界限似乎符合除最严格的可扩展性要求之外的所有要求。