O Torvalds Linus

Сайт о *nix системах и всем что с ними связано

Возможно, вы желаете знать, откуда взялась константа 0х9еЗ 70001 (= 2 654 404 609). Данная хеш – функция основана на умножении индекса на подходящее большое число с такой целью, чтобы результат вызвал переполнение, и значение 32 – битовой переменной можно было считать результатом операции деления с остатком. Кнут предположил, что хорошие результаты можно получить, когда большой сомножитель является простым числом, примерно равным золотому сечению от 232 (32 бита —это размер регистров в архитектуре 80×86). Число 2 654 404 609 является простым, близким к 232х(л/5 —1)/2. Кроме того, на него легко умножать, выполняя сложение и сдвиг битов, потому что оно равно 231 + 229-225 + 222-219-216 + 1.

Read the rest of this entry »