Алгоритм хеширования djb2 на Ассемблере

Алгоритм djb2 - одна из самых известных некриптографических хеш-функций для строк. Разработанный выдающимся математиком Дэниелом Бернстайном, который также хорошо известен по алгоритму SipHash-2-4, djb2 стал настоящим стандартом благодаря балансу между простотой реализации, скоростью работы и качеством распределения хешей. Это та самая функция, к которой обращаются, когда нужен быстрый и надежный хеш для хеш-таблицы.

Алгоритм был впервые опубликован Дэниелом Бернстайном много лет назад в знаменитой новостной группе comp.lang.c. В мире Unix и C эта группа была местом, где рождались и обсуждались самые важные инженерные решения. Главное преимущество djb2 - компактность и эффективность на низком уровне. В эпоху программирования под DOS и на Ассемблере, когда каждый байт и каждый такт процессора были на счету, она стала идеальным решением. Функция использует всего две основные операции: сдвиг и сложение, что позволяет реализовать ее буквально несколькими инструкциями CPU.

hash = hash * 33 + c
Или вариант на Ассемблере, если он вам более приятен:В основе функции лежат два ключевых числа: 33 и 5381. Число 33 - не простое, но оно оказалось эмпирически лучшим кандидатом для перемешивания битов. С точки зрения программирования, его гениальность в том, что умножение на 33 можно заменить простой конструкцией: (hash << 5) + hash. Сдвиг влево на 5 бит - умножение на 32, прибавление исходного значения дает те самые 33. Эта конструкция работала молниеносно даже на процессорах 286, а тем более на новых. Например:или даже такПочему 5381? Это стартовое значение хеша. В шестнадцатеричном виде это 0x1505. Оно достаточно большое, чтобы начать перемешивание битов с первого же символа, но при этом не вызывает слишком быстрого переполнения на коротких строках. Точная причина его выбора остается на совести автора, но именно это число показало себя лучше многих других констант.

Также существует две версии djb2, и здесь часто возникает путаница. Дело в том, что обе версии считаются каноническими, так как были предложены самим Бернстайном. Классическая версия (через ADD) - самая распространенная реализация, которую можно встретить в учебниках и исходниках. Оригинальная версия (через XOR) - та, которую позже стал предпочитать сам автор. Она обладает немного другими свойствами перемешивания и может быть предпочтительнее для определенных типов данных.

hash = hash * 33 ^ c
И Ассемблер, конечно же.Обе версии работают превосходно. Выбор между ними обычно сводится к традиции или незначительным нюансам распределения хешей.

Простая идея, реализованная в djb2, может жить десятилетиями. Это не просто функция, а часть истории программирования. Ее ценят и олдскульные кодеры, пишущие на ассемблере, и современные разработчики, которым важны эффективность и проверенные решения.

В приложении примеры программ с исходными текстами, демонстрирующие вычисление различных вариантов хешей djb2 для введенной строки.

Комментарии

Добавить комментарий

Для вставки цитаты выделите текст и нажмите сюда

Имя*:

Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.

Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.