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

Because hashing can generate collisions, you have to keep the keys in memory anyway in order to discover these collisions. Hashmaps and other standard datastructures do do this in their internal bookkeeping.

As the key is so small, just use the key directly rather than hashing. This will be faster and will ensure no collisions.

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

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

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

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

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

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

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

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

Might be a bit overkill, but consider Boost.Hash. Generates very simple code and good values.

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