64-битное мультипликативное хеширование

Question

Я работаю над быстрым 64-битным хешем.Многие существующие безопасные хеш-функции слишком медленные, некоторые некриптографические хеш-функции, такие как FNV, просто плохие.

Ну, я придумал FNV-подобный хеш:

UINT64 hash=0;

// for each input byte
hash=(hash^(input_byte+1))*HASH_PRIME;

Mainвопрос о HASH_PRIME.Часто мы можем увидеть термин «золотое сечение» для мультипликативного хеширования.Для 64-битного хэша золотое сечение равно 0x9e3779b97f4a7c13.

Я проверил 32-битное золотое сечение для периода в PRNG:

DWORD hash=0;
// loop
hash=(hash^1)*0x9e3779b9;
rnd_out=hash>>24;

Хорошее значение здесь может привести кпериод 0xFFFFFFFF - то есть максимально возможный.Это золотое сечение дает заметно меньший период.

или просто

DWORD hash=~0;
// loop
hash*=0x9e3779b9;
rnd_out=hash>>24;

И опять же, достаточно хороший множитель может дать период 0x3FFFFFFF байтов.Золотое сечение здесь приводит к гораздо более короткому периоду.

Никогда не тестировал 64-битные простые числа - слишком дорого в вычислительном отношении.

Важен ли период для моего хэша?А где найти хороший 64-битный HASH_PRIMES и как проверить такие вещи?

Answer 1

Вы делаете это как упражнение?в противном случае я бы посоветовал взглянуть на хорошо известные хэш-функции, такие как lookup8 и семейство Боба Дженкина (http://burtleburtle.net/bob/hash/) и ропот Остина Эпплби http://code.google.com/p/smhasher/ (убийца скорости и мой любимый).Хорошие хеш-функции сложно создать ... и если вы хотите получить хеш-код типа «зашкаливать», то отпечатки Рабина трудно превзойти.И чтобы убедиться, что ваши хэши достойны, если вы действительно хотите откатить свои собственные, используйте хеш-тесты Appleby и Jenkins (пытки и smhasher)

Answer 2

Не уверен насчет первых двух примеров.Но в третьем, чтобы получить полный период из кода, вам нужно добавить нечетное число.В противном случае это будет максимальный период 65537. Он может быть ниже 3. Может даже существовать фиксированная точка.

Где бы вы ни получили 0x3FFFFFFF в течение хорошего периода, это неверно.В одном из томов Кнута это обсуждается слишком подробно.

Множитель должен иметь форму 4n + 1, и должно быть нечетное добавление