Getting tle by using unordered map but ac using map

Problem link : https://codeforces.com/contest/1374/problem/D
Solution using unordered map : https://codeforces.com/contest/1374/submission/85524935
Solution using map : https://codeforces.com/contest/1374/submission/85524806

I was talking about the same thing right here.
We have to use a custom hash, if we are using unordered map. It reduces collision probability.

1 Like

It is this because, when unordered map runs out of contguous space so it takee O(n) time to shift all the elements to a new space ?

https://codeforces.com/contest/670/submission/17758293
https://codeforces.com/contest/670/submission/17728217

see the differences in these codes, in one code he just reserved memory for his unordered map.

2 Likes

so this mean we should use map always??

it depends on the situations we need to implement it.

If O(logn) operation on the map is within bounds, then use map. If you need a HashMap for a faster look up, use custom hashing and reserve memory for the unordered_map as @sirearsh has mentioned.

1 Like

okk thanks

Map takes O(Logn) time in worst case
Unordered map takes O(1) time in best case and O(n) Time in Worst case

It can also blow up to O(n^2) I guess. When there are rehashing and reallocation of space.

I never understood this concept named “blow up to O(n^2)” in Unordered map what does it actually mean and why does it happen can you explain?

I am not very familiar with the implementation of unordered_map in C++ stl. But apparently, one can easily build a test case to make the map run into O(n) collisions. And as the number of elements/collisions increase, with each insertion it will change the hash function it uses (the prime it chooses for MOD I guess), recompute the hashes for all the elements, and reallocates them, thus costing you a lot of time. More on this here.

The last paragraph (just before the custom hashing solution), he has explained how one can make test cases to blow up a hash map.

Yeah i have seen this link before and read it too but the writer of this blog was so much into technicality that i couldn’t understand anything.

Haha, even I don’t understand much of it. But the only way to gain more knowledge on this is to dig deep into the stl implementation. Until then, lets stick with map.

1 Like

Yes i always use map now instead of unordered_map.

1 Like