Why hashing is required for unordered_map and not in map?

Question

I am new to C++, and I know that unordered_map uses hashing and map uses red black tree. I am confused why hashing is required for unordered_map whereas not in map. What is the reason?

#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;
}

Output:

Value found :2

Value not found

Value found :4

Value not found

@NathanOliver Yes, I know ihow it works.Is there anything I am missing — Shyam Prasanna, Aug 10 '21 at 18:49
Looks like you do not understand how RB trees work, otherwise, it would be immediately obvious to you why `std::map` doesn't need a hash function. — SergeyA, Aug 10 '21 at 18:50
Obligatory links to [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Together they amplify each other's worst effects and can easily turn a program into a minefield of weird. Use with caution, and when you have a problem with your code they should be among the first things to be removed. — user4581301, Aug 10 '21 at 19:08
If you are trying to learn C++ from coding competition sites, don't. Teaching is not what they are for and as a result they *really* suck at it. Save yourself time and get a [couple good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). You'll save yourself a lot of time. — user4581301, Aug 10 '21 at 19:10

score 5 · Answer 1 · answered Aug 10 '21 at 19:00

The reason is simple: a std::map looks up an item inside its red-black tree by starting at the root of the tree and recursively moving down the tree, comparing items at each node of the tree against the key-item (using the < operator), and using the result of the comparison to decide which child-node to recurse to, until it eventually arrives at the node it is looking for and returns the result (or alternatively until it arrives at a leaf node without ever encountering the requested key, in which case it will return an error). At no point in that process is it necessary to compute a hash-code of anything.

A std::unordered_map, on the other hand, doesn't use a tree-style data structure. Instead it uses hashing to compute where in its internal data-array it should look for the specified key. In order to do, that it needs to be able to compute a hash code for that key; it can then compute the modulo of that hash-code to obtain an array-index to start looking in.

Why hashing is required for unordered_map and not in map?

1 Answers1