komendart's blog

By komendart, history, 4 years ago, translation, In English,

Hi everyone!

I don't know, maybe this topis was discussed on Codeforces but google didn't help me.

It seems that standart hash function in gcc works badly (for Visual C++ all is good).

For 0 ≤ x ≤ 232 - 1

std::hash<int>()(x) == x 
std::hash<long long>()(x) == x

For any other number

std::hash<long long>()(x + (1LL << 32)) == std::hash<long long>()(x)

For example code in spoiler works more than 10 seconds on Codeforces because hashes of all numbers are equal to zero.

Code

What can we do without writing our own hash function?

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

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

On a laptop with gcc version 4.9.2 (Debian 4.9.2-10) compiling with g++ -std=c++11 this executes without any problem in 0m0.053s.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Probably you have 64bit OS and compiler. There some discussion in Russian threads with code to fail it