Хэш Pearson (64-бит) онлайн
Хэш на таблице перестановки из 256 байт вместо арифметики — придуман Питером Пирсоном в 1990 году. Считается прямо в браузере — текст никуда не отправляется.
Вычислить Pearson (64-бит)
Результат пересчитывается сам, пока вы печатаете. В режиме «По строкам» пустые строки тоже хэшируются — результат всегда совпадает по числу строк со входом. Нужна другая функция — на полной странице калькулятора их 32.
История Pearson hashing
Метод предложил Питер Пирсон в статье «Fast hashing of variable-length text strings» в журнале Communications of the ACM в 1990 году. Изюминка идеи — полный отказ от арифметики: ни умножения, ни сложения по модулю, только табличные подстановки и XOR. На процессорах конца 1980-х — начала 1990-х, где умножение могло стоить в разы дороже простого обращения к памяти, это давало заметный выигрыш в скорости.
Как устроен алгоритм
В основе — фиксированная таблица T из 256 байт, содержащая случайную перестановку чисел 0–255 (сама таблица — часть спецификации алгоритма, придумана один раз и не меняется). Базовый 8-битный вариант Пирсона предельно прост: h = T[h XOR очередной байт], повторяется для каждого байта строки — вся операция сводится к одному XOR и одному обращению к таблице.
Один проход даёт только 8 бит результата — слишком мало для практических нужд. Чтобы получить 64-битный хэш, показанный здесь, базовый проход повторяют восемь раз с разными начальными значениями (обычно 0, 1, 2, …, 7) — каждый проход даёт свой независимый байт результата, вместе они и складываются в 64-битное число.
Характеристики
| Параметр | Значение |
|---|---|
| Длина хэша | 64 бита (16 hex-символов) — 8 проходов по 8 бит |
| Операция на байт | XOR + табличная подстановка (без арифметики) |
| Таблица | 256 байт, фиксированная перестановка |
| Тип | Некриптографический хэш |
| Опубликован | 1990, Питер Пирсон |
Где применяется
- Встраиваемые и маломощные системы без быстрого аппаратного умножения
- Образовательные примеры «хэша без арифметики»
Криптостойкость
Некриптографический хэш — качество зависит от того, насколько «случайна» таблица T; для защиты от намеренной подделки не подходит.