Какие "взломы" хэш-функции вы используете?

#data-structures #hash #hashmap #hashtable #hashcode

#структуры данных #хэш #hashmap #хэш-таблица #хэш-код

Вопрос:

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

значение * Размер хэш-таблицы

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

1. Эти типы «взломов» обычно не полезны. Они работают в особых случаях, но в общем случае они страдают от той или иной проблемы. Ваш случай с вещественными числами, например, может быть ужасным, когда диапазон входных значений очень мал. Потому что многие числа преобразуются в одно и то же хэш-значение. Я проголосовал за закрытие этого как слишком широкого.

2. В примере с вещественными числами возникла бы проблема, если входные данные распределены неравномерно, это было бы нормально для случайных входных данных. Диапазон уже определен — от 0 до 1. Единственной причиной для использования таких «взломов» была бы скорость.

Ответ №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 содержит вариацию этой функции, подходящую для алгоритма двойного хеширования.