Revision en1, by Arpa, 2015-11-29 15:19:01

Hi!

##### How it works?

First of all I want to explain how unordered_map(and unordered_set) 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)

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.

##### 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 long long int), it will be done. It is pretty easy: x.first^(x.second<<32) is good. but be careful about BUG(OVERFLOW) (It's different from my friend bug-overflow :D ). The code is looks like this:

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>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.

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 (like when you have pair<long long int,long long int> as type) it doesn't problem. The only problem is that unordered_map becomes slower(however it is better than map).Here is example hash function for pair<long long int,long long int>:

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


Note2: Please be careful about your hash function time complexly! it is fun to use this hash function(WARNING: don't use it!):

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


#### History

Revisions

Rev. Lang. By When Δ Comment
en15 Arpa 2017-02-24 19:05:47 18 post name updated
en14 Arpa 2016-02-07 21:16:53 71
en13 Arpa 2016-02-07 21:11:47 162
en12 Arpa 2016-02-07 21:09:22 74
en11 Arpa 2016-02-07 21:06:53 4 Tiny change: '____**UPD:** T' -> '**UPD:** T'
en10 Arpa 2016-02-07 21:06:17 331
en9 Arpa 2016-02-07 20:54:44 438
en8 Arpa 2015-12-03 15:07:16 56 Tiny change: 'n};\n~~~~~' -> 'n};\n~~~~~\n\n**UPD** I will explain hash<type> in my next post.'
en7 Arpa 2015-11-30 22:21:36 2 Tiny change: ' map).\n**Note2:' -> ' map).\n\n**Note2:'
en6 Arpa 2015-11-30 22:07:16 448
en5 Arpa 2015-11-29 22:40:15 820
en4 Arpa 2015-11-29 19:18:52 4 Tiny change: 'red_map>.example:\n' -> 'red_map>.for example:\n'
en3 Arpa 2015-11-29 18:46:44 337
en2 Arpa 2015-11-29 17:21:04 349
en1 Arpa 2015-11-29 15:19:01 2957 Initial revision (published)