III Международная студенческая научная конференция Студенческий научный форум - 2011

Цель работы. Подбор оптимальной хеш-функции для создания хеш-таблиц словарей языков программирования. Использование прямого (хеш) доступа в эти таблицы значительно ускоряет стадии лексического анализа и генерации кода компиляторов. В качестве примеров рассмотрены два словаря языков программирования: Паскаль версии Delphy 6 и C# MS Visual Studio 2008.

Словарь ЯП Pascal

Всего 55 терминальных символов в словаре. Поэтому есть большая вероятность найти однобайтовую хеш-функцию без коллизий и с высоким быстродействием. Пакет OSPGEN 2.2 представляет удобный инструмент для поиска и статистического анализа таких хеш-функций [1].

Итак, найдены следующие хеш-функции без коллизий:

• Функция деления
• Мультипликативная функция
• Функция СРС

Самая быстрая (как наиболее простая) - функция деления: 678 тактов процессора или 202нс (для процессора PentiumIV-D 3Ггц.

Для функций выделения байта и 8 битов не удалось подобрать вариантов без коллизий (минимум - 1 коллизия).

Вкладка «Панель управления» пакета не требует комментариев. «Графопостроитель» для функции с одним параметром также понятен. В частности, для функции деления видно, что вариантов без коллизий достаточно много, особенно при значениях параметра V, близких к 20 тыс.

Когда хеш-функция подбирается по двум параметрам, ее коллизионная картина становится трехмерной. Чтобы не усложнять графическую часть пакета, было решено третье измерение (число коллизий) отображать степенью яркости пикселя на координатной плоскости параметров. Для нуля цвет - черный, чем больше коллизий, тем ярче пиксель.

Такой подход к статистическому анализу позволяет сразу увидеть качественную характеристику найденной функции и задачи в целом для данного массива символьных строк. А можно ли увидеть ее в статистических таблицах, содержащих тысячи значений? Тем не менее, пакет OSPGEN их также создает для более детального анализа.

Теперь проведем аналогичный эксперимент для словаря C#.

Словарь ЯП C#

Всего в словаре 77 термов. Вероятность найти эффективную хеш-функцию меньше, чем для Паскаля, но достаточно высока. При заполнении однобайтовых хеш-таблиц на 30% и менее почти всегда находится функция без коллизий среди стандартных вариантов, включенных в пакет OSPGEN. Для особых случаев, когда требуется функция без коллизий, ее можно запрограммированть на любом языке (лучше - на ассемблере) и подключить к пакету как dll-файл.

Проведем поиск хеш-функций, аналогичный случаю словаря Паскаля. Для этого достаточно подать на вход пакета текстовый файл, содержащий в строке по одному слову из словаря языка.

Найдена только одна хеш-функция без коллизий, на основе алгоритма СРС. Этот вариант дает в среднем лучший результат по числу коллизий, т.к. алгоритм очень равномерно «перемешивает» входные данные. Не случайно на СРС основаны многие программные и аппаратные методы кодирования и шифрования.

Недостаток СРС хеш-функции - низкое быстродействие: 2171 такт процессора (646нс) по сравнению с функцией деления (198нс). Осталось выбрать: использовать найденный вариант СРС или усложненный вариант функции деления (с рехешированием или строками переполнения). Для этого надо записать второй вариант на каком-нибудь языке программирования (на ассемблере, очевидно, будет лучший результат). Оформить функцию как dll-файл в соответствие с инструкцией, прилагаемой к пакету. С помощью вкладки «Подключение внешней функции» исследовать быстродействие и коллизионную картину стандартными средствами пакета.

Вывод. Пакет OSPGEN 2.2, разработанный на кафедре МОВС МИРЭА, представляет эффективный инструмент исследования и поиска хеш-функций для разных областей ИТ технологий. Целесообразно продолжить работу по его развитию, в частности для автоматизации поиска хеш-функций (например, «выделение байта»), а также для возможности отображения коллизионной картины в 3D-графике.

Литература

1. Е.Р. Абдулин, А.Л. Бескин. «Построение хеш-функций и анализ их свойств». Теоретические вопросы вычислительной техники, программного обеспечения и информационных технологий в муниципальном хозяйстве: Межвузовский сборник научных трудов / Государственное образовательное учреждение высшего профессионального образования «Московский государственный институт радиотехники электроники и автоматики (технический университет)» M., 2005 - .232 с.