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

Question

我正在为 Web 服务器实现会话存储。键是字符串，存储的对象是指针。我尝试使用地图，但需要更快的东西。我查找对象的频率是插入的 5-20 倍。

我尝试使用哈希映射但失败了。我觉得我有更多的限制而不是更多的空闲时间。

我在 Linux 下编写 c/c++。我不想承诺提升，因为我的网络服务器将比提升更长寿。:)

这是一个高度相关的问题，因为硬件（ssd 磁盘）正在迅速变化。正确的解决方案不会在 2 年内出现。

score 5 · Accepted Answer

我打算建议一个map，但我看到你已经排除了这个。

我尝试使用地图，但需要更快的东西。

这些是维基百科页面提供的 std::map 性能界限：

您如何衡量并确定地图没有为您充分优化？您看到的任何瓶颈很可能存在于代码的其他部分，并且 amap完全足够了。

除了最严格的可扩展性要求之外，上述界限似乎都可以满足。

score 2 · Accepted Answer

将使用的数据结构类型将由您要访问的数据决定。你应该问的一些问题：

哈希表通常在查找方面表现得非常好。您可以通过自己编写它们来极大地优化它们以提高速度（是的，您可以调整表格的大小）。使用哈希表提高性能的建议：

选择一个好的哈希函数！这将最好在您的哈希表中均匀分布，并且计算时间不会很长（这将取决于键输入的格式）。
确保如果您使用的桶的长度不超过 6。如果您确实超过 6 个桶，那么您的哈希函数可能分布不够均匀。< 3 的桶长度是优选的。
注意你如何分配你的对象。如果可能的话，尝试在内存中彼此靠近分配它们以利用引用的局部性。如果需要，请编写自己的子分配器/堆管理器。还要保持对齐边界以获得更好的访问速度（对齐取决于处理器/总线，因此您必须确定是否要针对特定的处理器类型）。

BTrees 也非常好，总体上表现良好。（有人可以在此处插入有关 btree 的信息）。

我建议查看您存储的数据并确保数据尽可能小。根据需要使用短裤、无符号字符、位字段。还有其他其他方法可以提高性能，例如在分配结构的同时在结构的末尾分配字符串数据。IE

struct foo {
  int a;
  char my_string[0]; // allocate an instance of foo to be 
                     // sizeof(int) + sizeof(your string data) etc
}

您可能还会发现实现自己的字符串比较例程实际上可以显着提高性能，但这取决于您的输入数据。

score 1 · Accepted Answer

可以自己制作。但是你不应该对 boost 或 std::tr1::unordered_map 有任何问题。

对于较少数量的元素，三元树可能比散列图更快。

3 回答 3