Структуры данных и алгоритмы (1021739), страница 29
Текст из файла (страница 29)
При реализации словарей посредством двоичныхвекторов все эти три оператора выполняются за фиксированное время независимо отразмера множеств, но в этом случае мы ограничены множествами целых чисел изнекоторого небольшого конечного интервала.Существует еще один полезный и широко используемый метод реализации словарей, который называется хешированием. Этот метод требует фиксированного времени(в среднем) на выполнение операторов и снимает ограничение, что множества должны быть подмножествами некоторого конечного универсального множества.
В самомхудшем случае этот метод для выполнения операторов требует времени, пропорцио116ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВнального размеру множества, так же, как и в случаях реализаций посредством массивов и списков. Но при тщательной разработке алгоритмов мы можем сделать так,что вероятность выполнения операторов за время, большее фиксированного, будеткак угодно малой.Мы рассмотрим две различные формы хеширования. Одна из них называется открытым, или внешним, хешированием и позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер мно1жеств.
Другая называется закрытым, или внутренним, хешированием и используетограниченное пространство для хранения данных, ограничивая таким образом раз2мер множеств .Открытое хешированиеНа рис. 4.3 показана базовая структура данных при открытом хешировании. Основная идея заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов.
Для В классов, пронумерованных от Одо В - 1, строится хеш-функция h такая, что для любого элемента ж исходного множества функция h(x) принимает целочисленное значение из интервала 0, ..., В — 1,которое, естественно, соответствует классу, которому принадлежит элемент х. Элемент х часто называют ключом, h(x) — хеш-значением х, а "классы" — сегментами.Мы будем говорить, что элемент х принадлежит сегменту h(x).Список элементовкаждого сегментаВ-1Заголовки таблицысегментовРис. 4.3. Организация данных при открытом хешированииМассив, называемый таблицей сегментов и проиндексированный номерами сегментов О, 1,...,В - 1, содержит заголовки для В списков.
Элемент х i-ro списка —это элемент исходного множества, для которого h(x) = I.Если сегменты примерно одинаковы по размеру, то в этом случае списки всехсегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из N элементов, тогда средняя длина списков будет N/Bэлементов. Если можно оценить величину N и выбрать В как можно ближе к этойвеличине, то в каждом списке будет один-два элемента.
Тогда время выполненияоператоров словарей будет малой постоянной величиной, зависящей от N (или, чтоэквивалентно, от В).1Есть несколько классификаций методов хеширования по разным признакам. Мы оставляем здесь классификацию (и терминологию) авторов, поскольку она проста и непротиворечива.Отметим только, что открытое хеширование, как оно изложено далее, является частным случаем так называемого расширенного хеширования, а закрытое хеширование часто называютпрямымхешированием. — Прим.
ред.2Путем внесения изменений в структуру данных можно изменять объем пространства, занимаемого данными при открытом хеширование, и увеличить его при закрытом хешировании.Мы опишем эти технологии после знакомства с основными методами хеширования.4.7. СТРУКТУРЫ ДАННЫХ, ОСНОВАННЫЕ НА ХЕШ-ТАБЛИЦАХ117Не всегда ясно, как выбрать хеш-функцию А так, чтобы она примерно поровнураспределяла элементы исходного множества по всем сегментам. Ниже мы покажемпростой способ построения функции А, причем h(x) будет "случайным" значением,почти независящим от х.Здесь же мы введем хеш-функцию (которая будет "хорошей", но не "отличной"),определенную на символьных строках.
Идея построения этой функции заключается втом, чтобы представить символы в виде целых чисел, используя для этого машинныекоды символов. В языке Pascal есть встроенная функция ord(c), которая возвращаетцелочисленный код символа с. Таким образом, если х — это ключ, тип данных ключейопределен как аггау[1..10] of char (в примере 4.2 этот тип данных назван nametype),тогда можно использовать хеш-функцию, код которой представлен в листинге 4.7. Вэтой функции суммируются все целочисленные коды символов, результат суммирования делится на В и берется остаток от деления, который будет целым числом из интервала от 0 до В - 1.Листинг 4.7. Простая хеш-функцияfunction h ( х: nametype ): О..В-1;vari, sum: integer;beginsum:= 0;for i:= 1 to 10 dosum:= sum + ord(x[i]);h:= sum mod Вend; { h }В листинге 4.8 показаны объявления структур данных для открытой хештаблицы и процедуры, реализующие операторы, выполняемые над словарем. Типданных элементов словаря — nametype (здесь — символьный массив), поэтому данные объявления можно непосредственно использовать в примере 4.2.
Отметим, что влистинге 4.8 заголовки списков сегментов сделаны указателями на ячейки, а не"настоящими" ячейками. Это сделано для экономии пространства, занимаемого данными: если заголовки таблицы сегментов будут ячейками массива, а не указателями,то под этот массив необходимо столько же места, сколько и под списки элементов.Но за такую экономию пространства надо платить: код процедуры DELETE долженуметь отличать первую ячейку от остальных.:.':.•••:';•'•'.
' '-:.:.:: '..'.•<•' ''"v >. .' °:'*<""V.':. . . ' . ' '' ' ' ' • " '.<*•>*•: ' : ; . . . , • . • i y.'v" • :• ' . . ' • : ,;< • < . ; . <••;•;.• ; . . ; Ь^Ц'%';Листинг 4.8. Реализация словарей посредством открытой хеш-таблицыconstВ = { подходящая константа };typecelltype = recordelement: nametype;next: tcelltypeend;DICTIONARY = array[0..5-1] of Tcelltype;procedure MAKENULL ( var A: DICTIONARY );vari:= integer;beginfor i:= 0 to В - 1 doA [ i ] : = nilend; { MAKENULL }118ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВfunction MEMBER ( x: nametype; var A: DICTIONARY ): boolean;varcurrent: tcelltype;begincurrent:= A[h(x)];{ начальное значение current равно заголовку сегмента,которому принадлежит элемент х }while current о nil doif current?.element = x thenreturn(true)elsecurren t:= currentt.
next ;return(false) { элемент х не найден }end; { MEMBER }procedure INSERT ( x: nametype; var A: DICTIONARY );varbucket: integer; { для номера сегмента }oldheader: tcelltype;beginif not MEMBER(x, A) then beginbucket:= h(x) ;oldheader: = A[bucket];new(A[bucket]) ;A[buaket]t.element:= x;Albucket]t.next:= oldheaderendend; { INSERT }procedure DELETE ( x: nametype; var A: DICTIONARY );varbucket: integer;curren t: Tee11type;beginbucket:= h(x);if A[buc£et] <> nil then beginif A [bucket]'?, element = x then { x в первой ячейке }A[bucket]:= Albucket]!'.next { удаление х из списка }else begin { x находится не в первой ячейке }current:= A[bucket];{ current указывает на предыдущую ячейку }while currentt.next <> nil doif currentt.nextt.element = x then begincurren tt.next:= curren tt.nextt. next;{ удаление х из списка }return { останов }endelse { x пока не найден }current:= currentt.nextendendend; { DELETE }4.7.
СТРУКТУРЫ ДАННЫХ, ОСНОВАННЫЕ НА ХЕШ-ТАБЛИЦАХ119Закрытое хешированиеПри закрытом хешировании в таблице сегментов хранятся непосредственно элементы словаря, а не заголовки списков. Поэтому в каждом сегменте может храниться только один элемент словаря. При закрытом хешировании применяется методикаповторного хеширования. Если мы попытаемся поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов hi(x), h%(x), ..., куда можно поместить элемент х.
Каждое из этих местоположений последовательно проверяется, пока не будетнайдено свободное. Если свободных сегментов нет, то, следовательно, таблица заполнена и элемент х вставить нельзя.Пример 4.3. Предположим, что В = 8 и ключи а, Ъ, с и d имеют хеш-значенияЛ(а) = 3, h(b) = 0, h(c) = 4 и h(d) = 3. Применим простую методику, котораяназываетсялинейнымхешированием.Прилинейномхешированииh-i(x) — (h(x) + i) mod В. Например, если мы хотим вставить элемент d, a сегмент 3уже занят, то можно проверить на занятость сегменты 4, 5, 6, 7, О, 1 и 2 (именно втаком порядке).Мы предполагаем, что вначале вся хеш-таблица пуста, т.е. в каждый сегмент помещено специальное значение empty (пустой), которое не совпадает ни с одним элементом словаря1.
Теперь последовательно вставим элементы а, Ь, с и d в пустую таблицу: элемент а попадет в сегмент 3, элемент Ь — в сегмент О, а элемент с — в сегмент 4. Для элемента d h(d) — 3, но сегмент 3 уже занят. Применяем функцию h-c.hi(d) = 4, но сегмент 4 также занят. Далее применяем функцию Л 2 : h2(d) = 5,сегмент 5 свободен, помещаем туда элемент d. Результат заполнения хештаблицы показан на рис. 4.4. ПРис. 4.4. Частично заполненная хеш-таблицаПри поиске элемента х (например, при выполнении оператора MEMBER) необходимо просмотреть все местоположения h(x), hi(x), h2(x), ..., пока не будет найден хили пока не встретится пустой сегмент. Чтобы объяснить, почему можно остановитьпоиск при достижении пустого сегмента, предположим, что в словаре не допускаетсяудаление элементов. И пусть, для определенности, h3(x) — первый пустой сегмент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
