std::unordered_map有没有可能发生碰撞？

Question

我在这里看到 post 你可以“遇到生日问题”。使用 std::unordered_map

When should I use unordered_map and not std::map

这让我很吃惊，这和说 std::unordered_map 是不安全的是一样的。真的吗？如果我不解释自己，让我给你举个例子：

unordered_map<size_t, size_t> m;
for (size_t i = 0; i < 100; ++i)
    m[i] = i;
for (size_t i = 0; i < 100; ++i)
    if (m[i] != i)
        cerr << "ERROR!" << endl;

如果此代码在 main 中，是否有可能打印 ERROR!？

Answer 1

Is there any possibility that std::unordered_map collides?

不是容器有冲突，而是您为容器提供的哈希函数。

是的，所有哈希函数 - 当它们的输出范围小于输入域时 - 都会发生冲突。

is there any possibility that it prints ERROR!?

不，这不可能。哈希函数将多个值放入一个桶中是完全正常的。这会在哈希冲突的情况下发生，但它也会发生在不同的哈希值上。查找函数将使用线性搜索获得正确的值。密钥的身份由相等函数确定，而不是由哈希函数确定。

std::unordered_map有没有可能发生碰撞？

Is there any possibility that std::unordered_map collides?

c++

dictionary

hashmap

hash-collision