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

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

С использованием отдельной области переполнения легче устраняются проблемы загруженности таблиц хеширования. На практике считается, что коэффициент заполнения таблиц хеширования не должен быть больше 0,8–0,9. Поэтому необходимо иметь автоматическую процедуру, которая помогала бы вовремя приостанавливать рост коэффициента заполнения.

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

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

2.2.4. Методы ускорения процедур поиска

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

41

Флажок коллизии

Чтобы быстро определить, имеется ли в таблице требуемый исковый элемент, можно зарезервировать в каждой ячейке таблицы специальный разряд, называемый флажком коллизии. Поисковый аргумент или заменяющий его идентификатор может не совпадать с записанным по вычисленному адресу ключевым словом (или соответствующим идентификатором) по двум причинам:

1) либо элемент с данным ключевым словом содержится в таблице, но вследствие коллизии он записан в резервную ячейку;

2) либо его просто нет в таблице.

Пусть во флажковом разряде первоначально записан “0”. После первой коллизии в данной ячейке флажок переводится в “1”. Тогда, если по вычисленному адресу ключевое слово не совпадает с аргументом поиска, а флажок установлен в “0”, то это означает, что ни в одной из резервных ячеек искомого ключа нет, и поиск надо прекратить.

В комбинации с флажком “занято” реализуется возможность определения продолжения поиска, если флажок коллизии в каждой ячейке таблицы, за которой следует резервная ячейка, устанавливается в “1”. После удаления элемента флажок “занято” устанавливается в “0”, и это означает, что ячейка свободна. Если флажок коллизии в данной ячейке установлен в “1”, то это означает, что цепочка резервных ячеек не закончилась и поиск надо продолжать.

Упорядоченные таблицы хеширования

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

Виртуальные хеш-адреса

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

42