为什么 Apple Clang 会调用以比较无序映射中的唯一哈希值？

Question

我试图提高我对 unordered_map 实施的理解并对这种行为感到惊讶。考虑下面这个最小的例子。

#include <iostream>
#include <unordered_map>

using namespace std;

template<>
struct std::hash<int*>
{
    size_t operator()(int* arr) const
    {
        cout << "custom hash called" << endl;
        return arr[0];
    }
    
};


template <>
struct std::equal_to<int*>
{
    bool operator()(const int* lhs, const int* rhs) const
    {
        std::cout << "call to compare" << std::endl;
        return lhs == rhs;
    }
};

int main(int argc, char *argv[]) 
{   
    int arr1[8] {11,12,13,14,15,16,17,18};
    int arr2[8] {1,2,3,4,5,6,7,8};
    
    unordered_map<int*, string> myMap;
    myMap.insert(make_pair(arr1, "one"));
    myMap.insert({arr2, "two"});
}

我会期望这个输出：

custom hash called
custom hash called

两个插入的散列是唯一的，因此据我所知不需要比较多个键（因为桶应该只包含一个键）。这确实是我在 godbolt.org 上使用 Clang、GCC 和 MSVC 尝试时的结果。但是，当我在本地 Mac 上编译和运行这个示例时，第二个插入发生了对 equal_to 调用运算符的额外调用：

custom hash called
custom hash called
call to compare

测试

Apple clang version 13.1.6 (clang-1316.0.21.2)
Target: arm64-apple-darwin21.4.0
Thread model: posix

和

Apple clang version 13.1.6 (clang-1316.0.21.2.3)
Target: x86_64-apple-darwin21.4.0
Thread model: posix

在所有情况下，仅使用了 C++20 标志。

Answer 1

基本上有两种情况不需要应用比较器：

第一个是目标桶为空的时候（那么，没有什么可以比较的）。一个简单的同时适用于libstdc++和libc++的演示代码如下：

struct Hash {
  size_t operator()(int a) const { return a; }
};

struct Equal { ...  /* log operator call */ };

std::unordered_map<int, int, Hash, Equal> m; 
m.reserve(2);

std::cout << m.bucket(0) << std::endl;  // 0
std::cout << m.bucket(1) << std::endl;  // 1

m.insert({0, 0});
m.insert({1, 0})

这里，key 0 和 1 都针对不同的 bucket，所以没有对这两个实现进行比较。

现场演示：https://godbolt.org/z/5jfYv6sba

第二种情况是目标桶中的所有键都具有不同的哈希值，并且那些 哈希值存储（缓存）在哈希值 table 个节点 中。此缓存由 libstdc++ 支持，并且似乎默认应用。不过libc++好像不支持。示例代码：

std::unordered_map<int, int, Hash, Equal> m; 
m.reserve(2);

std::cout << m.bucket(0) << std::endl;  // 0
std::cout << m.bucket(2) << std::endl;  // 0

m.insert({0, 0});
m.insert({2, 0})

这里，两个键都指向同一个桶（索引为 0）。使用 libstdc++，由于哈希值被缓存并且不同，因此会比较它们，没有理由另外比较整个键。但是，使用 libc++ 时，不会缓存哈希，需要比较键。

现场演示：https://godbolt.org/z/vWK4Ko7Yj

为什么 Apple Clang 会调用以比较无序映射中的唯一哈希值？

Why does Apple Clang make a call to compare for a unique hash in an unordered map?

c++

clang

libc++