是否在abseil::node_hash_map中选择随机(ish)元素？

Question

有没有可能在abseil::node_hash_map中有效地选择某个随机元素，或者更普遍地选择任何abseil映射？

例如，我对这样一种方法很满意:随机选择一个插槽，然后找到下一个占用的插槽，并从散列到该插槽的元素中选择一个随机元素，但如果不访问map内部，就不清楚这是不是可能的。

像std::next(map, n)这样的东西，其中n是在[0, map.size())之间随机选择的整数，可以工作，但是对于复杂的O(map.size())，速度非常慢。

Answer 1

不，你不能这么做。

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