0

我有一个std::unordered_map<std::string, int> map;

然后在其中插入大量元素，但字符串键都是唯一的。

以下情况是否可能以及如何处理？

map[x] = 5;
map[y] = 3;

让我们假设x和y是不同的字符串，但它们产生相同的哈希，所以 5 和 3 放在同一个桶中。

当我们尝试检索值时map[x]，地图如何返回正确的值 5？散列x会给桶中的两个元素 5、3 但我看不出它是如何在没有密钥本身进行比较的情况下获得正确的值的。

我错过了什么？

4

2 回答 2

3

的完整声明unordered_map如下所示：

template <
    class Key,
    class T,
    class Hash      = std::hash<Key>,
    class KeyEqual  = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<Key const, T>>
> class unordered_map;

请注意，它需要哈希函数和密钥类型的相等比较器。

当搜索具有特定键的元素时，容器将首先使用哈希函数找到正确的桶，然后遍历该桶中的元素，使用相等比较器比较每个元素的键。

于 2013-10-24T02:18:26.463 回答
1

桶就是这样，一个桶。unordered_map 实际上是一个模板，其中包含键和值类型以及检查键是否相等的函数（默认为std::equal_to<KeyType>）它使用相等比较来查找存储桶中与您正在搜索的值匹配的元素为了。

如果您完全邪恶并为它们提供具有大量冲突的键，则哈希表通常会退化为线性或对数时间，实际上它们通常接近 O(1)。

于 2013-10-24T02:18:38.403 回答