Чрезвычайно быстрая хеш-функция с разрешенными коллизиями
Мой ключ — это 64-битный адрес, а вывод — это 1-байтовое число (0-255). Столкновения допускаются, но вероятность их возникновения должна быть низкой. Кроме того, предположим, что количество вставляемых элементов невелико, скажем, не более 255, чтобы минимизировать эффект дырки.
Адреса являются адресами функций в программе.
Решение
uint64_t addr = ...
uint8_t hash = addr & 0xFF;
Я думаю, что соответствует всем вашим требованиям.
Другие решения
Я бы XOR вместе 2 младших бита (младшие байты), если это плохо распределяется, затем добавить третий и т. Д.
Это объясняется следующим: адреса функций не распределяются равномерно. Проблема обычно заключается в младших (lsb) битах. Функции обычно должны начинаться с адресов, кратных 8/8/16, поэтому 2-4 lsb, вероятно, не имеют смысла. Используя XOR для следующего байта, вы должны избавиться от большинства этих проблем, и это все еще довольно быстро.
Я думаю, что адреса функций, скорее всего, будут выровнены (см. этот вопрос, например). Кажется, это указывает на то, что вы хотите пропустить младшие значащие биты, в зависимости от выравнивания.
Итак, возможно, возьмем 8 бит, начиная с бита 3, то есть пропуская младшие 3 бита (биты с 0 по 2):
const uint8_t hash = (address >> 3);
Это должно быть очевидно из проверки вашего набора адресов. В шестнадцатеричном виде следите за самой правой цифрой.
Как насчет:
uint64_t data = 0x12131212121211B12;
uint32_t d1 = (data >> 32) ^ (uint32_t)(data);
uint16_t d2 = (d1 >> 16) ^ (uint16_t)(d1);
uint8_t d3 = (d2 >> 8) ^ (uint8_t)(d2);
return d3;
Он объединил все биты ваших 8 байтов с 3 сменами и тремя инструкциями xor.