3

我遇到了一个与 stdext hashmap 相关的非常奇怪的事情。我必须处理很多对象，并且优先考虑快速访问元素。我的程序从文件中读取对象值，如果它是新元素，则将此值插入哈希图中，如果它是已处理的对象，则更改哈希图中的存储值。

我的问题与hashmap(stdext). 我还没有找到这个容器的任何初始化选项。

键元素是一个无符号整数 ( uint64)，该对象与该键一起存储在哈希图中，大小为 160 KB。
该程序正在运行，但是当 hashmap 中的对象数量达到限制时，我不得不等待太多。

在此之后，哈希图再次运行良好，正如我所期望的那样。我想也许这是一个重组步骤。

但这些步骤很关键，因为在处理一定数量的物体后，这一步需要 5 个小时才能完成，而正常的处理步骤大约需要 2-3 分钟。此后，处理变为“正常”。

有没有人遇到过这样的问题？有人对这个哈希图有更深入的了解吗？我没有找到与该主题相关的任何内容。

我正在尝试使用具有非默认值的 hashmap 参数：bucket_sizeand min_buckets。其默认值为bucket_size=4和min_buckets=8。我已将 xhash 文件中的它们更改为更大的值，因为我没有设法从代码中更改这些值。我认为这min_buckets在我的应用程序中至关重要，我尝试“微调”以获得更好的性能，避免重组步骤。

但是所以我遇到了另一个问题，在我尝试清除哈希图之前一切正常。这需要很多时间。当我将它与默认值一起使用时，运行速度非常快。

更改 xhash 文件是不是一个糟糕的步骤？以前有人用过非默认值吗？这种缓慢清除的原因是什么？

我的第二个问题与在哈希图中存储指针有关。这个想法很清楚，但我怎么能设法释放指向的内存。我应该创建指向我的对象的指针；这些指针存储在 hashmap 中，当我需要该值时，我可以让它解除对这个指针的引用。但是保存地图后如何清除内存呢？也许这是一个微不足道的问题，但现在我没有看到解决方案。

感谢您已经发布的答案。

4

4 回答 4

3

复制您的对象可能非常昂贵（考虑到它的大小）。尝试存储指向对象而不是整个事物的指针，或者如果您想让删除变得简单，请尝试存储 boost::shared_ptr。

这样，当数据结构自我重组时，复制非常快，因为它只是一个指针分配，而不是复制巨大对象所需的任何东西。

于 2009-02-24T19:36:57.167 回答
0

您的问题是重新分配（和复制）或哈希冲突。

向量受此影响太大（并且分配大小呈指数增长）。然而，maps、sets 和 hashmaps 通常受到的影响较小。在大多数情况下，后面的这些类没有 resize() 成员。所以，

  • 您可以传递自定义分配器（大多数容器允许 AFAIK）
  • 选择更好的哈希算法

如果你愿意，你可以检查你的 hashmap 实现，看看它们是否遵循 move-idiom。如果他们不试一试。

于 2009-02-24T20:18:43.323 回答
0

当容器决定为更多对象分配空间时，听起来您会受到复制对象的成本的打击。两个最简单的选择是：

  1. 如果您知道将使用该void resize(size_type n)函数插入的对象数量。

  2. 您可以将指针存储在容器中，而不是对象本身。

于 2009-02-24T19:42:04.113 回答
0

使用 Java。当涉及到高效的哈希映射插入（更好的分配器，无复制）并在查找时匹配它时，你会被它击败 C++ 的顺序震惊。

于 2009-07-03T18:56:07.020 回答