Блог пользователя Arpa

[Tutorial] Everything about unordered_map
Автор Arpa, история, 8 лет назад, По-английски

UPD: Tricks to make unordered_map faster added.

Hi!

What is unordered_map?

It is a data structure like map but it is more than 4 times faster than map.you can use it in C++11 with including #include<unordered_map>.for example:

#include<unordered_map>
using namespace std;
int main(){
  unordered_map<int,int>mp;
  mp[5]=12;
  mp[4]=14;
  cout<<mp[5]<<' '<<mp[4]<<endl;//prints: 12 14
}

Lets explain it more.

How it works?

Focus on unordered_set for simplify.You can imagine that it has vector of vector like vector<vector<type> > mp. Every time you insert value V in that, it calculate its hash(I will explain how it works), let hash(V)=K; it inserts V into mp[K] (formally it calls mp[K].push_back(V)).When you call mp.count(V) it searchs for V in mp[K].

map VS unordered_map (and set VS unordered_set)

1-unordered_map is more than 4 times faster

Focus on problem 527E - Data Center Drama, it seems that it is good to use unordered_map instead of map.

My submission with map: 14269000 Time:484 MS.

My submission with unordered_map: 14269381 Time:358 MS.

Another good sample to show how fast is unordered_map is problem 178C3 - Smart Beaver and Resolving Collisions:

My submission with map: 15781810 Time limit exceeded on test 36 .

My submission with unordered_map: 15774685 Accepted (Time:966 MS).

2-unordered_set (and unordered_map) is not sorted

Please note that set (and map) is sorted, for example *(s.begin()) is always smallest number in the set; but in unordered_set it isn't. similarly there isn't lower_bound and upper_bound in unordered_set (and unordered_map similarly).

Creating hash function for structs

Now, one other problem remains, you can try to compile this code:

unordered_map<pair<int,int>,int>mp;

You will get Compilation Error! Why? See this page for unordered_map supported types. For unsupported types, you have to create your own hash function for use. For example lets see how we can create a hash function for pair<int,int>.

As you know any int value is between -2^31+1 to 2^31-1.so if we create function that for every pair<int,int> returns distinct value in type size_t(alias of unsigned int), it will be done. It is pretty easy: x.first^(x.second<<32) is good. but be careful about overflow ;for having good hash function we use hash<long long>.The code is looks like this:

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};
unordered_map<pair<int,int>,int,HASH>mp;

Now you have a unordered_map of pair<int,int> (it isn't problem what is second member, in example it was int).Creating hash function for other structs is same.

How to test unordered_map is faster than map?

You can test that for N=10^6, unordered_set(unordered_map) is more than 4 times faster than set(map) ;with this code:(compile code with command: g++ file.cpp -std=c++11 -O2)

#include <bits/stdc++.h>
using namespace std;
unordered_set<int>s;//replace it with set for test.
int main(){
  auto T=clock();
  s.reserve(32768); //updated !
  s.max_load_factor(0.25); //updated !
  for(int i=0;i<1000000;i++)
    s.insert(i);
  cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
}

Note1: Let your hash function H(V), it is better that H(V) returns distinct value for every distinct V, it makes unordered_map faster; but if you can't do that it doesn't problem. The only problem is that unordered_map becomes slower(however it is better than map).

Note2: Please be careful about your hash function time complexly! it is fun to use this hash function:

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    size_t ans=0;
    for(int i=0;i<x.first;i++)
      ans+=x.second;
    return ans;
  }
};

UPD I will explain hash<type> in my next post.

UPD It seems that sometimes unordered_map becames so slow.but it can improve with this two lines of code:

unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);

With this two lines unordered_map become about 10 times faster. You can replace 1024 with another suitable power of two.(it depends on number of insert s you will do).

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you so much! I had no idea about this. From now I'll use it as much as possible :)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

    you can use unordered_set/map when you don't need order of members.

    for example one of unordered_set applications is when you are storing all of the settings of one vector (for example); you can store them in unordered_set.for example:

    unordered_set<vector<int> >all;
int count(vector<int>v){
  if(all.count(v))
    return 0;
  all.insert(v);
  ...
}

    you will never check the same vectors with that trick!

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Unordered_map isn't faster than map when count of elements isn't much. Sorry for bad eng :)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    if N is about 100 ;map has equal time with unordred_map.

    but you can test it when N is about 10^6. it seems that unordered_map is about 4 times faster than map.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Hi, I need a small clarification. I was just solving this problem. I made submission using both unordered_map and map. But when I include the reserve and max_load_factor, my code gets AC I don't understand why the normal unordered_map gives TLE when N is about 1e5 when it's supposed to be faster than map. Could you please help me with this? Is it because of "sometimes unordered_map becomes so slow" ?

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Hey AishwaryaR

        When the capacity is not reserved beforehand, it takes capacity as 16 and creates a hashtable on this.

        Everytime the number of elements increase than threshold, it doubles this capacity and rehashes all the existing keys.

        Reserving an approximate capacity before hand avoids this rehashing and dynamic space allocation, in turn making the program more efficient and reducing the runtime.

        → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится 
    size_t operator()(const pair<int,int>&x)const{
        return ((long long)x.first)^(((long long)x.second)<<32);
    }

Most competitive programming environments are still 32-bit. So, by doing ^(((long long)x.second)<<32) and then implicitly casting to size_t, you are effectively discarding x.second. Now, the hash depends only on x.first.

Here is the code to check that:

#include <bits/stdc++.h>

using namespace std;

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return ((long long)x.first)^(((long long)x.second)<<32);
  }
};

unordered_map<pair<int,int>,int,HASH>m;

int main(){
  auto T=clock();
  for(int i=0;i<20000;i++)
    m[make_pair (1, i)] = i;
  cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
}

Note make_pair (1, i). The above test takes more than a second locally when compiled in 32-bit mode. You can run a custom test in any Codeforces past contest and check for yourself.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится -23 Проголосовать: не нравится

    Post edited.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Sorry, I don't get what you are saying.

      I think you have to work on your math. 858 is smaller than 1000; isn't it?

      So what? That's still on the order of a second.

      Note that we insert 20,000 elements, not a million like you do. If inserting twenty thousand, again, elements takes on the order of a second, that's quadratic behavior, or at least definitely not linear. The constant 20,000 is used instead of your code's 1,000,000 so that we can actually see the result in reasonable time. One can make it 1,000,000 and watch it time out (I, for one, wasn't patient enough to let it finish).

      Also, note that changing make_pair (1, i) to make_pair (i, i) makes the program run in an instant (less than 100 ms).

      To summarize again:

      1. Codeforces checks your solutions in a 32-bit environment.

      2. So, size_t is 32 bits long.

      3. So, for every possible X and Y, the result of X ^ (((long long)Y)<<32) converted to size_t is just X.

      4. So, the hashes for pairs (1, 0), (1, 1), (1, 2), (1, 3), ..., (1, 999999) will be equal, and unordered_map will have trouble storing them.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I have interested! thank you.

        I have changed my hash function, you can see the new one.

        I have mistaken, size_t is alias of unsigned int, no unsigned long long int.

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          The new hash approach perhaps does something like x * 37 + y anyway, so why not do that explicitly?

          struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return (size_t) x.first * 37U + (size_t) x.second;
  }
};

          On a side note, I'm surprised that a language as mature as C++ (11) does not define a default hashing method for library containers such as pair or vector.

          → Ответить
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

            It has one for vector: hash<vector<int> >.

            You can use it for pair, first create a vector of {x.first,x.second} and use hash<vector<int> >.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Can you please elaborate?

              I try the following:

              #include <bits/stdc++.h>
using namespace std;
unordered_set <vector<int>, hash<vector<int> > () > s;
int main() {s.insert ({1, 2, 3});}

              And it does not compile (MinGW GCC 4.8.1 and 5.1.0), throwing some 100+ lines of error messages at me, basically stating that I misuse hash<vector <int> >. Removing () after hash<vector<int> > does not help.

              Googling for a few minutes did not help me either. I only found a reference stating that it is not implemented in the library, and a few implementations for custom types.

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                You can create it like this:

                namespace std{
    template<>struct hash<vector<int> >{
        size_t operator()(vector<int> const& v) const{
          unsigned long long h=0;
          for(auto &x:v)
            h<<=32,h^=hash<int>()(x),h=hash<long long>()(h);
          return h;
        }
    };
}
                → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  So, what you are saying is that there is in fact no built-in hash<vector<int> > after all? Then my point still stands.

                  I won't deny that almost anything is possible with C++. I'm just surprised some trivial pieces of that work aren't in the library already.

                  → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Hey Gassa! Would you recommend same struct HASH when the order of elements in my pair doesn't matter? for example, in my case pair (1, 2) can be considered same as (2, 1). Is there any faster way for that?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      When you store the pairs, always make it such that pair.first <= pair.second holds.

      → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In fact, my point above was that I don't like the very idea of C++ not having a standard hash of pair in the library, and the 95%+ horrendous implementations of pair hashing that ensue. Plentiful examples around or on StackOverflow.

      In particular, no, I don't recommend hashing by just XORing the elements of the pair, as there are naturally occurring cases when it results in suboptimal behaviour.

      As for hashing a pair where the order of elements doesn't matter, I'd do that explicitly at first opportunity: when constructing the pair. So that (a, b) becomes (min(a,b), max(a,b)) right away. And then use standard pairs.

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Thank you. I get it now.

        → Ответить
      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        As for hashing a pair where the order of elements doesn't matter, I'd do that explicitly at first opportunity: when constructing the pair. So that (a, b) becomes (min(a,b), max(a,b)) right away. And then use standard pairs. This is not clear.can you please explain Gassa or anyone

        → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I run these two versions of map and unordered_map on custome test with GNU G++11 5.1.0. I see that unordered_map is slower than map

Version of map:

#include <bits/stdc++.h>

using namespace std;

map<pair<int,int>,int>m;

int main(){
  auto T=clock();
  for(int i=0;i<1000000;i++)
    m[make_pair (1, i)] = i;
  cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
}

Version of unordered_map:

#include <bits/stdc++.h>

using namespace std;

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return ((long long)x.first)^(((long long)x.second)<<32);
  }
};

unordered_map<pair<int,int>,int,HASH>m;

int main(){
  auto T=clock();
  for(int i=0;i<1000000;i++)
    m[make_pair (1, i)] = i;
  cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
}

Why is that?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

    On Intel® Core™ i3 CPU M 390 @ 2.67GHz × 4 :

    map : 2469 MS

    unordered_map: 485 MS

    On CodeForces:

    map: 2469 MS

    unordered_map : 1885 MS

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      hey @Arpa can u explain me the struct HASH code? thanks in advance.....

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You should implement operator () for this struct. It takes an object and returns size_t (alias of unsigned int). You should write it in a way such that minimize the number of conflicts.

        → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Add this two lines:

    m.reserve(4096);
m.max_load_factor(0.25);
    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Arpa (previous revision, new revision, compare).

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

What does this mean ? s.max_load_factor(0.25);

And which library it uses ?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    The load factor is the ratio between the number of elements in the container (its size) and the number of buckets (bucket_count). (source)

    it uses <unordered_map>(or <unordered_set>) for sure.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hi can anyone explain, why map is more than 10 times faster in this case? I could not find any reason for this. any help on this matter would be highy appreciated. I also tried adding the 2 lines of code mentioned above to make unordered_map faster but with no luck. 21740384 and 21740655

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Because map has a logarithmic access time on size always, on the other hand, unordered_map in average has a constant access time, but in worst case it's just linear in size.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for the quick reply! I am aware of the worst case complexity of unordered map. However, usually most of the times unordered map is observed to be faster. Can you share any further insights on deciding between unordered map and map. And also what is making unordered map slower than map in the above case I presented? i,e.. what kinds of data is suitable to be represented by map and unordered_map exactly?

      EDIT: I see that the test case on which unordered map gave TLE involves hashing a multiple of some fixed number. Has this got something to do with the TLE(I believe it must be the reason). Also, was the testcase specifically designed so that unordered_map fails on it, How do we make sure not to fall in such traps if so?

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please see the following issue: http://codeforces.com/blog/entry/44705?#comment-292160

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Hi. I have 3 questions.

  1. Why must the input value for the reserve() method be a power of 2?

  2. Is there formula to determine the input value for the reserve() method? Let's say we use mp.reserve(x) where x is a power of 2. Does that mean that x must be >= N, where N is the number of elements that we are going to input into the unordered_map?

  3. How did you determine the value for the max_load_factor? Is that supposed to be a magic value?

Please advise me.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Thank you for your hard work, but unfortunately I don't find it that much useful with all that painful implementation.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

AC using map: 33860000

TLE using unordered_map: 33860168 [ Yes, I used the tricks you mentioned to make unordered map faster. Also I have used the Hash function that you gave in the post for pair<int, int>

So, how can I believe that unorded_map is faster than map ??

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's really confusing when to use unordered_map and when to use map. My submission with map takes 1450 ms: 38906751 Same submission with unordered_map takes 467 ms:38906911 Though both passed time limit (3 s), if the time limit was 1-1.3 s, solution using map would have failed.

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You just need to use a better hash function for pair<int,int> to get your solution passed. The hash function proposed here for pair<int,int> clearly isn't a good one. Read the above discussion here. I have changed your hash function and your TLE code gets ac for that problem. Here's the ac code with modified hash function.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But is it always safe to use unordered_map in contests, since in worst case unordered_map can be of O(n)? Should anyone use unordered_map always instead of map ?

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

SUMFOUR — 4 values whose sum is 0 on SPOJ in an example where unordered_map with reserve() will give AC and others will give TLE

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

ََُArpa youre the best :)

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have used unordered_map for this problem. Christmas Trees I got a TLE with this Then I changed the unordered_map to just map and got AC with this Can you explain what is happening here. [Sorry for my bad English]

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Unordered_map : TLE submission link

map : AC submission link

i've no idea why...

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    It happens. Try to use the reserve method. You can implement Hash Map on your own too.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi. Could you please explain how you arrive with values such as 1024 or 4096 while using reserve? Say, for example, I know that in my program there will be 10^7 insert operations. What value do I use then?

      Doesn't reserve(4096) mean set the appropriate number of buckets to hold at least 4096 elements in the hash table without exceeding the max_load_ratio?

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Be careful with hash data structures. Even though std::unordered_map is often faster than std::map, it still has a worst case complexity of O(n) per operation and it is possible to design TLE hacks this way. See https://codeforces.com/blog/entry/62393.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is unordred_map?

Shouldn't it be "What is unordered_map?"

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is the average time complexity of insertion/search in unordered_map if key is string ? Is it O(L) L=>length of string ?

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi I have tried to change (unordered_)map to many thing like this ones but every time I get TLE on last testcase; I think this idea should be change but if anybody can help me, I ll be happy. link of submission

→ Ответить