c++ - 在 abseil::node_hash_map 中选择一个随机（ish）元素？

Question

是否可以有效地选择 中的某种随机元素abseil::node_hash_map，或者更普遍地选择任何abseil地图？

例如，我很高兴随机选择一个插槽，然后找到下一个占用的插槽并从散列到该插槽的元素中选择一个随机元素，但不清楚这是否可能没有访问地图内部。

像std::next(map, n)where nis an integer 之间随机选择的东西[0, map.size())会起作用，但复杂性非常慢O(map.size())。

标签： c++performancehashhashmapabseil

Answer 1

不，你不能那样做。

您可以获得的最接近的方法是创建一个单独的指向 node_hash_map 元素的指针数组，然后在这些指针中随机选择。这样，第一次选择一个元素时，它是 O(N) 时间，但之后是 O(1)。