Всем привет!
Я не знаю, возможно, эта тема где-то уже поднималась, но быстрый гуглинг не помог.
Такое ощущение, что стандартная хеш-функция для целых чисел в 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)) == std::hash<long long>()(x)
Например, код ниже работает в запуске на Codeforces более 10 секунд, потому что хеши всех чисел равны нулю.
Код
Можно ли что-то с этим сделать без написания собственной хеш-функции?
Наверно это зависит от версии GCC, или проблема только в порте под Windows — один из последних clang, и две версии gcc под линух работают как надо — http://imgur.com/a/Itm0H
Вероятно, вы тестили на х64. Там все типы лезут в size_t и поэтому прямо хеши не совпадают
В любом случае завалить изи, если знать кол-во бакетов (там просто по модулю берется, видимо)
Вот такое у меня (clang) работает долго, при шевелении
mgc— мгновенноВот так видимо валится любой gcc. Естьественно, можно предпосчитать
mgcЗабавно. Но сейчас можно завалить вообще случайно. В задаче 675C - Денежные операции у меня есть тесты только из одинаковых степеней двойки, и они предназначались для решений с переполнением.
Не очень понял, у вас же числа на 2^32 не могут отличаться(т.к до 1е9)
2^29 тоже валит, просто в восемь раз меньше чисел с одинаковыми хешами по сравнению с 2^32 (насколько я понимаю)
В моем понимании, нет, т.к принципиальность 32 в размере типа данных, а дальше уже важно значение по модулю кол-ва бакетов, которое вроде простое в gcc
тем более кратных 2^29 вы тоже много не сможете собрать
Я забыл сказать, что там рассматриваются префиксные суммы. Если просто взять 10^5 чисел, равных 2^29 (там в задаче еще говорится, чтобы сумма в массиве была равна нулю, но это не принципиально), то каждое восьмое число будет кратно 2^32. Ну и плюс мое решение с unordered_map валится на этих тестах.
Да, если префиксные суммы, тогда мы часто получаем кратное 2^32, согласен (я просто не читал задачу, думал исходные числа кладутся)
Вот несколько магических последовательностей bucket:
Вот по этому коду. Сейчас посмотрим, что происходит когда значения больше 2**32
hash(x) = static_cast<size_t>(x)в gcc, определенноТак ваша функция ничем не отличается(т.к результат почти наверно приводится к size_t
Моя функция даёт на выходе i64, как и на 64-битных системах, но во внутренних преобразованиях hash_set использует size_t, который в данном случае i32 (как ты предположили выше). Или речь про то, что создав какое-то усложнённое распределение результатов hash-функции можно избежать тестов с большим количеством коллизий?
Например, если сделать хеш рандомным (скажем взять побайтовый полиномиальный со случайными коэффами), то кажется уже не завалишь(по крайней мере так легко)
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.
Probably you have 64bit OS and compiler. There some discussion in Russian threads with code to fail it
Как уже выше заметили, std::hash интегральных типов в gcc это просто каст в size_t. В самой же таблице значение хешера берется по модулю числа бакетов, которое простое и выбирается из фиксированного списка, который можно найти в исходниках.
Такая хеш-функция работает в целом хорошо (на достаточно случайных данных), но если нужна защита от направленной атаки коллизиями, то без рандомизации не обойтись. Например, std::hash считает достаточно неплохой murmurhash, но на него тоже при желании нетрудно провести атаку, хоть на x64. У нас даже в прошлом году на ФКН была такая задача.
Можете пояснить эту фразу? Кажется из неё вылетел какой-то кусок:)
Там было
std::hash<string>, но кф выкинул<>:)