Блог пользователя komendart

Автор komendart, история, 9 лет назад, По-русски

Всем привет!

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

Такое ощущение, что стандартная хеш-функция для целых чисел в 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 секунд, потому что хеши всех чисел равны нулю.

Код

Можно ли что-то с этим сделать без написания собственной хеш-функции?

  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Наверно это зависит от версии GCC, или проблема только в порте под Windows — один из последних clang, и две версии gcc под линух работают как надо — http://imgur.com/a/Itm0H

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Вероятно, вы тестили на х64. Там все типы лезут в size_t и поэтому прямо хеши не совпадают

  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +11 Проголосовать: не нравится

    В любом случае завалить изи, если знать кол-во бакетов (там просто по модулю берется, видимо)

    Вот такое у меня (clang) работает долго, при шевелении mgc — мгновенно

    #include <unordered_map>
    #include <iostream>
    
    int main() {
    	std::unordered_map<int64_t, int> x;
    	int64_t mgc = 102877;
    	for (int i = 0; i < 100000; ++i) {
    		x[i * mgc] = 1;
    	}
    	int sum = 0;
    	for (int i = 0; i < 100000; ++i) {
    		sum += x[i * mgc];
    	}
    	std::cout << sum;
    }
    
    

    Вот так видимо валится любой gcc. Естьественно, можно предпосчитать mgc

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Забавно. Но сейчас можно завалить вообще случайно. В задаче 675C - Денежные операции у меня есть тесты только из одинаковых степеней двойки, и они предназначались для решений с переполнением.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Не очень понял, у вас же числа на 2^32 не могут отличаться(т.к до 1е9)

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          2^29 тоже валит, просто в восемь раз меньше чисел с одинаковыми хешами по сравнению с 2^32 (насколько я понимаю)

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            В моем понимании, нет, т.к принципиальность 32 в размере типа данных, а дальше уже важно значение по модулю кол-ва бакетов, которое вроде простое в gcc

            тем более кратных 2^29 вы тоже много не сможете собрать

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
              Rev. 4   Проголосовать: нравится +18 Проголосовать: не нравится

              Я забыл сказать, что там рассматриваются префиксные суммы. Если просто взять 10^5 чисел, равных 2^29 (там в задаче еще говорится, чтобы сумма в массиве была равна нулю, но это не принципиально), то каждое восьмое число будет кратно 2^32. Ну и плюс мое решение с unordered_map валится на этих тестах.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Да, если префиксные суммы, тогда мы часто получаем кратное 2^32, согласен (я просто не читал задачу, думал исходные числа кладутся)

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Вот несколько магических последовательностей bucket:

      Мой clang
      Все мои gcc

      Вот по этому коду. Сейчас посмотрим, что происходит когда значения больше 2**32

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Даже написание своей хэш-функции не поможет
  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Так ваша функция ничем не отличается(т.к результат почти наверно приводится к size_t

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Моя функция даёт на выходе i64, как и на 64-битных системах, но во внутренних преобразованиях hash_set использует size_t, который в данном случае i32 (как ты предположили выше). Или речь про то, что создав какое-то усложнённое распределение результатов hash-функции можно избежать тестов с большим количеством коллизий?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        Например, если сделать хеш рандомным (скажем взять побайтовый полиномиальный со случайными коэффами), то кажется уже не завалишь(по крайней мере так легко)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Как уже выше заметили, std::hash интегральных типов в gcc это просто каст в size_t. В самой же таблице значение хешера берется по модулю числа бакетов, которое простое и выбирается из фиксированного списка, который можно найти в исходниках.

Такая хеш-функция работает в целом хорошо (на достаточно случайных данных), но если нужна защита от направленной атаки коллизиями, то без рандомизации не обойтись. Например, std::hash считает достаточно неплохой murmurhash, но на него тоже при желании нетрудно провести атаку, хоть на x64. У нас даже в прошлом году на ФКН была такая задача.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Например, std::hash считает достаточно неплохой murmurhash

    Можете пояснить эту фразу? Кажется из неё вылетел какой-то кусок:)