为什么 unordered_map 需要散列而不是 map？

Question

我是 C++ 新手
我的问题是

我知道 unordered_map 使用散列，而 map 使用红黑树。但我很困惑，为什么 unordered_map 需要散列，而 map 不需要。可能是什么原因？

#include <bits/stdc++.h>
using namespace std;
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
  
int main()
{
    unordered_map<pair<int, int>, int, hash_pair> hmap1;
    hmap1[{1,1}]=2;
    
    if (hmap1.find({1,1})!=hmap1.end()) cout<<"Value found :"<<hmap1[{1,1}]<<endl;
    if (hmap1.find({0,0})==hmap1.end()) cout<<"Value not  found"<<endl;
    
    map<pair<int, int>, int> hmap2;
    hmap2[{2,2}]=4;
    
    if (hmap2.find({2,2})!=hmap2.end()) cout<<"Value found :"<<hmap2[{2,2}]<<endl;
    if (hmap2.find({0,0})==hmap2.end()) cout<<"Value not  found"<<endl;
  
    return 0;
}

输出：

发现值：2

未找到值

发现值：4

未找到值

Answer 1

原因很简单：astd::map通过从树的根部开始并递归地向下移动树来查找其红黑树中的项目，将树的每个节点上的项目与关键项目进行比较（使用<运算符），并使用比较的结果来决定递归到哪个子节点，直到它最终到达它正在寻找的节点并返回结果（或者直到它到达叶节点而从未遇到请求的键，在在这种情况下它会返回一个错误）。在这个过程中，任何时候都不需要计算任何东西的哈希码。

std::unordered_map另一方面，A不使用树样式的数据结构。相反，它使用散列来计算它应该在其内部数据数组中查找指定键的位置。为此，它需要能够计算该密钥的哈希码；然后它可以计算该哈希码的模以获得数组索引以开始查找。