Про gcc и std::hash

Revision ru1, by komendart, 2016-05-18 19:17:19

Всем привет!

Я не знаю, возможно, эта тема где-то уже поднималась, но быстрый гуглинг не помог.

Такое ощущение, что стандартная хеш-функция для целых чисел в gcc работает плохо (для Visual C++ все нормально).

Для 0 ≤ x ≤ 232 - 1

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

Для остальных чисел верно

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

Например, код ниже работает в запуске на Codeforces более 10 секунд, потому что хеши всех чисел равны нулю.

Код

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English komendart 2016-05-18 19:54:02 32 Tiny change: ' '
ru3 Russian komendart 2016-05-18 19:53:24 32 Мелкая правка: '< 32)) == x\n~~~~~\n\' -> '< 32)) == std::hash<long long>()(x)\n~~~~~\n\'
en4 English komendart 2016-05-18 19:43:41 15 Tiny change: 're than 10s on Codef' -
en3 English komendart 2016-05-18 19:31:42 15 Tiny change: ' summary="Код">\n\n~~~~' -> ' summary="Code">\n\n~~~~'
en2 English komendart 2016-05-18 19:28:39 11 Tiny change: 't google don't help m' -> 't google didn't help m'
en1 English komendart 2016-05-18 19:28:09 923 Initial revision for English translation
ru2 Russian komendart 2016-05-18 19:18:56 77
ru1 Russian komendart 2016-05-18 19:17:19 885 Первая редакция (опубликовано)