2.4 Структура и форматы таблиц хеширования
2.4.1 Непосредственная и косвенная адресация
а) Индексные таблицы хеширования (ТХ)
Для размещения данных, хранящихся в ТХ совместно с ключевыми словами или их идентификаторами, часто требуются большие объемы памяти. Размеры ЭД могут изменяться, однако, как правило, таблицы хеширования строятся исходя из максимальной длины. В результате – часть памяти используется непроизводительно. Кроме того, с увеличением длины записей возрастает трудоемкость (время) поиска. Допуская некоторые увеличения количества обращений к памяти (что неизбежно при использовании многоуровневой памяти) можно повысить эффективность поиска. Для этого ЭД необходимо размещать в специально отведенной области, а в основной таблице хеширования хранить только указатели, содержащие адреса элементов в этой области, а также соответствующие идентификаторы. При такой структуре в процессе поиска проверке подвергаются только ключевые слова (или их идентификаторы) и обращение к отдельной области памяти производится только после того, как будет найден требуемый элемент. Преимущество предлагаемой схемы также состоит в том, что при необходимости основную таблицу хеширования (которую в дальнейшем будем называть индексной таблицей хеширования) можно без особых затруднений поместить в другую область.
Индексные таблицы хеширования достаточно распространены, особенно в СУБД. Однако с их помощью не всегда удается достичь желаемого результата. Например, при использовании только коротких имен (ключевых слов), внутренней адресации (т.е. цепочек внутри ТХ, и т.д.).
б) Комбинированная адресация в хеш-таблице (ступенчатое хеширование)
Рассмотренный выше принцип построения ТХ можно рассматривать как простейшую форму косвенной адресации. Такая адресация является обязательным элементом индексной хеш-таблицы. Ее можно сделать более эффективно, если наряду с косвенной адресацией использовать и прямую (непосредственную) адресацию. Для задания режима адресации в каждой ячейке таблицы отводится специальный разряд, именуемый флажком связи.