Массивы структур – таблицы
Большинство подобных задач решается с использованием методики, называемой хэшированием. Ее основу составляют различные алгоритмы отображения значения ключа в значение адреса размещения элемента в таблице. Непосредственное преобразование ключа в адрес производится с помощью функций расстановки, или хэш-функций. Адреса, получаемые из ключевых слов с помощью хэш-функций, называются хэш-адресами. Таблицы, для работы с которыми используются методы хеширования, называются таблицами с вычисляемыми входами, хэш-таблицами, или таблицами с прямым доступом.
Основополагающую идею хэширования можно пояснить на следующем примере. Предположим, необходимо подсчитать, сколько раз в тексте встречаются слова, первый символ которых – одна из букв английского алфавита (или русского – это не имеет значения, можно в качестве объекта подсчета использовать любой символ из кодовой таблицы). Для этого в памяти нужно организовать таблицу, количество элементов в которой будет соответствовать количеству букв в алфавите. Далее необходимо составить программу, в которой текст будет анализироваться с помощью цепочечных команд. При этом нас интересуют разделяющие слова пробелы и первые буквы самих слов.
Так как символы букв имеют определенное двоичное значение, то на его основе вычисляется адрес в таблице, по которому располагается элемент, в минимальном варианте состоящий из одного поля. В этом поле ведется подсчет количества слов в тексте, начинающихся с данной буквы. В следующей программе с клавиатуры вводится 20 слов (длиной не более 10 символов), производится подсчет английских слов, начинающихся с определенной строчной буквы, и результат подсчета выводится на экран. Хэш-функция (функция расстановки) имеет вид:
A=(C-97)*L,
Где А – адрес в таблице, полученный на основе двоичного значения символа С; L – длина элемента таблицы (для нашей задачи L=l); 97 – десятичное смещение в кодовой таблице строчного символа "а" английского алфавита.
:prg02_07.asm – программа на ассемблере для подсчета количества слов, начинающихся с определенной строчной буквы :Вход: ввод с клавиатуры 20 слов (длиной не более 10 символов). :Выход: вывод результата подсчета на экран. buf_Oahstruc len_bufdb 11; длина bufjn lenjin db 0 действительная длина введенного слова (без учета Odh) bufjn db 11 dup (20h) – :буфер для ввода (с учетом Cdh) ends 1.data tabdb 26 dup (0) buf buf_0ah<> db Odh.Oah,'$';для вывода функцией 09h (int 21h) .code ;вводим слова с клавиатуры mov ex,20 lea dx.buf movah.Oah ml: int 21h:анализируем первую букву введенного слова – вычисляем хэш-функцию : А=С*1-97 mov b1, buf.bufjn sub Ы. 97 inc [bx] loop ml :выводим результат подсчета на экран push ds popes xor al,al lea di,buf mov ex.type bufjah rep stosb; чистим буфер buf mov ex.26:синвол в buf.buf_1n lea dx.buf mcv b1.97 m2: push bx mov buf.bufjn.bi:опять вычисляем хэш-функцию: А>>С*1-97 и преобразуем "количество" в символьный вид sub b1. 97 mov al.[bx] aam or ax,03030h;в ах длина в символьном виде mov buf.len in.al – mov buf.len_buf.ah;теперь выводим: mov ah, 09h int 21h pop bx inc b1 loop m2
Таким образом, относительно сложная с первого взгляда задача очень просто реализуется с помощью методов хэширования. При этом обеспечивается высокая скорость выполнения операций доступа к элементам таблицы. Это обусловлено тем, что адреса, по которым располагаются элементы таблицы, являются результатами вычислений простых арифметических функций от содержимого соответствующих ключевых слов.
Перечислим области, где методы хэширования оказываются особенно эффективными.
- Разработка компиляторов, программ обработки текстов, пользовательских интерфейсов и т. п. В частности, компиляторы значительную часть времени обработки исходного текста программы затрачивают на работу с различными таблицами – операций, идентификаторов, констант и т. д. Правильная организация работы компилятора с информацией в этих таблицах означает значительное увеличение скорости создания объектного модуля, может быть, даже не на один порядок выше. Кстати, другие системные программы – редакторы связей и загрузчики – также активно работают со своими внутренними таблицами.
- Системы управления базами данных. Здесь особенный интерес представляют алгоритмы выполнения операций поиска по многим ключам, которые также основаны на методе хэширования.
- Разработка криптографических систем.
- Поиск по соответствию. Методы хэширования можно применять в системах распознавания образов, когда идентификация элемента в таблице осу ществляется на основе анализа ряда признаков, сопровождающих объект поиска, а не полного соответствия заданному ключу. Если рассматривать эту возможность в контексте задач системного программирования, то ее можно использовать для исправления ошибок операторов при вводе информации в виде ключевых слов. Подробная информация о поиске по соответствию приведена в литературе.
Но на практике не все так гладко и оптимистично. Для эффективной и безотказной работы метода хэширования необходимо очень тщательно подходить как к изучению задачи на этапе ее постановки, так и к возможности использования конкретного алгоритма хэширования в контексте этой задачи. Так, на стадии изучения постановки задачи, в которой для доступа к табличным данным планируется использовать хэширование, требуется проводить тщательные исследования по направлениям: диапазон допустимых ключей, максимальное количество элементов в таблице, вероятность возникновения коллизий и т. д. При этом нужно знать как общие проблемы метода хэширования, так и частные проблемы конкретных алгоритмов хэширования. Одну из таких проблем рассмотрим на примере задачи.
Пусть необходимо подсчитать количество двухсимвольных английских слов в некотором тексте. В качестве хэш-функции для вычисления адреса можно предложить функцию подсчета суммы двух символов, умноженной на длину элемента таблицы: A=(Cl+C2)*L-97, где А – адрес в таблице, полученный на основе суммы двоичных значений символов С1 и С2; L – длина элемента таблицы; 97 – десятичное смещение в кодовой таблице строчного символа "а" английского алфавита.
Проведем простые расчеты. Сумма двоичных значений двух символов 'а' равна 97+97=194, сумма двоичных значений двух символов 'r' равна 122+122=244. Если организовать хэш-таблицу, как в предыдущем случае, то получится, что в ней должно быть всего 50 элементов, чего явно недостаточно. Более того, для сочетаний типа ab и bа хэш-сумма соответствует одному числовому значению. В случае когда функция хэширования вычисляет одинаковый адрес для двух и более различных объектов, говорят, что произошла коллизия, или конфликт. Исправить положение можно введением допущений и ограничений, вплоть до замены используемой хэш-функции.
Программист может либо применить один из известных алгоритмов хэширования (что, по сути, означает использование определенной хэш-функции), либо изобрести свой алгоритм, наиболее точно отображающий специфику конкретной задачи. При этом необходимо понимать, что разработка хэш-функции происходит в два этапа.
- Выбор способа перевода ключевых слов в числовую форму.
- Выбор алгоритма преобразования числовых значений в набор хэш-адресов.