При рассмотрении процедур поиска обычно предполагается, что запись для которой организуется поиск хранится в некоторой таблице, и нахождение нужной записи сводится к просмотру некоторого количества значений ключевых полей. Организация файла и порядок, в котором вставляются ключи, определяют то число проверок, которые должны быть выполнены для получения нужной записи. Очевидно, что эффективными методами поиска, являются те, которые минимизируют число таких сравнений. В идеале требуется такая организация таблицы, при которой не было бы ненужных сравнений.
Если каждая запись может быть найдена за один доступ, то ее положение в таблице должно зависеть только от значения данного ключа. Оно не может зависеть от расположения других записей, как это, например, имеет место в бинарном дереве. Наиболее эффективным способом организации такой таблицы является массив, где каждая запись хранится по некоторому конкретному смещению по отношению к базовому адресу таблицы. Если ключи записи являются целыми числами, то сами значения ключей могут использоваться как индексы в массиве. Хотя многие позиции массива могут соответствовать не существующим элементам, эти потери компенсируются преимуществом прямого доступа к каждому из существующих элементов.
К сожалению, такая система не всегда имеет практический смысл. Например, в файле со списком студентов записи могут идентифицироваться шестизначным номером зачетной книжки, что в рассмотренном выше случае предполагает использование массива, содержащего миллион записей. В то же время число студентов в вузе не превышает двадцати тысяч.
Естественно использовать некоторый метод преобразования ключа в какое-либо целое число внутри ограниченного диапазона. В идеале один и тот же индекс массива записей не должен соответствовать при таком преобразовании двум разным ключам. К сожалению, такого идеального метода обычно не существует. Ниже рассматриваются методы которые дают приемлемые решения для реализации этой идеи.
Пусть известно, что в рассмотренном примере число студентов не превышает 1000, и что для каждого студента в списке существует не более одной записи. Тогда для хранения всех записей списка будет достаточно массива из 1000 элементов. Для нахождения нужного индекса можно использовать три последние цифры номера зачетной книжки:
481137 -> 137;
481934 -> 934.
Функция, которая трансформирует значение ключа записи в некоторый значение индекса элемента массива для хранения записей называется хеш -функцией h(key). В приведенном выше примере
h(key) = key mod 1000.
К сожалению, в общем случае нет гарантии, что значения хеш-функции для двух разных значений ключа всегда будут различаться. В то же время очевидно что две записи в массиве не могут занимать одну и ту же позицию. Такая ситуация. Возникающая при хешировании, называется столкновением или коллизией. Один из критериев для оценки хеш-функции – минимизация коллизий, что соответствует размещению записей списка при хешировании по максимальному количеству позиций в массиве.
Желательно иметь массив для хранения записей с числом позиций большим, чем число реальных записей. Часто, чем больше диапазон области значений хеш-функции, тем менее вероятно, что два ключа дадут одинаковое значение хеш-функции. При этом выдерживается некоторый компромисс между временем и пространством:
- чем больше массив, тем менее эффективно используется память ЭВМ;
- увеличение массива уменьшает возможность коллизий, а следовательно уменьшает время на размещение и поиск нужной записи.
Для разрешения коллизий могут использоваться два качественно различных метода: метод повторного хеширования (метод открытой адресации) и метод цепочек.
Примером повторного хеширования является метод линейного опробования, при котором при возникновении коллизии запись помещается в следующую свободную позицию. То есть функция rh (i) повторного хеширования имеет вид
rh(i) = (i+1) mod 1000, где i позиция в массиве, на которую претендовала запись до повторного хешированияю В частности, на первом шаге
rh(h(key)) = h(key) + 1 .
В общем случае для повторного хеширования rh воспринимает одно значения индекса в массиве и выдает следующее значение индекса. Если ячейка rh(h(key)) уже занята, то преобразование полученного индекса выполняется еще раз и проверяется позиция массива с номером rh(rh(h(key))). Процесс продолжается до тех пор, пока не будет найдена пустая ячейка. Данный цикл может оказаться бесконечным по двум возможным причинам:
- массив может быть заполненным, так что вставить какое-либо новое значение невозможно;
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
