Какую функцию хэша «хаки» вы используете?

Question

Функция хэширования может зависеть от данных. Например (из статьи this), если ваши данные являются строками, и почти все они имеют разную длину, тогда простая длина строки может быть очень хорошей хэш-функцией (не очень реалистичной, я знаю). Или, например, действительные числа от 0 до 1 может иметь простой хэш-функции:

значение * sizeOfHashTable

Я интересно, если вы используете такие хэш-функции, которые специально созданы вокруг входов? Есть еще примеры?

Answer 1

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

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

• Функция должна иметь хорошее распределение (псевдослучайное) в тестовом наборе данных. Хорошая идея - использовать в хеш-функции «эффект снежного краха», при изменении одного бита во входных данных изменяется ~ половина бит в выходном значении.

• Для внешних входных данных функция хэша должна быть «универсальной», т. Е. Сопротивляться попыткам возникновения столкновения.

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

const unsigned int S_block[256] = { ... }; 
#define NLF(h, c) (S_block[(unsigned char)(c + h)]^c) 

unsigned int hash(const char *key) { 
unsigned int h = 0x1F351F35; 
char c; 
while(c = *key++) 
    h = ((h << 7) | (h >> (32 - 7))) + NLF(h, c); 
h ^= h >> 16; 
return h^(h >> 8); 
} 

Как практический пример, см, используя вариации этой функции в моей программе emcSSH. Файл htable.c содержит изменение этой функции, подходящее для алгоритма double hashing.