2.4 Структура и форматы таблиц хеширования
2.4.1 Непосредственная и косвенная адресация
а) Индексные таблицы хеширования (ТХ)
Для размещения данных, хранящихся в ТХ совместно с ключевыми словами или их идентификаторами, часто требуются большие объемы памяти. Размеры ЭД могут изменяться, однако, как правило, таблицы хеширования строятся исходя из максимальной длины. В результате – часть памяти используется непроизводительно. Кроме того, с увеличением длины записей возрастает трудоемкость (время) поиска. Допуская некоторые увеличения количества обращений к памяти (что неизбежно при использовании многоуровневой памяти) можно повысить эффективность поиска. Для этого ЭД необходимо размещать в специально отведенной области, а в основной таблице хеширования хранить только указатели, содержащие адреса элементов в этой области, а также соответствующие идентификаторы. При такой структуре в процессе поиска проверке подвергаются только ключевые слова (или их идентификаторы) и обращение к отдельной области памяти производится только после того, как будет найден требуемый элемент. Преимущество предлагаемой схемы также состоит в том, что при необходимости основную таблицу хеширования (которую в дальнейшем будем называть индексной таблицей хеширования) можно без особых затруднений поместить в другую область.
Индексные таблицы хеширования достаточно распространены, особенно в СУБД. Однако с их помощью не всегда удается достичь желаемого результата. Например, при использовании только коротких имен (ключевых слов), внутренней адресации (т.е. цепочек внутри ТХ, и т.д.).
б) Комбинированная адресация в хеш-таблице (ступенчатое хеширование)
Рассмотренный выше принцип построения ТХ можно рассматривать как простейшую форму косвенной адресации. Такая адресация является обязательным элементом индексной хеш-таблицы. Ее можно сделать более эффективно, если наряду с косвенной адресацией использовать и прямую (непосредственную) адресацию. Для задания режима адресации в каждой ячейке таблицы отводится специальный разряд, именуемый флажком связи.
Напомним, как аналогичный принцип реализуется в современных ЭВМ (80 г.г.).
Можно было бы прямо в поле КОП указать, является ли содержимое адресного поля константой или адресом. Это может быть задано специальным признаком D/I (непосредственная или косвенная адресация).
Если D/I = 0 - в поле адрес > адрес непосредственный или абсолютный.
Если D/I = 1 - истинный адрес извлекается из специальной таблицы, либо из специального регистра, номер указывается в поле адреса (это метод косвенной адресации).
Схема косвенной адресации может быть многоуровневой. Такой комбинированный вариант адресации может быть использован при построении таблиц хеширования. В этом случае функцию флажка D/I выполняет флажок связи. Если значение этого флажка = 0, то это означает, что искомые данные хранятся в той же ячейке хеш-таблицы, если же флажок связи = 1, то соответствующее информационное поле нужно рассматривать как хеш-связь, т.е. адрес второй таблицы, содержащей, как правило, значительно меньшее количество слов, но большей разрядности. Если нужно хранить записи еще большего размера, то можно организовать еще одну (третью) таблицу.
Введение ступенчатого хеширования обусловлено также тем, что для обращения к данным, расположенным во ВЗУ, адреса должны содержать обычно не менее 20 разрядов. Указатели такой длины нерационально размещать в ТХ.
Метод ступенчатого хеширования успешно применяется при решении ряда задач – в частности, – банковских, ЯВУ, ИИ, обработки списков.
2.4.2 Форматы таблиц хеширования
Форматы и содержимое ячеек таблицы хеширования
Размер ячейки хеш-таблицы в первую очередь определяется объемом той информации, которую в ней предполагается хранить. Следует учитывать и возможность использования укороченного идентификатора вместо ключевого слова (при использовании метода деления), а также применения комбинированной адресации. В то же время в соответствии с принятой в ЭВМ адресацией памяти ячейки должны занимать целое число байтов или машинных слов. Иногда появление одного лишнего байта может привести к удлинению ячейки на целое слово. Этого можно избежать, оставляя резервное пространство в конце последнего слова ячейки.
В число обязательных компонент содержимого ячейки хеш-таблицы входят:
- ключевое слово (или идентификатор);
- соответствующие данные (или указатель этих данных);
Если используется внутренняя адресация, то дополнительно резервируется место для флажка “конец последовательности пробинга” (или специальное слово в конце цепочки) – со специальным кодом.
В состав ячейки хеш-таблицы может также входить:
- флажок “занято”;
- флажок коллизии;
- флажок вычеркивания;
- флажок связи.
Могут использоваться комбинации этих флажков или специальные коды.
При поиске по многим ключам структура строки (ячейки) усложняется, т.к. в ячейку потребуется записывать несколько ключевых слов (идентификаторов) и указателей.
Способы индексации слов в хеш-таблице
Как правило, длину каждой ТХ надо знать заранее. Предположим, что запись состоит из k слов (ячеек). В ОП с произвольным доступом обычно занимают по k – последовательно расположенных слов. Например:
1) (1, 1) (2, 1) (3, 1) …
(1, 2) (2, 2) (3, 2) …
(1, 3) (2, 3) (3, 3) …
(1, 4) (2, 4) (3, 4) …
k = 4 – это количество слов в записи.
Это означает, что их вычисленные адреса должны быть кратны k (т.е. исходный хеш-адрес, полученный с помощью некоторого алгоритма, впоследствии умножается на k).
2) Таблицу можно разделить на k секций:
(1, 1) (1, 2) (1, 3) (1, 4)
(2, 1) (2, 2) (2, 3) (2, 4)
(3, 1) (3, 2) (3, 3) (3, 4)
(4, 1) (4, 2) (4, 3) (4, 4)
. . . .
. . . .
. . . .
В этом случае хеш-адрес рассматривается как индекс любого элемента записи, распределенной по k секциям. При таком способе требуется меньше вычислений, что особенно важно в случае, если хеш-таблица используется в качестве таблицы символов.
Буферизация таблиц хеширования. Клеточная организация
1. Большие таблицы хеширования обычно хранятся на ВЗУ, и лишь тот фрагмент таблицы, в котором находится ЭД с вычисленным адресом, помещается в БП. Если для обработки коллизий используются процедуры линейного пробинга, то значительную часть резервных ячеек (а иногда и все) также попадет в БП. Специальные системные программы позволяют осуществлять эффективный обмен между ОП и ВЗУ, причем этот обмен производится страницами. Для МД типовой размер страницы – 256 слов, что соответствует одному адресуемому сектору дорожки.
Можно повысить вероятность попадания всех резервных ячеек на одну и ту же страницу, если адрес смещения вычислять циклически, по модулю, равному размеру страницы.
2. Распространен еще один метод построения хеш-таблиц, названный – с клеточной организацией.
Этот метод основан на объединении нескольких последовательно расположенных ячеек памяти, которым присваивается общий для всех ячеек хеш-адрес. Полученная группа называется клеткой, делится на фиксированное количество “позиций”, в каждой из которых размещается по одному конфликтующему элементу, до тех пор, пока все позиции такой клетки не будут заняты, резервные ячейки отыскиваются в ней. Если клетка заполнена целиком, то берется вторая клетка, и “цепочка” резервных ячеек продолжает формироваться в ней. Т.о. на каждую клетку приходится один указатель.
В случае линейного пробинга резервные ячейки, не помещающиеся по своему адресу, могут располагаться в ближайшей клетке, имеющей свободные позиции. Очевидно, что для каждого типа прикладных задач можно найти оптимальное количество позиций в клетке. Этот оптимум определяется наличием двух факторов:
- увеличение количества позиций позволяет сократить общий объем памяти, выделяемой для размещения указателей;
- уменьшается количество хеш-адресов, и поэтому записи распределяются по таблице менее равномерно (что приводит к увеличению количества коллизий).
По данным теоретических оценок, количество позиций должно быть невелико (раздел 2.5).
Для НМД более удобны клетки большого размера. Если клетка занимает целую дорожку, то ее содержимое можно передать в ОП за одну операцию считывания.
Выдвигались и применялись методы, построенные на использовании цепочек, составленных из клеток, размеры которых последовательно увеличивались в геометрической прогрессии. Эти методы были направлены на повышение эффективности использования дискового пространства, но эти методы не всегда эффективны и не всегда принимались.
Отметим, что необходимость буферизации данных была осознана давно, на ранних стадиях развития ВТ. Клеточная организация тоже была предложена достаточно давно.
Размещение в клетках записей переменной длины
Т.к. клеточная организация применяется в основном в случаях, когда используется ВЗУ (внешняя память), в клетках могут помещаться и записи достаточно большого размера. Продолжительность поиска определяется в первую очередь затратами времени на пересылку клетки в ОП. Что касается проверки содержимого “позиций”, то она выполняется при помощи коротких операций, выполняемых в ЦП, и занимает малое время. Записи переменной длины внутри клетки могут располагаться непосредственно друг за другом, без разбиения на “позиции”. Их необходимо лишь как-то отделять друг от друга – например, при помощи специальных кодов.