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

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

Ситуация, когда при попытке поместить элемент x в сегмент с номером h(x) оказывается, что сегмент занят другим элементом y (x≠y, но h(x)=h(y)) называется коллизией.

Для разрешения коллизий при закрытом хешировании применяется методика повторного хеширования. Выбирается последовательность других номеров сегментов , , ..., куда можно поместить элемент . Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное, куда и помещаетя x. Если свободных сегментов нет, то, следовательно, таблица заполнена и элемент вставить нельзя.

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

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

Различные методики разрешения коллизий различаются принципом построения последовательности функций Рассмотрим далее два принципа повторного хеширования.

2.1. Линейное повторное хеширование. Нахождение повторных хеш-значений происходит по формуле

(1)

В частности,

***

Пример 2. Предположим, что и ключи , , и имеют хеш-значения , , и .

Мы предполагаем, что вначале вся хеш-таблица пуста, т.е. в каждом сегменте словаря, свойство Null = true, которое говорит о том, что в сегмент запись не производилась. Теперь последовательно вставим элементы , , и в пустую таблицу: элемент попадет в сегмент 3, элемент — в сегмент 0, а элемент — в сегмент 4. Для элемента , но сегмент 3 уже занят. Применяем функцию : , но сегмент 4 также занят. Далее применяем функцию : , сегмент 5 свободен, помещаем туда элемент . Результат заполнения хештаблицы показан на рис. 14.2.

Рис. 14.2. Частично заполненная хеш-таблица

Пример 3. Предположим, что надо определить, есть ли элемент в множестве, представленном на рис.14.2. Если , то надо проверить сегмент 4. Поскольку там элемента e нет, проверяем сегмент с номером 5 и затем сегмент с номером 6. Сегмент 6 пустой, в предыдущих просмотренных сегментах элемент не найден, следовательно, этого элемента в данном множестве нет.

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