Вопрос по hash, c++ – Строка в целочисленную функцию хеширования с точностью

4

Я хочу хэшировать массив символов в int или long. Результирующее значение должно соответствовать заданному значению точности. Функция, которую я использовал, приведена ниже:

<code>int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}
</code>

Строка для хэширования аналогична "SAEUI1210.00000010_1".

Однако в некоторых случаях это приводит к дублированию значений. Есть ли хорошие альтернативы, которые бы не дублировали один и тот же хеш для разных строковых значений.

Попробуйте использовать CRC 32:en.wikipedia.org/wiki/Crc32 Akira Yamamoto

Ваш Ответ

4   ответа
2

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

2

День рождения проблема.

Возможно, вы захотите проверить, что криптография имеет такие функции, как MD5 (относительно быстрая, и вам все равно, что она небезопасна), но она также будет иметь коллизии.

Совершенные хеши по определению не имеют значения.
1

MD5 или жеША, Есть много открытых реализаций, и вряд ли результат даст дублирующий результат.

Правда, но преобразование тривиально - от 128 бит до 32 бит целое число. Вы получите 2-строчный код (хеш, преобразование int), который фактически создает хеш без коллизий.
Да. Но мое требование также включает в себя тот факт, что результат должен быть целым числом. Хеши MD5 содержат как целые, так и символы. Я думаю, что то же самое для алгоритмов SHA Gayan
13

что он создает повторяющиеся значения для некоторых значений, поскольку диапазон значений хеша меньше, чем пространство хешированных данных.

Теоретически, 32-битный хэш имеет достаточный диапазон, чтобы хэшировать все ~ 6 символьных строк (A-Z, a-z, только 0-9), не вызывая коллизии. На практике хеши не являются идеальной перестановкой входных данных. Учитывая 32-битный хеш, вы можете ожидать получения хеш-коллизий после хэширования ~ 16 битных случайных входов, из-запарадокс дня рождения.

Учитывая статический набор значений данных, всегда можно создать хеш-функцию, разработанную специально для них, которая никогда не будет конфликтовать с самим собой (конечно, размер ее вывода будет по меньшей мереlog(|data set|), Однако, это требует, чтобы вы знали все возможные значения данных заранее. Это называетсяидеальное хеширование.

Что, как говорится,Вот Есть несколько альтернатив, которые должны помочь вам начать (они предназначены для минимизации столкновений)

Единственный способ проверить, какая хеш-функция является «наилучшей». для ваших целей - выполнить эталонный тест выборки данных, который соответствует вашим ожидаемым реальным данным. Используемая вами функция не пытается слишком сильно смешать входные биты, чтобы создать хеш - на каждом шаге смешиваются не более 4 старших бит; и в строках длины & lt; 8, даже если этого не происходит, ваш хэш просто накапливает все символы с небольшим перекрытием.
Какую функцию хэширования лучше всего использовать из тех, что указаны в предоставленной вами ссылке, и той, которую я использую прямо сейчас. Функция, которую я использую, кажется более сложной, чем djb2 и sdbm. Означает ли это, что лучше избегать столкновений? Gayan

Похожие вопросы