jerdno's blog

unordered_map hashing function
By jerdno, history, 4 years ago, In English

Hi,

I'm trying to move from using Java for CP to C++. As such I'm missing some knowledge, but usually I'm able to google it. Today I encountered something that doesn't make sense for me and wasn't able to find good answer for that. In this solution for latest Div 3 contest (problem D) I used unordered_map and received TLE. Then I changed it to map and got Accepted.

I know that what are the differences between map and unordered_map, but I would expect unordered_map to be even faster then map. Does hashing ints really creates so many conflicts, or I'm missing something (for example initialization of size of hash table)?

Thanks.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think map guarantees you O(logn) but unordered_map can be O(n) in the worst case.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

They usually include testcases where the numbers are such that unordered_map degenerates to O(n) caused by hash collisions. Simply use map instead.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/blog/entry/62393

use this custom hash

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to make an unordered_map solution pass: 85405513

This line does the trick:

cnts.reserve(1024);

It runs in 2/3 the time compared to my solution using map. Im not sure why it works though, and its reliability.

→ Reply