std::unordered_map中同一个键有多个条目？

Question

我有一个使用相同键的多个值的map，键是C字符串类型。

我期望只有一个指定键的条目。

然而，当唯一地识别一个键时，该map似乎考虑了它的地址。

#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>

typedef char const* const MyKey;

/// @brief Hash function for StatementMap keys
///
/// Delegates to std::hash<std::string>.
struct MyMapHash {
public:
    size_t operator()(MyKey& key) const {
        return std::hash<std::string>{}(std::string(key));
    }
};

typedef std::unordered_map<MyKey, int, MyMapHash> MyMap;

int main()
{
    // Build std::strings to prevent optimizations on the addresses of
    // underlying C strings.
    std::string key1_s = "same";
    std::string key2_s = "same";
    MyKey key1 = key1_s.c_str();
    MyKey key2 = key2_s.c_str();

    // Make sure addresses are different.
    assert(key1 != key2);

    // Make sure hashes are identical.
    assert(MyMapHash{}(key1) == MyMapHash{}(key2));

    // Insert two values with the same key.
    MyMap map;
    map.insert({key1, 1});
    map.insert({key2, 2});

    // Make sure we find them in the map.
    auto it1 = map.find(key1);
    auto it2 = map.find(key2);
    assert(it1 != map.end());
    assert(it2 != map.end());

    // Get values.
    int value1 = it1->second;
    int value2 = it2->second;

    // The first one of any of these asserts fails. Why is there not only one
    // entry in the map?
    assert(value1 == value2);
    assert(map.size() == 1u);
}

在将这些元素插入后，调试器中的打印显示地图包含两个元素。

(gdb) p map
$4 = std::unordered_map with 2 elements = {
  [0x7fffffffda20 "same"] = 2,
  [0x7fffffffda00 "same"] = 1
}

为什么如果散列函数只考虑了值（在代码中被断言），委托给std::hash<std::string>的话，仍然会出现这种情况？

此外，如果这是预期的行为，我如何使用C字符串作为键创建一个1:1的键值映射的地图？

- Andrei Pavel

---

为什么要使用 const char*，而不是使用 string 呢？MyMapHash 的定义在哪里？ - EdChum

我需要它与现有的 const char* 兼容。我想避免在其上构建一个 string 的开销，但我现在意识到我已经在我定义的 MyMapHash 中这样做了。所以我可以使用 string。谢谢！ - Andrei Pavel

Answer 1

哈希映射（例如std::unordered_map）之所以不仅依靠哈希函数来确定两个键是否相等，是因为哈希函数只是第一层比较，之后元素始终会按值进行比较。这是因为即使使用好的哈希函数，您也可能会遇到冲突，即两个不同的键产生相同的哈希值 - 但您仍然需要能够在哈希映射中保存这两个条目。有各种策略可以处理这个问题，您可以查找有关散列映射冲突解决方法的更多信息。

在您的示例中，两个条目具有相同的哈希值但不同的值。这些值仅由标准比较函数进行比较，该函数比较char*指针，这些指针是不同的。因此，值比较失败并且您将在映射中获得两个条目。要解决此问题，您还需要为哈希映射定义自定义等式函数，可以通过为std::unordered_map指定第四个模板参数KeyEqual来完成。

- Matthias247

Answer 2

这个失败是因为unordered_map不能仅仅依靠哈希函数来区分键，它还必须比较具有相同哈希值的键是否相等。而比较两个char指针则会比较其所指向的地址。

如果想要更改比较方式，可以在映射中除了哈希之外还传递一个KeyEqual参数。

struct MyKeyEqual
{
    bool operator()(MyKey const &lhs, MyKey const &rhs) const
    {
        return std::strcmp(lhs, rhs) == 0;
    }
};

- PaulR

Answer 3

unordered_map需要能够对键执行两个操作-检查相等性和获取哈希码。自然地，两个不相等的键允许具有不同的哈希码。当发生这种情况时，无序映射将应用哈希冲突解决策略来将这些不相等的键视为不同。

当您为键提供字符指针并提供其哈希实现时，就会发生这种情况：指针的默认相等比较开始工作，因此即使相应的C字符串内容相同，两个不同的指针也会产生两个不同的键。

您可以通过提供自定义实现的KeyEqual模板参数来修复它，以执行C字符串的实际比较，例如通过调用strcmp：

return !strcmp(lhsKey, rhsKey);

- Sergey Kalinichenko

Answer 4

你定义的不是一个键的映射，而是一个指向键的指针的映射。

typedef char const* const MyKey;

编译器可以优化两个"name"实例并仅在const数据段中使用一个实例，但这可能发生也可能不发生。即未定义的行为。

您的映射应包含键本身。将键设置为std::string或类似类型。

- harper