Структуры данных и алгоритмы (1021739), страница 30
Текст из файла (страница 30)
Втакой ситуации невозможно нахождение элемента х в сегментах h4(x), h&(x) и далее,Если тип данных элементов словаря не соответствует типу значения empty, то в каждыйсегмент можно поместить дополнительное однобитовое поле с маркером, показывающим, занятили нет данный сегмент.120ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВтак как при вставке элемент х вставляется в первый пустой сегмент, следовательно,он находится где-то до сегмента 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. DВ листинге 4.9 представлены объявления типов данных и процедуры операторовдля АТД DICTIONARY с элементами типа nametype и реализацией, использующейзакрытую хеш-таблицу.
Здесь используется хеш-функция Л из листинга 4.7, дляразрешения коллизий применяется методика линейного хеширования. Константаempty определена как строка из десяти пробелов, а константа deleted — как строкаиз десяти символов "*", в предположении, что эти строки не совпадают ни с однимэлементом словаря. (В базе данных примера 4.2 эти строки, очевидно, не будут совпадать с именами законодателей.) Процедура INSERT(x, Л) использует функциюlocate (местонахождение) для определения, присутствует ли элемент х в словаре Аили нет, а также специальную функцию locate! для определения местонахожденияэлемента х. Последнюю функцию также можно использовать для поиска константdeleted и empty.Листинг 4.9. Реализация словаря посредством закрытого хешированияconstempty = ''; { 10 пробелов }deleted = •**********•; { Ю символов * }typeDICTIONARY = array[0..B-l] of nametype;procerude MAKENULL ( var A: DICTIONARY );vari: integer;beginfor i:= 0 to В - I doA[i]:= emptyend,- { MAKENULL }function locate ( x: nametype; A: DICTIONARY ): integer;{ Функция просматривает А начиная от сегмента h(x) до техпор, пока не будет найден элемент х или не встретится4.7.
СТРУКТУРЫ ДАННЫХ, ОСНОВАННЫЕ НА ХЕШ-ТАБЛИЦАХ121пустой сегмент или пока не будет достигнут конец таблицы(в последних случаях принимается, что таблица не содержитэлемент х). Функция возвращает позицию, в которойостановился поиск. }varinitial, i: integer;begininitial:= h(x);i:= 0;while (i < B) and (A[(initial + i) rood B] <> x) and(A[(initial + i) mod В] о empty) doi:= i + 1;return((initial + i) mod B)end; { locate }function locate! ( x: nametype; A: DICTIONARY ): integer;{ To же самое, что и функция locate, но останавливается и придостижении значения deleted }function MEMBER ( x: nametype; var A: DICTIONARY ): boolean;beginif A[locate(x)] = x thenreturn(true)elsereturn(false)end; { MEMBER }procedure INSERT ( x: nametype; var A: DICTIONARY );varbacket: integer;beginif A[locate(x)] = x then return; { x уже есть в А }bucket:= locatel(x);if (A[bucket] = empty) or (A[bucket] = deleted) thenA[bucket]:= xelseerror('Операция INSERT невозможна: таблица полна1}end; { INSERT }procedure DELETE ( x: nametype; var A: DICTIONARY );varbucket: integer;beginbucket:= locate(x);if A[locate(x)] = x thenAibucket]:= deletedend; { DELETE }4.8.
Оценка эффективности хеш-функцийНапомним, что хеширование — эффективный способ представления словарей инекоторых других абстрактных типов данных, основанных на множествах. В этомразделе мы оценим среднее время выполнения операторов словарей для случая открытого хеширования. Если есть В сегментов и N элементов, хранящихся в хеш122ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВтаблице, то каждый сегмент в среднем будет иметь N/B элементов и мы ожидаем,что операторы INSERT, DELETE и MEMBER будут выполняться в среднем за время О(1 + N/B). Здесь константа 1 соответствует поиску сегмента, а N/В — поискуэлемента в сегменте. Если В примерно равно N, то время выполнения операторовстановится константой, независящей от N.Предположим, что есть программа, написанная на языке программирования, подобном Pascal, и мы хотим все имеющиеся в этой программе идентификаторы занести в хеш-таблицу.
После обнаружения объявления нового идентификатора он вставляется в хеш-таблицу, конечно же, после проверки, что его еще нет в хеш-таблице.На этапе проверки естественно предположить, что идентификатор с равной вероятностью может быть в любом сегменте. Таким образом, на процесс заполнения хештаблицы с N элементами потребуется время порядка O(N(1 + N/B)). Если положить,что В равно N, то получим время O(N).На следующем этапе анализа программы просматриваются идентификаторы втеле программы. После нахождения идентификатора в теле программы, чтобы получить информацию о нем, его же необходимо найти в хеш-таблице. Какое времяпотребуется для нахождения идентификатора в хеш-таблице? Если время поискадля всех элементов примерно одинаково, то оно соответствует среднему временивставки элемента в хеш-таблицу. Чтобы увидеть это, достаточно заметить, чтовремя поиска любого элемента равно времени вставки элемента в конец списка соответствующего сегмента.
Таким образом, время поиска элемента в хеш-таблицесоставляет О(1 + N/B).В приведенном выше анализе предполагалось, что хеш-функция распределяетэлементы по сегментам равномерно. Но существуют ли такие функции? Рассмотримфункцию, код которой приведен в листинге 4.7, как типичную хеш-функцию.(Напомним, что эта функция преобразует символы в целочисленный код, суммируеткоды всех символов и в качестве результата берет остаток от деления этой суммы начисло В.) Следующий пример оценивает работу этой функции.Пример 4.5. Предположим, что функция из листинга 4.7 применяется для занесения в таблицу со 100 сегментами 100 символьных строк АО, А1, ..., А99.
Принимая во внимание, что ord(O), ord(l)ord(9) образуют арифметическую прогрессию(это справедливо для всех таблиц кодировок, где цифры 0, ..., 9 стоят подряд, например для кодировки ASCII), легко проверить, что эти элементы займут не более 29сегментов из ста , наибольший сегмент (сегмент с номером 2) будет содержать элементы А18, А27, А36, ..., А90, т.е. девять элементов из ста2. Используя тот факт,что для вставки i-ro элемента требуется i + 1 шагов, легко подсчитать, что в данномслучае среднее число шагов, необходимое для вставки всех 100 элементов, равно 395.Для сравнения заметим, что оценка N(1 + N/B) предполагает только 200 шагов.
ПВ приведенном примере хеш-функция распределяет элементы исходного множества по множеству сегментов не равномерно. Но возможны "более равномерные" хешфункции. Для построения такой функции можно воспользоваться хорошо известнымметодом возведения числа в квадрат и извлечения из полученного квадрата нескольких средних цифр. Например, если есть число п, состоящее из 5 цифр, то после возведения его в квадрат получим число, состоящее из 9 или 10 цифр. "Средние цифры" — это цифры, стоящие, допустим, на позициях от 4 до 7 (отсчитывая справа).Их значения, естественно, зависят от числа п. Если В = 100, то для формированияномера сегмента достаточно взять две средние цифры, стоящие, например, на позициях 5 и 6 в квадрате числа.1Отметим, что строки А2 и А20 не обязательно должны находиться в одном сегменте, ноА232 и А41, например, будут располагаться в одном сегменте.Обратите внимание, что здесь "А" — буква английского алфавита и что приведенное распределение элементов по сегментам справедливо только для записанных выше символьныхстрок.
Для другой буквы (или других символьных строк) получим другое распределение элементов по сегментам, но также, скорее всего, далекое от равномерного. — Прим. ред.4.8. ОЦЕНКА ЭФФЕКТИВНОСТИ ХЕШ-ФУНКЦИЙ123Этот метод можно обобщить на случай, когда В не является степенью числа 10.Предположим, что элементы исходного множества являются целыми числами изинтервала О, 1, ..., К. Введем такое целое число С, что ВС2 примерно равно К2,тогда функцияЛ(п) = [n2/C] mod В,где [я] обозначает целую часть числа х, эффективно извлекает из середины числа л2цифры, составляющие число, не превышающее В.Пример 4.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
