Главная Промышленная автоматика.

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

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

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

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

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

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

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



так как при вставке элемент х вставляется в первый пустой сегмент, следовательно, он находится где-то до сегмента кз(х).

Но если в словаре допускается удаление элементов, то при достижении пустого сегмента мы, не найдя элемента х, не можем быть уверенными втом, что его вообще нет в словаре, так как сегмент может стать пустым уже после вставки элемента х. Поэтому, чтобы увеличить эффективность данной реализации, необходимо в сегмент, который освободился после операции удаления элемента, поместить специальную константу, которую назовем 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 и реализацией, использующей закрытую хеш-таблицу. Здесь используется хеш-функция Л из листинга 4.7, для разрешения коллизий применяется методика линейного хеширования. Константа empty определена как строка из десяти пробелов, а константа deleted - как строка из десяти символов в предположении, что эти строки не совпадают ни с одним элементом словаря. (В базе данных примера 4.2 эти строки, очевидно, не будут совпадать с именами законодателей.) Процедура INSERT(jc, Л) использует функцию locate (местонахождение) для определения, присутствует ли элемент х в словаре А или нет, а также специальную функцию locatel для определения местонахождения элемента х. Последнюю функцию также можно использовать для поиска констант deleted и empty.

Листинг 4.9. Реализация словаря посредством закрытого хеширования const

empty = ; { 10 пробелов }

deleted = •******♦***- { ю символов * }

type

DICTIONARY = array[О..В-l] of nametype;

procerude MAKENULL { var A: DICTIONARY );

i: integer; begin

for i:= 0 to S - 1 do

A[i]:= empty end,- { MAKENULL }

fimctian locate ( x: nametype; A: DICTIONARY ) : integer;

{ Функция просматривает A начиная от сегмента h(x) до тех пор, пока не будет найден элемент х или не встретится



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

initial, i: integer; begin

initial:= h(x); i:= 0;

while (i < B) and {Al {initial + i) mod B] <> x) and (A[ (initial +i) mod B] о empty) do i;= i + 1/ return((initiai + i) mod B)

end; { locate }

function iocatel ( x: nametype; A: DICTICNARY ): integer;

{ To же самое, что и функция locate, но останавливается и при достижении значения deleted }

function MEMBER { х: nametype; var A: DICTIONi\RY ) : boolean; begin

if A[2ocate(x)] = x then return(true)

else

return(false)

end; { MEMBER }

procedure INSERT ( x: nametype; var A: DICTIONmY ); var

backet: integer; begin

if A[locate{K)\ = x then return; { хуже есть в A } buc;:et:= Iocatel (x);

if (Albucket] = empty) or {A[bucket] = deleted) then A[bucket] := x

else

error(Операция INSERT невозможна: таблица полна} end; { INSERT }

procedure DELETE ( x: nametype; var A: DICTIONARY ); var

bucket: integer; begin

bucket:= locate(x) ;

if A[Iocate(x)] = x then Albucket]:= deleted end; { DELETE }

4.8.0ценкаэффективностихеш-функций

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 [36] 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.004