ГоловнаЗворотній зв'язок

Алгоритмы структуры данных

Закрытое хеширование

При закрытом хешировании в таблице сегментов хранятся непосредственно элементы словаря, а не заголовки списков. Поэтому в каждом сегменте может храниться только один элемент словаря. При закрытом хешировании применяется методика повторного хеширования. Если мы попытаемся поместить элемент x в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h1(x), h2(x), ..., куда можно поместить элемент х. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. Если свободных сегментов нет, то, следовательно, таблица заполнена и элемент х вставить нельзя.

Пример 4.3. Предположим, что B = 8 и ключи а, b, с и d имеют хеш-значения h(а) = 3, h(b) = 0, h(с) = 4 и h(d) = 3. Применим простую методику, которая называется линейным хешированием. При линейном хешировании hi(x) = (h(x) + і) mod В. Например, если мы хотим вставить элемент d, а сегмент 3 уже занят, то можно проверить на занятость сегменты 4, 5, 6, 7, 0, 1 и 2 (именно в таком порядке).

Мы предполагаем, что вначале вся хеш-таблица пуста, т.е. в каждый сегмент помещено специальное значение empty (пустой), которое не совпадает ни с одним элементом словаря(если тип данных элементов словаря не соответствует типу значения empty, то в каждый сегмент можно поместить дополнительное однобитовое поле с маркером, показывающим, занят или нет данный сегмент). Теперь последовательно вставим элементы а, b, с и d в пустую таблицу: элемент а попадет в сегмент 3, элемент b — в сегмент 0, а элемент с — в сегмент 4. Для элемента d h(d) = 3, но сегмент 3 уже занят. Применяем функцию h1: h1(d) = 4, но сегмент 4 также занят. Далее применяем функцию h2- h2(d) = 5, сегмент 5 свободен, помещаем туда элемент d. Результат заполнения хеш-таблицы показан на рис. 4.4.

При поиске элемента х (например, при выполнении оператора MEMBER) необходимо просмотреть все местоположения h(x), h1(x), h2(x), ..., пока не будет найден х или пока не встретится пустой сегмент. Чтобы объяснить, почему можно остановить поиск при достижении пустого сегмента, предположим, что в словаре не допускается удаление элементов. И пусть, для определенности, h3(x) — первый пустой сегмент. В такой ситуации невозможно нахождение элемента х в сегментах h4(x), h5(x) и далее, так как при вставке элемент х вставляется в первый пустой сегмент, следовательно, он находится где-то до сегмента h3(x).

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

Пример 4.4. Предположим, что надо определить, есть ли элемент е в множестве, представленном на рис. 4.4. Если h(e) = 4, то надо проверить еще сегменты 4, 5 и затем сегмент 6. Сегмент 6 пустой, в предыдущих просмотренных сегментах элемент е не найден, следовательно, этого элемента в данном множестве нет.

Допустим, мы удалили элемент с и поместили константу deleted в сегмент 4. В этой ситуации для поиска элемента d мы начнем с просмотра сегмент h(d) = 3, затем просмотрим сегменты 4 и 5 (где и найдем элемент d), при этом мы не останавливаемся на сегменте 4 — хотя он и пустой, но не помечен как empty.

В листинге 4.9 представлены объявления типов данных и процедуры операторов для АТД DICTIONARY с элементами типа nametype и реализацией, использующей закрытую хеш-таблицу. Здесь используется хеш-функция h из листинга 4.7, для разрешения коллизий применяется методика линейного хеширования. Константа empty определена как строка из десяти пробелов, а константа deleted — как строка из десяти символов "*", в предположении, что эти строки не совпадают ни с одним элементом словаря. (В базе данных примера 4.2 эти строки, очевидно, не будут совпадать с именами законодателей.) Процедура INSERT(x, А) использует функцию locate (местонахождение) для определения, присутствует ли элемент х в словаре А или нет, а также специальную функцию locate! для определения местонахождения элемента х. Последнюю функцию также можно использовать для поиска констант deleted и empty.

 

53