如何在 O(1) 中从 C++ 哈希 table 中随机检索元素

Question

有没有办法在 O(1) 的平均时间内从 C++ unordered_set 中随机检索一个元素？而不是做

std::unordered_set<int> s;
// initialize s
auto start = s.begin();
for (int i = 0; i < rand()%s.size()-1; ++i, ++start) {}
int randomNumber = *start;

更新：

我需要为post而战，所以我添加了我需要上述功能的原因。

我正在玩迷宫生成器。不知何故，我需要一个支持的数据结构：

插入/删除复杂度为 O(1)
从 O(1) 的数据结构中随机检索一个元素

std::vector 具有随机访问，但插入/删除是昂贵的

std::list 没有随机访问

std::set 支持 O(logN) 随机访问和 O(logN) 插入/删除，这很棒，但我的初始化是一个排序序列，很容易打破它的平衡。

所以我认为 hash table 是最好的选择，但是随机检索一个元素并不简单。

感谢您的宝贵时间。

Answer 1

从 std::unordered_set 中随机选择一个元素是个坏主意。这是因为 std::unordered_set 不支持随机访问，因此没有下标运算符（即 operator[]）。

我坚信您需要的是 std::vector 与 std::unique 结合以满足元素唯一性。

在下面的示例中，我使用了 std::vector，然后通过在其上应用 std::unique 算法确保它只有唯一元素。然后我使用 random 实用程序在 [0, vector's size - 1]:

中生成随机索引

std::vector<int> v{1, 2, 8, 3, 5, 4, 5, 6, 7, 7, 9, 9, 19, 19};
v.erase(std::unique(v.begin(), v.end()), v.end());

std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(0, v.size() - 1);

std::cout << "Random number from vector: " << v[distribution(generator)] << std::endl;

LIVE DEMO

Answer 2

您不能在 O(1) 时间内从 unordered_set 中随机选择一个元素。迭代器是 ForwardIterators，而不是 RandomAccessIterators。您将不得不使用不同的容器。 boost::container::flat_set<int> 或自己写一个内部也有类似 vector 的东西：

template <typename T>
class set_with_random_access
{
    std::vector<T*> vec;
    std::unordered_set<T> set;
};

为此，我们提供了使它们保持一致的功能，例如插入：

void insert(const T& value) {
    auto pr = set.insert(value);
    if (pr.second) {
        vec.push_back(&*pr.first);
    }
}

随机性：

template <typename GEN>
T& random(GEN& gen) {
    std::uniform_int_distribution<size_t> dist(0, vec.size() - 1);
    return *vec[dist(gen)];
}

坦率地说，这是一项繁重的工作，所以可能会使用增强版。

Answer 3

a way to randomly retrieve an element from C++ unordered_set in O(1) average time?

取决于什么算作 "random" 用于您的目的，以及超过 O(1) 一点点是否足够好。您可以在 0 和 s.bucket_count() - 1 之间选择一个随机桶“b”，如果桶为空则重复，然后在 0 和 [=] 之间选择列表索引 li 16=]，然后 std::advance(s.begin(li)) 得到指向 "random" 元素的迭代器，但是，考虑这种情况：

You roll three dice - then randomly pick one of those: you get a random 1-6 value with even probability, but if you keep picking without rolling again you can only ever get whatever value(s) ended up on the three dice: the probabilities of each value from 1 through 6 are severely uneven.

上面在 unordered_set 中选择随机元素的方法有点像这样：如果有 x 个包含元素的桶，那么每个桶都有均匀的机会被选中，但是该桶中的元素有 1 / x / bucket_size() 个选择机会 - 对于任何给定的桶 - 可能小于或大于 1 / size()。换句话说，如果你认为散列实际上是随机的，那么各种元素在它们的位置上有相同的机会受到青睐或惩罚，但是 "skew" 然后将其设置为石头，直到 table 数据发生显着突变或 table 的重新散列（如果通过将 table 大小加倍而不是更大的质数（unordered_set 加倍的模糊记忆）重新散列，那么一旦惩罚值将倾向于一半时间仍然受到惩罚）。

上面的大 O 效率比 O(1) 稍微高一点，因为：

在初始探测中有一些重复以找到包含元素的桶，但是加载因子为 1.0 时不太可能需要多次尝试（假设有一个良好的哈希函数）；其他选项可用——比如从一个空桶迭代，或通过各种位移跳跃（修改为 table 大小）——这可能比尝试另一个完全随机的桶执行得更好，但也可能会加剧几率的差异元素选择
在任何给定的桶中，元素的碰撞都是线性迭代，但由于默认加载因子为 1.0，因此很少会发生超过几次碰撞，并且越来越少发生多次碰撞不止于此。

如何在 O(1) 中从 C++ 哈希 table 中随机检索元素

How to random retrieve an element from C++ hash table in O(1)

c++

hashtable

unordered-map

random-access

unordered-set