关于C++ unordered_map和散列冲突的困惑

问题描述：

我读过unordered_map在桶中放置相同散列的元素，这就是它处理散列冲突的方式。然而，当我检查了insert function，它说：关于C++ unordered_map和散列冲突的困惑

每个元素的插入只有当它的关键是不等同于其他任何元素的键已在容器

这是否意味着我不能插入具有相同散列的元素？..我应该能够插入带有新散列的元素，因为unordered_map结构可以处理冲突，对吗？..我想我可能会错过某些东西。

2个不同的密钥可以导致相同的散列，甚至2个不同的散列可以对应于同一个桶 – BoBTFish

答

肯定是可能对于那些语句要一致，一旦你意识到散列不一定是关键。

一组不同的密钥可能会生成相同的哈希值，因此要存储在同一个存储桶中，但仍允许限制重复密钥不被允许。

例如，假设您有一个使用名字作为关键字的friends集合。散列函数是（一个相当简单的）“使用名称的第一个字母。

所以，虽然伟业，安德鲁·亚当，比尔，本尼和Chloe六种不同键，他们只占三种不同哈希值：

  A     B   C (buckets) 
    ______/|\_____  /\   | 
/  |  \  / \   | 
Albert Andrew Adam Bill Benny Chloe (keys)

值得一提的是2个不同的散列可以在同一个桶中结束，比那里给出。将（几乎肯定）比桶更可能有更多的散列。 – BoBTFish

@BoBTFish，这取决于你如何定义h灰，我想。如果你得到的32位“散列”进一步缩减为8位桶ID，我倾向于不把32位值作为散列值，而是中间值。真正的哈希将是桶ID。 – paxdiablo

对我来说，它是'hasher'的'result_type'。 “bucket id”肯定与'bucket_count'或'max_bucket_count'返回的类型'size_type'相同。 – BoBTFish