Как работает эта функция хеширования от CryEngine?

unsigned int HashString( const char *string ) {
    const char* p;
    unsigned hash = 40503;

    for ( p = string; *p != '\0'; ++p ) {
        hash += *p;
        hash += ( hash << 10 );
        hash ^= ( hash >> 6 );
    }
    hash += ( hash << 3 );
    hash ^= ( hash >> 11 );
    hash += ( hash << 15 );

    return hash;
}

Просто бродить по их коду. Я никогда раньше не видел такую ​​функцию хеширования.

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

Что именно это делает?

Источник

3 ответа

Решение

Прочитайте здесь для общего обзора, и перейдите к "Единовременному хэшу" (Дженкинс), который совпадает с этим.

Также смотрите эту запись в Википедии, упомянутую в этом ответе.

"Как именно это хороший хэш?" Не совсем. Эти сдвиги немного произвольны, что объясняется в основном некоторыми эвристическими и эмпирическими тестами.

Источник

Кто сказал, что он хорошо хэшируется?

Хеш-функция отображает вход, который в этом случае является строкой, на выход, в этом случае unsigned int, Размер ввода (number of usable characters) ^ number of characters in the string где ^ "возведен во власть".

Если ваша входная строка может содержать только символы 0 а также 1 тогда размер ввода будет 2^ number of characters in the string

Размер вывода фиксирован, на наибольшее число, представимое в unsigned int,

Это означает, что существует "количество символов в строке", где размер ввода будет больше, чем размер вывода. По принципу голубиного отверстия у вас обязательно начнутся столкновения. В действительности у вас, вероятно, были столкновения до того, как этот порог был достигнут.

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

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

Источник

Такого рода вещи будет гораздо легче понять, когда вы получите более широкое понимание бинарной арифметики в целом. Проще перейти от математики к коду, чем наоборот.

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

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

Источник
Другие вопросы по тегам