Функция хеширования для четырех целых чисел без знака (C ++)

Question

Я сейчас пишу программу, которая выдает четыре беззнаковых 32-разрядных целых числа в качестве вывода из определенной функции. Я хочу хешировать эти четыре целых числа, чтобы я мог сравнить выходные данные этой функции с будущими выходными данными.

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

Вывод хеша может быть 32-разрядным или 64-разрядным целым числом. Рассматриваемая функция генерирует многие миллиарды хэшей, поэтому коллизии представляют собой реальную проблему, и я готов использовать большую переменную, чтобы обеспечить как можно меньше коллизий.

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

Answer 1

Почему бы вам не сохранить четыре целых числа в подходящей структуре данных и не сравнить их все? В этом случае польза от их хеширования представляется сомнительной, если только хранение не является проблемой.

Если проблема с хранилищем, вы можете использовать одну из проанализированных хеш-функций здесь .

Answer 2

Вот довольно разумная хеш-функция от 4 целых до 1 целого:

unsigned int hash = in[0];
hash *= 37;
hash += in[1];
hash *= 37;
hash += in[2];
hash *= 37;
hash += in[3];

При равномерно распределенном входе он дает равномерно распределенный выход. Все биты ввода участвуют в выводе, и каждое входное значение (хотя не каждый входной бит) может влиять на каждый выходной бит. Скорее всего, это быстрее, чем функция, которая производит вывод, в этом случае производительность не имеет значения.

Существуют и другие хэши с другими характеристиками, но накопление с умножением на простое число - хорошее начало, пока не доказано обратное. Вы можете попробовать накопить с помощью xor вместо сложения, если хотите. В любом случае, легко генерировать коллизии (например, {1, 0, a, b} сталкивается с {0, 37, a, b} для всех a, b), поэтому вы можете выбрать простое число, которое, по вашему мнению, имеет не имеет ничего общего с какой-либо вероятной ошибкой реализации в вашей функции. Так что если в вашей функции много арифметики по модулю 37, возможно, вместо нее используйте 1000003.

Answer 3

Поскольку хеширование может генерировать коллизии, вам все равно нужно хранить ключи в памяти, чтобы обнаружить эти коллизии. Хеш-карты и другие стандартные структуры данных делают это в своей внутренней бухгалтерии.

Поскольку ключ очень маленький, просто используйте ключ напрямую, а не хэширование. Это будет быстрее и обеспечит отсутствие столкновений.

Answer 4

Я полностью согласен с Винко - просто сравните их все. Если вы все еще хотите хорошую функцию хеширования, вам нужно проанализировать распределение ваших 4 незаполненных целых чисел. Затем вам нужно создать свою функцию хеширования таким образом, чтобы результат был равномерно распределен по всему диапазону 32-битного значения хеширования.

Простой пример - давайте просто предположим, что большую часть времени результат от каждой функции находится в диапазоне от 0 до 255. Затем вы можете легко смешать младшие 8 бит из каждой функции в свой хеш. В большинстве случаев вы находите результат напрямую, просто иногда (когда одна функция возвращает больший результат) вы сталкиваетесь с коллизией.

Подводя итог - без информации о том, как распределяются результаты 4 функций, мы не можем помочь вам с хорошей функцией хеширования.

Answer 5

Может быть немного излишним, но рассмотрим Boost.Hash . Создает очень простой код и хорошие значения.

Answer 6

Попробуйте использовать CRC или FNV . FNV хорош, потому что он быстрый и имеет определенный метод складывания битов для получения «меньших» значений хеша (то есть 12-бит / 24-бит / и т. Д.).

Также преимущество генерации 64-битного хэша из 128-битного (4 х 32-битного) числа вызывает сомнения, поскольку, как и другие люди, вы можете просто использовать исходное значение в качестве ключа в наборе. , Вы действительно хотите, чтобы количество бит в хэше представляло количество значений, которые у вас изначально были. Например, если ваш набор данных имеет 100 000 4X32-битных значений, вам, вероятно, нужно 17-битное или 18-битное хеш-значение, а не 64-битное хеш-значение.

Answer 7

Почему хэш? Похоже, что std :: set или std :: multi set лучше подходят для хранения такого рода вывода. Все, что вам нужно сделать, это заключить четыре целых числа в структуру и написать простую функцию сравнения.