Как работает эта функция хеширования от 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;
}
Просто бродить по их коду. Я никогда раньше не видел такую функцию хеширования.
Я не слишком опытен, когда дело доходит до побитовых операций, я знаю, как работает сдвиг битов и маскирование, но только в зачаточном сценарии, таком как проверка, установлены ли биты.
Что именно это делает?
Решение
Читать Вот для общего обзора, и перейдите к «Единовременному хэшу» (Дженкинс), который совпадает с этим.
Также увидеть это Википедия, упоминается в этот ответ.
«Как именно это хороший хэш?» Не совсем. Эти сдвиги немного произвольны, что объясняется главным образом некоторыми эвристическими и эмпирическими тестами.
Другие решения
Такого рода вещи будет намного легче понять, когда вы получите более широкое понимание бинарной арифметики в целом. Проще перейти от математики к коду, чем наоборот.
Мне не очень повезло с поиском хорошего интернет-ресурса, но я был очень доволен предыдущим выпуском этот учебник когда я был в школе Вы также можете найти некоторые онлайн лекционные заметки из хорошего класса CS по двоичной арифметике.
Этот сайт может дать вам общее представление о теории хеширования. Хотел бы я порекомендовать там учебник, но я еще не наткнулся на действительно ясный учебник по теории чисел.
Кто сказал, что он хорошо хэшируется?
Хеш-функция отображает вход, который в этом случае является строкой, на выход, в этом случае 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 или любую другую структуру данных, убедитесь, что она настроена на ваш конкретный вход. Не берите в руки первое, что вы найдете в Интернете. Хорошая хеш-функция обеспечивает как можно меньше коллизий для ваших конкретных входных данных.
Хеш-функция общего назначения может быть неоптимальной в вашем конкретном случае. Хеш-функция, специально предназначенная для некоторых входов (и это вполне может быть такой функцией), может работать значительно хуже ваш входы.