2021-03-25 16:12:00
Известный факт, что CPython использует алгоритм djb2 для реализации своей строковой хеш-функции и выглядит он так:
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c;
return hash;
}
А hash уже применяется в реализации dict, set и вообще везде, где нужна хэшируемость объекта. И, вроде бы, всё с ней хорошо, работает годами, только непонятно нихуя.
Магическое число 5381— простое число
— недостаточное число
— нечётное число
— имеет бинарное представление 001/010/100/000/101
— в сравнении с другими имеет хороший лавинный эффект
Я не настоящий сварщик, поэтому будем считать, что такой ответ нас устраивает. Daniel J. Bernstein, автор сия алгоритма, отвечает на пацана, что всё посчитал и ему это число зашло больше остальных. Но вместо 5381 может быть и любое другое.
hash = ((hash << 5) + hash) + cЧто тут вообще происходит?! А это не более, чем hash * 33 + c. Так наши деды экономили процессорное время и умножали числа битовым сдвигом. hash << 5 это hash * 32, ну и плюс ещё один hash, вот и выходит 33.
Самое популярное объяснение зачем там 33 звучит так — “потому что”: the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained. То есть ещё одно магическое число и смиритесь с этим. Но истина чуть сложнее.
— даёт хорошее распределение (aka меньше коллизий)
— это выяснилось опытным путём
Из диапазона чисел от 1 до 256 выбросили все чётные числа (криптографы их ненавидят). Поэтому уже не 42. И все они, в общем-то подходят. Но некоторые можно представить битовым сдвигом, это 17, 31, 33, 63, 127 и 129. Daniel посчитал, что 33 выглядит прикольно и взял именно его.
В итоге, в ключевой для хеш-таблиц функции, в ключевой для языка структуре данных, используются 2 магическим образом подобранные константы. Вот и живите с этим.
965 views13:12
Т
