Хеш-функция для четырех целых чисел без знака (C++)

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

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

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

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


c++ hash integer
person jakogut    schedule 30.11.2009    source источник
comment
Я хочу хешировать эти четыре целых числа, чтобы сравнить вывод этой функции с будущими выводами. Не обязательно следует. Если бы вы тестировали функцию, которая выводит строки, вам не нужно было бы хэшировать до 32 или 64 бит, чтобы проводить регрессионные тесты. В вашем случае вы создаете себе головную боль, чтобы сэкономить 50% дискового пространства (предположим, вы используете 64 бита вместо 128). Стоит ли оно того? Вы пробовали вместо этого использовать gzip?   -  person Steve Jessop    schedule 30.11.2009
comment
Рассматривали ли вы возможность использования одной или нескольких следующих хэш-функций общего назначения: partow.net/programming /хэш-функции/index.html   -  person    schedule 19.12.2009

Ответы (7)


arrow_upward
8
arrow_downward

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

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

person Vinko Vrsalovic    schedule 30.11.2009

arrow_upward
4
arrow_downward

Вот довольно разумная хеш-функция от 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.

person Steve Jessop    schedule 30.11.2009

arrow_upward
3
arrow_downward

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

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

person Will    schedule 30.11.2009

arrow_upward
1
arrow_downward

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

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

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

person Tobias Langner    schedule 30.11.2009

arrow_upward
0
arrow_downward

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

person Graphics Noob    schedule 30.11.2009

arrow_upward
0
arrow_downward

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

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

person Adisak    schedule 30.11.2009

arrow_upward
0
arrow_downward

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

person larsmoa    schedule 30.11.2009