如何判断std::unordered_map是否经历了哈希碰撞？

Question

如何识别在std::unordered_map中的键是否经历了哈希碰撞？

也就是说，如何确定是否存在任何冲突链接？

- Greg

---

我猜你想要强制执行某些策略，如果是这样的话，那就让unordered_map来执行它，不要试图从客户端代码中强制执行。检查max_load_factor成员函数是否解决了底层问题。 - Giuseppe Puoti

Answer 1

你可以使用桶接口及其bucket_size方法。

std::unordered_map<int, int> map;
bool has_collision = false;

for(size_t bucket = 0; bucket < map.bucket_count(); bucket++) {
    if(map.bucket_size(bucket) > 1) {
        has_collision = true;
        break;
    }
}

- Aerle

---

如果两个元素恰好在同一个桶中，这并不意味着存在哈希冲突。 - Revolver_Ocelot

@Revolver_Ocelot -- 当然会有碰撞；那就是碰撞的定义。 - Pete Becker

一个简单的 if (map.bucket_count() < map.size()) 可以快速检查是否有任何冲突，以避免在许多情况下使用 for 循环。 - phuclv

@phuclv 可能存在空桶，因此仅进行总计数检查是不够的。 - rustyx