Хеш-функция с целочисленным переполнением PHP - PullRequest
Новая
       17

Хеш-функция с целочисленным переполнением PHP

3 голосов
/ 06 января 2011

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

Я хочу использовать хэш-функцию djb2 в PHP для хеширования ключей в нечто вроде идентификатора сегмента (индекс домена для SimpleDB). Он переполняет беззнаковые длинные целые, поэтому я не могу сделать это одинаково в обычном PHP, потому что собственные встроенные PHP-выражения имеют 32-битную подпись.

Итак, я попробовал математические расширения PHP bc и libgmp , которые допускают произвольную длину, и обходят проблему подписи / масштаба, но они делают ints "слишком большими" - т.е. они не переполняются.

Использование GMP, в частности, работает и, похоже, дает согласованные результаты, но, очевидно, на порядок медленнее, чем в C (0m0,017s против 0m0,002s). Я не знаю, является ли это просто потому, что это PHP против C, или это было бы значительно быстрее в PHP, если бы я мог заставить его переполниться. Я бы лучше проверил и выяснил, но я не вижу способа, чтобы это произошло.

Итак, есть ли способ заставить ULONG максимум в PHP? Должен ли я обернуть функцию C в расширение PHP? Или, учитывая, что я планирую хэшировать только короткие ключи (вероятно, 64 символа или меньше), это обеспечит серьезное снижение доходности?

1 Ответ

0 голосов
/ 14 августа 2014

Почему, по вашему мнению, эти хэш-функции требуют более 32 бит?long типам не гарантируется такой размер, они просто> = 32 бита.На моих 32-битных платформах long всегда 32 бит.

Эти заметки, на которые вы ссылались, я полагаю, были написаны в те времена, когда 64-битные были не так популярны, как в наши дни, а также до long longбыл введен тип (который равен> = 64 бита даже на 32-битных платформах), поэтому автор просто использовал самый большой тип, который был доступен тогда.

Этот хэш "djb2" - это просто еще один вариант хеш-функциипочти аналогичен линейному конгруэнтному генератору, и это известно давно.Явная операция по модулю была заменена переполнением, которое фактически равно "modulo 2^(sizeof long)".Это может быть (хотя и не совсем точно) полезно для производительности, если скомпилировано как C, но, вероятно, не так хорошо для качества хэширования.И это не имеет смысла в PHP, потому что число будет повышаться до double и расти до бесконечности.

Я бы предложил использовать этот алгоритм хеширования с обычными целыми числами PHP, но улучшу хеширование, добавивявное по модулю с делителем, который является простым числом, меньшим PHP_INT_MAX (кстати, вы проверяли этот предел для 64-битных сборок PHP?).Возможно, нужно изменить множитель (33), чтобы получить лучшее распределение хеша со строками, которые должны быть хешированы.

...