    14. Три способа реализации множества на базе вектора. Последовательный 
поиск, бинарный поиск, хеширование 

    Непрерывная реализация. Последовательный поиск. Основная идея шмфгрышюП 
реализации, как мы знаем, состоит о том, чтобы хранить Клементи имитируемой 
структуры в векторе единым слитным куском, а для задания порядка элементов 
структуры исполь-аовать порядок их расположения в векторе. Для множества 
порядок элементов не существен, и остается лишь расположить элементы множества 
в векторе непрерывным куском, например «прижив» их к началу вектора 
(аналогично' расположению элементов стеки п рпмд. 12). Правую границу этого 
непрерывного куска (т. е, число элементов множества) легко задать с помощью объекта 

    мощность: 0. .максинд 

    Определение принадлежности элемента множеству сводится к просмотру 
начального куска вектора — просмотру элементов с индексами от 1 до мощность, 
При имитации удаления элемента из миожсппц нужно прежде иссго выяснить, есть 
ли удаляемый эле-Мсмт и ммижгппг, и если есть, то и K;IKOM элементе вектора он 
рппюложсн. Другими словами, перед удалением принадлежащего множеству элемента 
нужно сначала определить индекс соответ-ггнующсто элемента вектора. Мы будем 
это делать с помощью программы 

    искать (вх: е, вых: нашли: да/нет, вых: и : индекс) 

    Кроме того, надо позаботиться, чтобы при удалении элемента «я середины 
оставшиеся элементы множества по-прежнему лежали слитным куском. Естественным 
кажется решение переместить все элементы множества, лежащие правее удаляемого, 
на один элемент k;it!uo по вектору. Эта операция, однако, является массовой (число 
наполняемых при этом элементарных действий с вектором заранее неизвестно 
— оно зависит от числа  перемещаемых элементов). Потому   поступим  
по-другому — возьмем   последний   (самый  правый  векторе) элемент множества 
*й переместим его в образовавшуюся 

    212 ГЛ. 3. СТРУКТУРЫ ДАННЫХ И ИХ  РЕАЛИЗАЦИИ 

    «дырку». Заметьте, что такое решение возможно только потому, что порядок 
элементов множества в векторе не важен, 

    исполнитель Ограниченное множество | на базе вектора 
    .	СП: 
    .	1. начать работу 
    .	?. сделать множество пустым 
    .	3. множество пусто                                                 i да/нет 
    .	4. есть свободное место                                            I да/нет 
    .	5. нет свободного места                                            : да/нет 
    .	6. элемент (вх : е : Е) принадлежит множеству      I да/нет 
    .	7. добавить элемент {вх: е : Е) в множество 
    .	8. удалить элемент (вх: е: Е) из множества 
    .	9. взять какой нибудь элемент множества в (вых: е: Е) 
    .	—  искать (вх : е: Е, вых: нашли : да/нет, вых: и: индекс) 
    .	10. кончить работу 
    * 
    . константы: 
    .   максинд = 100 
    . типы:	. .   индекс = 1. .максинд                                       >i • 
    • 
    . объекты: 
    .   мощность :0. .максинд [число элементов множества 
    . идеи реализации: 
    . Множество хранится "прижатым" к началу вектора, т. е. в эле-. ментах 
вектора с индексами 1. .мощность. При удалении эле-. мента в получившуюся 
дырку переставляется элемент, занимав-, ший место с индексом мощность 
используемые исполнители: вектор: вектор элементов типа Е с индексом типа индекс 
    конец описаний 

    программа начать работу =~ вектор.начать работу; мощность := О программа 
сделать множество пустым        ~~   мощность := О программа множество пусто	: 
да/нет -- (мощность = 0) программа есть свободное место   : да/нет -- 
(мощность<максинд) программа нет свободного места   ; да/нет -- (мощность=максинд) 
    программа элемент (вх! е: Е) принадлежит множеству: да/иен Дано 


    14  ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 213 


    . получить: 
    .   искать (вх:с, вых: ответ,и) конец программы 
    программа добавить элемент (вх:е:Е) в множество . дано        : есть 
свободное место . получить: 
    .   искать (вх : е, вых : нашли, и) 
    .   если не нашли то 
    .    .    мощность.увеличить на 1 
    .    .    вектор(мощность) := е 
    .    конец если 
    конец программы 
    программа удалить элемент (вх:е:Е) из множества . дано        : . получить: 
    .   искать (вх : е, вых : нашли, и) 
    .   если шпили то	* 
    ,    .    ш>ктор(и) :«= вектор(мощность)	' 
    .   .    мощность.уменьшить на 1 
    •   конец если	' конец программы 
    программа взять какой нибудь алемент множества в (вых:е:Е) . дано       : 
множество не пусто . получить: 
    •	/ 
    .    г :— пгмтп|>(мо|11пость) 
    .'i     .-«' ,.., (.,,'. .1 ... .    мощность.уменьшить на 1	ч ! 
    конец программы 
    программа искать (вх:е:Е, вых:нашли:да/нет, вых:и:индекс) . дано       : i получить: 
    выполнять 
    .   цикл V и е 1.. мощность пока вектор(и) 
    .    .     ничего не делать 
    .    конец цикла 
    .    нашли :=> (и ^& неопр) 
    конец программы 
    программа кончить работу -- вектор . кончить работу конец исполнителя | 

    214 ГЛ. 3. СТРУИТРЫ ДАННЫХ И ИХ РЕАЛИЗАЦИИ 

    Операция «искать» в этой реализации является массовой: чтобы узнать, что 
элемент е не принадлежит множеству, надо перебрать все элементы множества. 
Если е принадлежит множеству, *то число операций зависит от близости 
расположения е к началу вектора, )Таким образом, если в множестве п элементов, 
то при поиске принадлежащего множеству элемента максимальное число 
элементарных операций с вектором равно п, среднее — п/2. При поиске не 
принадлежащего множеству элемента число операций всегда равно п. В 
приложениях, где определение принадлежности элемента множеству является 
основной операцией, а сами множества достаточно велики, приведенная выше 
реализация может оказаться неудовлетворительной. Вся последующая часть этого 
раздела посвящена, задаче уменьшения числа операций при поиске элемента в множестве. 
    Непрерывная реализация. Бинарный поиск. Идею бинарного поиска (или поиска 
методом деления пополам) поясним на следующем примере: пусть задуманы 1000 
каких-то натуральных чисел—• чвсло номер 1, число номер 2, .,,, число номер 
1000. По условиям игры мы имеем право попросить назвать любое задуманное 
число, например 5-е, 28-е, 976-е и др. Наша задача 
    — задача поиска—-(узнать, есть ли среди задуманных некоторое конкретное 
число е, например 2718. 
    Если про порядок задуманных чисел ничего не известно и число е может 
оказаться на любом месте, то у нас нет иного способа, кроме как перебирать все 
задуманные числа (например, последовательно (узнавать 1-е, 2-е, 3-е, .... 999, 
1000-е задуманные числа) и смотреть, не попадется ли среди них е. Это и есть 
последовательный поиск, при котором в наихудшем случае понадобится задать 1000 
(мощность множества) вопросов, прежде чем мы узнаем, есть ли там е. 
    Если, однако, условия игры предполагают, что задуманные числа упорядочены 
по возрастанию, т. е. первое число меньше второго, второе меньше третьего и т. 
д., можно вести себя по-другому. Узнаем сначала 500-е задуманное число; пусть 
это х. Ясно, что если е < х, то дальше надо искать е среди чисел с 1-го по 
499-е, если е == х, то мы его нашли, а если  е > х, то надо искать среди чисел с 
501-го по 1000-е. Тем самым, задав всего один вопрос, мы либо найдем е, либо 
уменьшим количество подозреваемых чисел как минимум вдвое. Следующим 
вопросом количество подозреваемых можно уменьшить еще вдвое. Например, 
если после первого вопроса остались числа с 501-го по 1000-е, надо узнать 
750-е число и сравнить его с е, после чего останется не более 250 
подозревавмых чисел, и т, д. 

    И. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 215 

    Поскольку при каждом вопросе круг подозреваемых вдвое су< жается, то 
примерно за logj(n) (т. е. за 10) вопросов мы либо попадем на е, либо дойдем 
до ситуации, когда подозреваемых чисел не осталось. Последнее означает, что 
число е множеству задуманных чисел не принадлежит. Заметьте, что при п = 1000 
бинарный поиск в 100 раз быстрее последовательного, а при п = 1000000 в 50000 раз. 
    То, что в предыдущем рассуждении речь шла о натуральных числах, не очень 
важно. Если, например, задуманы 1000 слов и нужно узнать, есть ли среди них 
некоторое конкретное слово, то можно применить тот же самый метод деления 
пополам. Только сравнивать надо будет не числа, а слова (например, в 
алфавитном порядке), Единственное, что действительно требуется от типа Е,— это 
чтобы он был упорядоченным, т. е. чтобы над объектами типа Е были допустимы 
операции <, ^, ^, >. 
    Изменим теперь реализацию множества в соответствии с описанными выше 
идеями. Во-первых, надо обеспечить сохранение порядка элементов в множестве 
при добавлении и удалении; во-вторых, надо заменить в программе «искать» 
последовательный поиск па бинарный. 
    Ничш'м с реализации программы добавления элемента е в мможеспю. Мели е уже 
принадлежит множеству, то ничего делать по надо. Если же е множеству не 
принадлежит, то надо найти место для е между элементами множества, т. е. 
понять, куда вставлять е, и сдвинуть все элементы множества правее этого места 
(элементы большие е) вправо по вектору (рис. 14.1) 
    , 
    •лементы		< •	элементы	> в 
    f		V		Л 
    о	О	ojp-	ХУХ	JX7"	• • * 
    ^				; 
    место	ДЛЯ  •	XT мощность 

    Рис.   14.1 

    Поиск места для вставки е можно совместить с бинарным поиском е в 
множестве: если последнее подозреваемое число оказало?!, меньше е, то е надо 
вставлять правее этого числа; если равно е, то е принадлежит множеству; если 
больше е, то е надо иставлять левее. Поэтому изменим назначение программы 
«искать», и именно потребуем, чтобы в случае «не нашли» эта программа пидавала 
индекс того элемента вектора, куда надо вставлять е, Тогда программа 
«добавить» реализуется следующим образом^ 

    216 ГЛ. 3. СТРУКТУРЫ   ДАННЫХ   И   ИХ   РЕАЛИЗАЦИИ 

    программа добавить элемент <вх : е : Е) в множество . дано        : есть 
свободное место . получить: 
    искать (вх : е, вых : нашли, ие) если не нашли то 
    цикл V и е ие..мощность реверс выполнять 
    .    .    вектор(и + 1) := вектор(и) 
    .    .    конец цикла 
    .    .    мощность.увеличить на 1 
    .    .    вектор(ие) := е 
    .   конец если 
    конец программы 

    В цикле сдвига элементов множества вправо стоит слово реверс. Это значит, 
что индексы из диапазона ие ., мощность перебираются в обратном порядке — 
справа налево, т. е. тело цикла сначала выполняется при и = мощность, затем 
при и = мощность — 1 и т. д., последний раз — при и = ие. Такой порядок сдвига 
элементов необходим, так как при переборе элементов слева направо при 
пересылке, например, элемента с индексом ие в элемент с индексом' ие + 1 
старое значение элемента с индексом ие + 1 было бы поте* ряно, а ведь именно 
его надо пересылать в элемент с индексом ие + 2. 
    В программе «удалить», где элементы множества надо сдвигать влево, 
наоборот, нужно использовать обычный цикл: 

    программа удалить элемент (вх : е : Е) из множества . дано        : получить: 
    .    искать (вх: е, вых: нашли, ие) 
    .   если нашли то 
    .    .     цикл V и е ие..мощность   —1 выполнять 
    .    .     . вектор(и) := вектор(и-Ь О 
    .    .     конец цикла	' 
    .    .    мощность.уменьшить на 1 
    . конец если 
    конец программы 

    Реализуем теперь программу «искать» для бинарного поиска о учетом 
сделанных выше замечаний. 
    Несмотря на простоту идеи, реализовать бинарный поиск без ошибок не так 
просто. Поэтому подойдем к реализации более (pops мально, чем обычно, и 
явно'выпишем все инварианты и 

    14.   ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 217 

    ния по схеме проектирования цикла с помощью инварианта. Мы приведем два 
варианта программы бинарного поиска. Первый из них в точности соответствует 
описанному выше процессу поиска числа е среди задуманных. В .соответствии с 
этим описанием у нас будет диапазон а .. b номеров подозреваемых чисел 
(диапазон индексов подозреваемых элементов вектора). В начальный момент (до 
первого вопроса) элемент е может оказаться на любом месте и подозреваемыми 
являются все индексы элементов множестваз 

    а=1,    b = мощность. 

    После каждого вопроса этот диапазон уменьшается как минимум вдвое. Процесс 
заканчивается либо в момент обнаружения элемента е, либо, если е множеству не 
принадлежит, когда подозреваемых индексов ие останется (диапазон а .. b станет 
пустым). Выберем, в качестве шшаршшта следующее утверждение: 

    Ь>а—1 и 
    элементы с индексами вне диапазона а..Ь вне подозрений. 

    Пторая часть этого утверждения означает, что элементы множе-< (••та, 
расположенные левее а, меньше е, а элементы множества, рисположсппыс правее Ь, 
больше е. С учетом упорядоченности элементом |н'ктор(1), вектор (2), .,,, 
вектор (мощность) инвариант можно записать так: 

    Ь>а-1	и (а «=• 1| или е > вектор(а — 1)) и (Ь = мощность или е < вектор(Ь 
+ 1)). 
    триграмма испить (вх:е:Е, вых : нашли : да/нет, ие : индекс) 
    . дино         : |»лгм1Ч1П4 вектора с индексами 1. .мощность возрастают 
    . получить: | ИР такое, что элементы вектора с индексами 1..ие— 1 
    (меньше е, а элементы с индексами ие..мощность ^е, 
    нашли = (иеХ: мощность и вектор(ие) = е) | -<=>• е е М 
    им т ли := нет 
    мощность = 0 то ие :=• 1 иначе 
    « : -• 1: b := мощность | подозреваем элементы с индексами а. .Ь 
    ЦИКЛ 
    .   инв: b > а — 1	и 
    . (а = 1 или е > вектор(а — 1)) и 
    . (Ь •= мощность или е < вектор(Ь + 1)) 
    . (элементы с индексами вне а..Ь вне подозрений 
    . пока не нашли и   а ^ b | (не нашли и есть подозреваемые) 
    . выполнять 
    i   с := частное(а + Ь, 2); утв: а< 


    218 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И  ИХ  РЕАЛИЗАЦИИ 


    .    .     .    выбор 
    ,   .     .    .   при е < вектор(с) =*• b :=c—I 
    ....   при е = вектор(с) =»- а:=с; Ь:=с; нашли :=*да 
    .   .    .   .   при е > вектор(с) =»• а :=с + 1 
    .    .     .    конец выбора 
    .    .    конец цикла 
    •^f—   утв: (а = 1	или е > вектор(а — 1)) в S.   •                  (а = 
мощность + 1 или е ^ вектор(а)) 
    •        * 
    .   .      | это утверждение можно переписать в виде: 
    .   .         утв: (а = 1	и е<! вектор(1))                         ила .   
.                 (1 < а < мощность и вектор(а—1) < е^вектор(а)) или .   .     
           (а — мощность + 1 а вектор(мощность) < е) .   .    ие:=а .   конец 
если конец программы 
    Условие окончания цикла «нашли или а > Ь» можно переформулировать в виде 
    (а = b и е = вектор(а)) или а = b + 1. 

    После этого постусловие (утверждение после слов конец цикла) можно строго 
формально вывести из инварианта и условия окончания (сделайте это). 
    Осталось проверить, что независимо от успешности или безуспешности поиска 
цикл рано или поздно заканчивается. Это следует из того, что при каждом 
выполнении тела цикла либо обнаруживается искомый элемент, либо разность b — а 
уменьшается по крайней мере на 1. 
    Приведенная  выше_ программа  обладает тем  недостатком, что _ 
    -*;вывод"постусл6вйя"из инварианта и условия окончания не является 
очевидным. Это вызвано тем, что мы строили программу в соответствии с 
интуитивным алгоритмом бинарного поиска, а потом пытались показать ее 
правильность, используя схему проектирования цикла с помощью инварианта. Можно 
поступить по-другому — отказаться от интуитивного алгоритма и строить 
программу, исходя из схемы проектирования цикла с помощью инварианта. В 
соответствии с этой схемой вначале надо выписать постусловие (конечную цель): 
    вектор(ие — 1) < е <[ вектор(ие). 
    Это постусловие, впрочем, не вполне верно. Например, если множество пусто 
или е ^ вектор (1), то нам надо получить ие = 1, а элемента с индексом не—-1 
вообще не существует. Но пока pai;

    14. ТРИ'СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА' 219 

    смотрим только общий случай с выписанным выше постусловием. Наша цель 
сейчас — придумать общую стратегию, инвариант и условие окончания, которые 
приводили бы к этому постусловию. Общая стратегия у нас фиксирована — это 
бинарный поиск. Значит, будет какой-то подозреваемый диапазон а.. Ь, который 
будет примерно вдвое уменьшаться при каждом выполнени и тела цикла. Но тогда с 
точностью до обозначений можно переписать постусловие jj__ терминах 
^вменяющегося в цикле __объекта— диапазона а .. bi	" """"" ——~ вектор(а) < е < 
вектор(Ь) и а = b — I. 
    Дальше   уже  просто — теперь   постусловие,  очевидно,  распадается па инвариант	• 
    вектор(а) < е < вектор(Ь) 
    н условие окипчишш а —Ь— 1, 
    II  полная  реализация с учетом особых случаев выглядит так: 
    программа искать (вх: е: Е, вых: нашли : да/нет, ие: индекс) . дано        
: | моменты вектора с индексам'й 1.. мощность 
    шкфпстают . получить: | ие такое, что элементы вектора с индексами 1..ие— 1 
    [меньше е, а элементы с индексами ие..мощность^ ч 
    '| нашли = да -Ф=> е е множеству 
    ие := ие : 
    выбор 
    .   при мощность —0 или е<вектор(1) 
    .    при иск юр! мощность) < в 
    .    мнйче •+ 
    .	утв: множество не пусто и 
    .	вектор(1) < е ^ вектор(мощность) 
    • 
    >       а :=> 1; b := мощность 
    i       цикл 
    •       .   инв: вектор(а) < е ^вектор(Ь) i       .   пока а =И= b — 1 
выполнять .    с := (а + Ь)/2; утв: а < с < b 
    •       .     выбор 
    •   . . при вектор(с) < е =*• а := с .  . . при вектор(с) = е => b := с; а 
:= 1 .   . . при вектор(с) > е =>- b := с .   . конец выбора Л •'. конец цикла 
    1 
    = мощность + 


    220 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ И  ИХ  РЕАЛИЗАЦИИ 


    .   .	утв: вектор(а) < е ^ вектор(Ь) и b = а + 1 
    .   .       ие:=Ь 
    .    конец выбора 
    .    нашли := (ие ^ мощность и вектор(ие) = е) 
    конец программы 

    Завершение цикла в этой программе также обеспечивается монотонным 
уменьшением величины b — а. 
    Количество операций при бинарном поиске по сравнению с последовательным 
сокращается с п до Iog2(n). Однако заметим, что при этом добавление и удаление 
элемента множества становятся массовыми операциями, требующими порядка п 
элементарных действий с вектором. Таким образом, реализация множества с 
помощью бинарного поиска эффективна только в том случае, если множество 
меняется редко,~~а принадлежность того или иного элемента "множеству надо 
определять достаточно часто. Существуют ссылочные реализации множества на базе 
вектора, использующие бинарный поиск и позволяющие добавлять или удалять 
элементы не более, чем за Clog2(n) элементарных операций. Мы, однако, эти 
реализации рассматривать не будем. 
    Битовая реализация множества элементов типа 1 .. максинд. Итак, и 
последовательный, и бинарный поиск имеют и свои до-йтоинства и недостатки. 
Выигрыш в скорости при бинарном поиске достигнут, образно говоря, за счет 
того, что мы «пожертвовали» добавлением и удалением, которые^теперь стали 
массовыми. Кроме того, несмотря на «жертвы», сам бинарный поиск также остался 
массовой операцией — количество действий с вектором по-прежнему зависит от п, 
хотя теперь эта зависимость логарифмическая, а не линейная. Естественно, 
возникает вопрос: а существует ли вообще деализация множества, .при .которой 
ДОЖК не является массовой операцией? И можно ли при этом не «жертвовать» 
добавлением и удалением? 
    Есть по крайней мере один частный случай, когда такая реализация не только 
существует"," "но~й очевидна^ — это случай, когда число значений типа Е 
невелико, и это число можно использовать в качестве максинд. Например, если Е 
= 1 .. максинд, то можно реализовать множество элементов типа Е на базе 
вектора элементов типа да/нет с индексом типа 1 .. максинд (т. е. с индексом 
типа Е), ^просто запоминая в каждой компоненте вектора, принадлежит или нет 
соответствующий элемент множеству: 
    вектор(и)=да •*=*- элемент и принадлежит множеству. 
    В этой реализации элементы вектора могут принимать лишь одно из двух 
значений. -** да или нет. Эти элементы часто называют 

    и. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА	221 

    битами   (от  англ,  binary  digit-двоичная  цифра),   а   реализацию в 
целом — битовой, исполнитель множество I элементов типа 1. .максинд на базе 
вектора • Cill» 
    .	1. начать работу 
    .	2. сделать множество пустым 
    .	3. множество пусто                                                    : да/нет .	
                 4. элемент (вх : е : Е) принадлежит множеству     : да/нет .	
                 5. добавить элемент (вх : е : Е) в множество .	
                 6. удалить элемент (вх : е : Е> из множества .	
                 7. взять какой нибудь элемент множества в (вых: е: Е) 	
           8. кончить работу 
    . 
    .   константы; 
    мпкснндш 100 
    типы: 
    Е = 1. .максинд 
    используемые исполнители: вектор | игнтор влемснтов типа да/нет с индексом 
типа Е 
    идеи реализации: 
    вектор(и) = да 
    и е множеству 
    оисц описаний 
    мри грамма начать ряЛоту «. 
    пгктор.иячять работу, сделать множество пустым сделен, множество пустым 
дино        [ 
    Получить) 
    . цикл V и е Е выполнять i •     и<чпор(и) := нет > Hour ц цикла Конец программы 
    программа множество пусто : да/нет . дино       ; i Получить: 
    I     *-	. ._ „ _т ,_ 
    i   Мшили := нет 
    f Цикл V и е Е пока не нашли выполнять 


    222	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И  ИХ  РЕАЛИЗАЦИИ 


    .    .    нашли := (вектор(и) = да) 
    »   конец цикла 
    .    ответ := не нашли 
    конец программы; 
    программа элемент (вх!:е:Е) принадлежит множеству: да/нет === 
    (вектор(е) = да) 
    программа добавить элемент (вх: е:Е) в множество == 
    вектор(е) := да 
    программа удалить элемент (вх:е;Е) из множества == 
    вектор(е) :== нет 
    программа взять какой нибудь элемент множества в (вых: е: Е) . дано        
: множество не пусто • получить: 
    . цикл V е г Е пока вектор(е) = нет выполнять 
    , ,    ничего не делать 
    • конец цикла 
    ,      утв: вектор(е) = да 
    . удалить элемент {вх: е) из множества 
    конец программы 
    программа кончить работу == вектор.кончить работу 
    конец исполнителя 
    | = = = =а = = =,=а=. = = =-. = = ^ = = „- = =»=.= 

    В этой реализации массовыми являются операции «сделать пустым», «множество 
пусто» и «взять». Анализ пустоты множества легко сделать не__массовой 
операцией, если ввести глобальный объект «мощность» и использовать его для 
хранения числа элементов в множестве аналогично тому, как это было сделано в 
последовательном и бинарном поиске. Операцию «взять» можно сделать не 
массовой, если использовать еще один вектор ссылок с индексами'"от""(Г до 
максинд, с помощью этого вектора объединить элементы множества в кольцо, 
начинающееся со служебного элемента пил = 0, и при добавлении/удалении 
элементов множества включать/исключать их из этого кольца так же, как мы 
освобождали/захватывали свободное место в ссылочной реализации Л1-списка. 
Операция «сделать^множество _ггустым» по^ сути реализации является массовой, 
но обычно она достаточно редка, и ее массовостью можно пренебречь. 
    Подчеркнем еще раз, что битовая реализация множества элементов типа Е 
применима только в случаях, когда значения типа Е можно использовать в 
качестве индексов некоторого вектора (т. е. когда тип Е является отрезком или 
перечислением), Но если уж битовую реализацию удалось применить, то добавление/удаленна 

    14. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 223 

    и ^пнализ принадлежности элемента множеству в ней проводятся за 
jWHy"'~onepauHio с вектором — вряд ли этот результат можно превзойти! 
    Хеширование. Итак, пока что наша мечта — поиск, не являющийся массовой 
операцией, — в общем случае осталась недостиг-нутой. Вспомним самое начало — 
непрерывную реализацию множества на базе вектора (последовательный поиск). Мы 
говорили, что основное отличие этой реализации состоит в том, что нам 
приходится искать элемент е в векторе, в то время как при реализациях стека, 
очереди, дека, последовательности индекс доступного элемента структуры (т. е. 
индекс вершины стека, начала очереди, начала или конца дека, очередного 
элемента последовательности) 

    О	1            2           3             • • •           р-1 

    Рис.   14.2 

    предопределен салоп  структурой.  Вот если  бы по элементу  МНР-ЖГГП1М   
мшимо   Лило   I'pn.iy   yiuriiiTb   индекс   компоненты   вектора, 1Дс     MI 
пгмепт  лежит!   Ведь  для  решения   именно  этой  задачи мы  HIM.in  
iipiii |>амму «искать». Увы, такое возможно^тодько в том,_ «•луч.и1,  если  
число различных значений_типа ЕjpaBnB)]количеству      / мгмемтоп в некотором 
векторе — тогда значения типа Е можно (па     ( мрнЛнсй мере теоретически) 
взаимно однозначно отобразить на мно-жепио   индексов,  а   в  компонентах  
вектора  хранить  информацию и том,  принидлежпт соотиетстпующее значение типа 
 Е  множеству или   нет   ,Ч|и  и   ксгь  бншиим  ршпиицнн   множества   
(^JJPJ^MePe RUI llf ос ' |м темпе ошт тиждсстцснпым). 
    Km,- ил, однако, конечная цель, т. е. ради чего мы избегаем мштопых 
операций при поиске? Очевидно, это скорость выполнении iipoi|>;iMM при работе 
с достаточно большими множествами. II» дли достижения высокой скорости вовсе 
не обязательно, чтобы ItUMt'N Hi'etilti шлюлнялся быстро; достаточно, если он 
„будет ,,быст< |'ЫМ почти исседа, т. е. надо интересоваться количеством 
операций Hf R Пйихудшем! а в некотором типичном. 9ЛУ1ае- ^ тогДа можно 
впГПОЛ1,:1оваться идеей об отображении зиаченийЪгипа Е на мноМ<Н'1ё« индексов, 
те требуя взаимн'ой однозначности  отображёнйя74 Рйссмотрйм   на   
простейшем"" примере,  как 'такое' 'отображение,, Мй*||Ц|пгм(11> хеш-функцией, 
 может ускорить работу  с множеством, llyi'Tii h: E->0 ,. р— 1 отображение 
множества значений типа И  ни   множество  из  р  элементов  О,   1,  2, 
,,.,р—1   (рис.   14.2)4 ju полосы над точками О,  1, 2, ,,,, р — 1 изображают. 


    224	ГЛ. 3. СТРУКТУРЫ ДАННЫХ И ИХ РЕАЛИЗАЦИИ 


    множества-слои   h-'(O),   h-«(l),   h-'(2), .... h-i(p - 1)    соответ-1 ственно. 
    Напомним, что исполнитель «множество элементов типа Е» моделирует  
конечное   подмножество   М  множества  значений   типа   Е, 


    (14. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 223, 


    Предположим, что М состоит из трех элементов а, Ь, с и что в «укаждом   
вертикальном   слое  лежит   не   более   одного  элемента   М {рис. 14.3). 
Тогда можно применить идеи битовой реализации — введем    вектор    «бит»    
элементов    типа    «да/нет»    с    индексом    типа 

    .а		.Ь		* « «	• с 
    о	1	2	3	• * •	Р-1 
    да	нет	да	нет	• • «	Яа    | 

    Рис	14.4 

    О .. р — 1 и запишем в элементы этого вектора да, если в слое над 
элементом есть точка из М, и нет в противном случав -{рис. 14.4).	/ 
    Пусть теперь надо определить, принадлежит ли элемент е типа Е множеству М. 
Можно действовать так: вычислим(Т=« Ь(е))и посмотрим, чему равно бит(1). Если 
битО)=нет, то элемент е заведомо не принадлежит М (так как в слое над 1 
элементов М нет). 

    бит! 
    .л		-• .Ь		• * .	.с 
    о	1            2		3	• * «           р-1 
    да	нет	да	нет	...	д» 

    Рис.   14.5 

    Если же бит(1) =да, то про е ничего сказать нельзя —нужна до-лолнитёльная 
информация.  Например,  если  h(e)=2,  то  е может *   совпадать с Ь, а может 
и не совпадать (рис. 14,5), 
    Поскольку мы предположили, что в каждом вертикальном слое лежит не более 
одного элемента М, то для задания этой дополнительной информации достаточно 
ввести еще один вектор «инф» Элементов типа Е — если .слой над i содержит 
точку т<=М, то инф(1)=т (рис. 14.6). 

    ннф! 
    ••		И, 
    0123 
    да	нет	да	мет 
    
    
    а		Ь	1 
    р-1 
    J-ZJ 

    Рис.   14.5 

    Итак, если сужение h на М не склеивает точек, то   ; i   е е М •«=»• 
бит(Ь(е)) = да и инф(Ь(е))_*= е.     __ ..-—.л, 
    Следовательно,  число  операций  при  поиске  не зависит  от числа 
элементов в М. 
    На практике, однако, h фиксируется заранее, а множество М меняется в 
процессе работы. Поэтому гарантировать инъектив--ность ограничения h на М 
нельзя — в некоторых слоях может ока* ваться более одного элемента, М. 
Например, для h, d a M может оказаться, что h(b)=h(d)=2. Что записать в инф(2) 
в этом случае (рис. 14.7)? 

    ••		.d .Ь 
    О            i             2             3 
    да	нет	да	нет \ 
    л		•? 
    р-1 
    т^п 

    Рис.   14.7 

    Хотелось бы записать в инф (2) одновременно Ь и d, но это невозможно — 
элемент вектора «инф» может хранить только одно вначение типа Е. Выход из этой 
ситуации состоит в том, чтобы вместо вектора «инф» элементов типа Е 
использовать вектор множеств элементов типа Е (рис. 14.8), Вектор «бит» при 
этом ста-поится ненужным, так как про множество можно узнать, пусто оно или нет. 

    8    А. Г. Кушниреико, Г. В, ЛсОедсв 
    226	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И  ИХ  РЕАЛИЗАЦИИ 

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

    .л		.d	•v. 
    .Ь 
    о	1           2		3 
    |*1                    to			1 
    d 

    Рис.   14.8 

    бинарный поиск. Можно, однако, рассмотреть какую-нибудь функцию на 
множестве таких карточек, например сопоставить каждой карточке первую букву 
названия книги (это и есть хеш-функция)„ а сами карточки разложить по 
отдельным ящикам — в один ящик | положить все карточки, начинающиеся с А, в 
другой — с Б и т. д. Тогда при поиске книги можно посмотреть на первую букву 
ее названия, взять соответствующий ящик и искать только в нем. (Название 
«хеширование» — от английского глагола hash — рассекать, рассеивать, 
разрезать, разбивать — как раз и означает такое разбиение множества на части, 
соответствующие значениям «рассеивающей» функции.) 
    Заметьте, что фактически получилась опять та же задача —« надо найти 
конкретную карточку в некотором их множестве. Однако можно надеяться, что 
«подозреваемых» карточек стало в 30 (число значений хеш-функции) раз меньше. 
Эту новую задачу по« иска в меньшем множестве можно решать любым образом — 
последовательным перебором всех карточек в ящике, упорядочением карточек в 
алфавитном порядке и бинарным поиском либо опять хешированием. Последнее 
означает, что надо придумать какую-то новую хеш-функцию, например сопоставить 
каждой карточке вторую букву названия или первую букву фамилии автора или 
число букв в названии и т. д., разгородить ящик на отделения, соответствующие 
значениям выбранной хеш-функции, и разложить карточки соответствующим образом. 

    «4. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 227 

    Обратите внимание, что при применении хеш-функция можно лишь надеяться на 
уменьшение числа подозреваемых карточек Эти надежды базируются на 
предположении, что если разбить данное конкретное множество карточек в 
соответствии со значениями данной конкретной хеш-функции, то в каждом ящик» 
карточек окажется примерно поровну. Таким образом, эффективность хеши» рования 
целиком зависит от того, _сколь_ равномерно данная хеш-функция разбивает 
данное множество. В наихудшем Мучае (например, если картотека содержит данные" 
только о книгах, начинающихся со слов «К вопросу о .,,») все карточки 
мог^т_попасть в один ящик (о буквой К) и хешировашШ-шг'М'Йоту и» облегчит нашу 
"задачу. Тем не менее, как показывает пример <$иблиотечных каталогов, если 
хеш-функция достаточно хороша, то применение хеширования позволяет во много 
раз повысить скорость поиска. 
    Вернемся теперь на более формальные, программистские рель* сы. Пусть 
имеется хеш-функция hi E-*0Mp— 1, принимающая р различных значений от 0 до р 
-» 1, Описанный выше механизм хеширования означает, что при однократном 
применении хеш-функ* ции множество М элементов *ипа В разбивается на р 
подмно-1 жеств: 
    Mi — {е G М : h(e) — i),    i — О, 1, 2, . , „ р — 1, 
    после чего все операции  над М сводятся к операциям над соот-петствующим 
MI. Действительно, в соответствии с определением Мц 
    добавление элемента е в множество М означает, что е надо добавить в Mh<«) 
и т. д. Соответствующая реализация множества на базе р множеств выглядит 
следующим образом: 
    исполнитель Ограниченное множество | на базе р множеств 
    .	СП: 
    ,	1. начать работу 
    .	2. сделать множество пустым 
    ,	3. множество пусто                                                   !да/нет 
    •	4. есть свободное место                                           :да/нет 
    б. нет свободного места                                           :да/нет 
    .	6. элемент (вх : е : Е) принадлежит множеству     :да/не# 
    •	7. добавить элемент (вх t е : Е) в множество 
    .	8. удалить элемент (вх : е I E) из множества 
    ,	9. взять йакой нибудь элемент множества в (вых : е i E) 
    ,	— искать непустое (вых J нашли ) да/нет, п : номер) 
    .	— h (вх ! е) : номер | хеш-функция 
    ,	10. кончить работу 


    228 ГЛ. 8. СТРУКТУРЫ   ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 


    константы: 
    р = 1019 
    типы: 
    номер = 0. .р — 1 
    .   используемые исполнители: 
    р множеств (ПМ) 
    идеи реализации: 
    е е множеству 
    ; ПМ.множество с номером (h(e)) 
    конец описаний | -_------------------_. 
    программа начать работу == ПМ.начать работу программа сделать множество 
пустым . дано        1 . получить: 
    .    цикл V п е номер выполнять 
    ,   .    ПМ.сделать множество (вх:п) пустым 
    . конец цикла 
    конец программы 
    программа множество пусто : да/нет . дано       : . получить! 
    .   искать непустое {вых: нашли, п) ,   ответ := не нашли конец программы 
    программа есть свободное место : да/нет == 
    ПМ.есть свободное место 
    программа нет свободного места : да/нет == 
    ПМ.нет свободного места 
    программа элемент (вх:е:Е) принадлежит множеству:да/нет «==» ПМ.элемент 
(вх:е) принадлежит множеству (exjh(e)) программа добавить элемент (вх: е : Е) 
в множество == 
    ПМ.добавить элемент (вх: е) в множество (вх:п(е)) программа удалить 
элемент (вх:е:Е) из множества == 
    ПМ.удалить элемент (вх: е) из множества {вх:Ь(е}) 
    программа взять какой нибудь элемент множества в (вых: е: Е) . дано       
: множество не пусто . получить: 
    04. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 229 
    .    искать непустое (вых : нашли, п) 
    утв: нашли 
    .   ПМ.взять какой нибудь элемент множества (вх:п) в (вых:е) конец программы 
    программа искать непустое {вых : нашли : да/нет, п: номер) . дано        : 
. получить: 
    .   цикл V п е номер пока ПМ. множество (вх:п) пусто выполнять 
    .    .     ничего не делать 
    .   конец цикла	* 
    .    нашли := (п «т*1 иеопр) 
    конец программы 
    программа кончить работу =»= ПМ. кончить работу 
    конец исполнителя 
    | --. — .--==.=.===-======_ = = _=^====.= 

    Реализацию хеш-функции, поскольку она зависит от приложений, мы опускаем. 
Заметим лишь, что очень часто хеш-функция икает вид h(c)-= f(c)modp, где р — 
прост&е, a f(e) функция с целыми .•шн'кчшнми. Типичными примерами f являются 
функции «сум-мп цифр числа е» или «само число е» (для E=*jZ), «первый 
сим-иол», «число символов», «сумма кодов символов» (для Е =» после» 
донительность элементов типа символ) и др. 
    Функция «сумма кодов символов» на множестве последовательностей Луки 
французского алфавита описана у Л. Н. Толстого (Война и мир, •.. Mi.ppy Пили 
открыто илннм in ripnri.rn млсошш следующее, выведен-N0* и» Липнилшп in « 
Нилина IMIIOC/IUII», пророчество относительно Hanoi «•nun, It Лшжплипснсс, 
главе тринадцатой, стихе восемнадцатом сказано «11л* мудрость есть; ижа имать 
ум да почтет число зверино: число б'о чилшшчсско есть и число его шестьсот 
шестьдесят шесть». II той же главы в стихе пятом: «И даны быша ему уста 
глаголюща млнкя и хульна; и дана бысть емУ область творити месяц четыре — 
де(HTh   ДНИ». 
    Фрямцу)ские буквы, подобно еврейскому число-изображению, по коте* (ищу 
nrpiiMMH десятью буквами обозначаются единицы, а прочими — де> HIKII, имеют 
следующее значение: 
    abcdefghik   I    mn   о   р 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 qrst      
uvwxyz 70 80 90 100 ПО 120 130 140 150 160 
    И ШМОН по  этой  азбуке цифрами слова  L'mpereur  Napoleon, выходт. *пч 
г»има   «тих   чисел   равна   666-ти  и  что   поэтому  Наполеон  есть  тот 

    230	ГЛ. 8, СТРУКТУРЫ  ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

    о котором предсказано в Апокалипсисе. Кроме того., написав по этой азбуке 
слова quartnte deux, то есть предел, который был положен зверю глаголатн 
велика и хульна, сумма STHX чисел, изображающих quarante deux, опять равна 
666-ти, из чего выходит, что предел власти Наполеона наступил в 1812-м году, в 
котором французскому императору минуло 42 года». 
    Изложение собственно хеширования на этом заканчивается, В программировании 
довольно часто максимальное число элементов имитируемого множества М меньше р. 
Таким образом, при? достаточно хорошей хеш-функции каждое из подмножеств Mi 
содержит обычно не более одного элемента и поиск элемента в множестве 
осуществляется мгновенно независимо от способа реализа* ции множеств MI. 
    Для завершения хеш-реализации множества осталось реализовать исполнителя 
«р множеств (ПМ)» на базе одного вектора. Реализацию проведем ссылочным 
образом. В соответствии с идея" ми предыдущего раздела это значит, что у нас 
будет р + 1 траектории — по одной на каждое множество и одна для свободного 
места. Траектория n-го множества будет начинаться с индекса п (нил этого 
множества), траектория «свободное место» будет начинаться с индекса р (нил 
свободного места). Внутри каждого отдельного множества будем хранить элементы 
неупорядоченными и использовать последовательный поиск; 

    исполнитель р множеств (ПМ) | ограниченных в совокупности . СП: 
    .     1. начать работу 
    .     2. сделать множество (вх: п: номер) пустым 
    .     3. множество (вх: п : номер) пусто	.  :да/нет 
    .     4. есть свободное место                  :да/нет 
    .     б. нет свободного места                  :да/нет ,.     
          6. элемент (вх : е) принадлежит множеству (вх : п : номер)   :да/нет ,     
          7. добавить элемент (вх:е:Е) в множество (вх:п: номер) 
    .     8. удалить элемент (вх: е i Е) из множества (вх: п: номер) 
    .     9. взять какой нибудь  элемент  множества (вх : п) в (вых : е 
: Е ,   — искать (вх: е: Е, п: номер, вых: нашли: да/нет, указатель) .   — 
связать (вх:И1, И2: индекс) .    — захватить место (вых: И: индекс) .    — освободить место (вх:И:индекс) 
    .    10. кончить работу   
    .	константы!   .	р            «= 1019 
    .	максинд = р + 1000 
    '•     ,   типы: 


    14. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА 231 


    i     индекс = 0. .максинд .     номер о»0. .р — 1 
    • 
    .   используемые исполнители; 
    .     информация: вектор Е(р + 1.. максинд) 
    .      ©следующий : вектор индекс (индекс) 
    .   обозначения: 
    .     нил свободного места ==• р 
    • 
    .   идеи реализации: 
    .     Каждое состояние вектора "^следующий" определяет 
    .     отображение i множества индексов в себя:	• f : и -> вследующий(и). 
    ,     Мы реализуем "р множеств" так, что в каждый момент времена 
    .     отображение f взаимно однозначно и имеет ровно р + 1 траектории. 
Множество с номером п определяется траекторией, проходящей через точку п (нил 
этого множества). Каждой точке I 
    .     этой траектории кроме точки п отвечает «лемент множества, лежащий в информация(1). 
    конец описаний | _-_--____ —— ___ ————— ____________ 
    программ» начать работу . дано : максинд > р . получить: | траектория 
каждого множества состоит из точки ния 
    | траектория свободное место=» .	|                     нил свободного 
места .. максинд 
    . информация. нлчать работу . вследующиА.нпчпть работу 
    . цикл V и е номер выполнять 
    . .     связать (п,п) [траектории множеств 
    . конец цикла 
    . цикл V И о нил свободного места .. максинд-1 выполнять 
    . .     считать (И, И + 1) 
    , конец цикла 
    , снизать (максинд, нил свободного места) 
    пинец программы 
    программа сделать множество (вхш: номер) 
    i дано 
    . получить: множество (вх$п) пусто 

    232 ГЛ. 3. СТРУКТУРЫ   ДАННЫХ   И   ИХ  РЕАЛИЯ МШИ 

    .   цикл пока множество (вх: п) не пусто выполнять 
    И :»=< ©следующий (п) . .       связать (п, ©следующий (И)) . .       
освободить место (вх: И) . конец цикла конец программы 
    программа множество (вх: п : номер) пусто: да/нет ==» 
    (©следующий (п) = п) 
    программа есть свободное место : да/нет == 
    (©следующий (нил свободного   места) =/= нил свободного места) программа 
нет свободного места: да/нет == 
    (©следующий (нил свободного места) = нил свободного места) 
    программа элемент (вх:е)  принадлежит множеству  (вх: п): да/нет 
    . дано        : . получить: 
    .   искать (вх:е,п, вых: ответ: да/нет, указатель) конец программы 
    программа добавить элемент (вх: е: Е) в множество (вх: п: номер) . дано    
    : есть свободное место . получить: 
    | траектории п-го множества , | разместить информацию 
    .   искать (вх: е,п, вых: нашли: да/нет, указатель) 
    .   если не нашли то 
    .   ,    вахватить место (вых: И)	| из свободного места 
    .   ,    связать (И, в следующий (п))   | включить И в начало 
    .   .    связать (п,И)	• — --..—.... „_„„ ..—, 
    .   .    информация (И):™ е 
    . конец если 
    конец программы 
    программа удалить элемент (вх I е i Е) из  множества (вх: п: номер) 
    . дано        i , получить» 
    .	искать (вх: е,п, выхs нашли5 да/нет, указатель) 
    .	если нашли то 
    .	.    И:= указатель. @аа                                        (удаление 
эл-та с 
    .	,    связать (указатель.®до,©следующий (И)) |инд. И из мн-ва 
    .	.    освободить место (вх i И), [и включение в свободное место 
    .	конец если 
    конец программы 

    Т4. ТРИ СПОСОБА РЕАЛИЗАЦИИ МНОЖЕСТВА' 233 

    программа взять какой нибудь элемент множества (вх;п) в (вых;в) . дано     
   : множество (вх:п) не пусто . получить: 
    .   И :«= & следующий (п) 
    .   е := информация (И) 
    .   связать (п, @ следующий (И)) 
    .   освободить место (вх: И) 
    конец программы 
    программа искать (вх:е,п, вых: нашли,указатель) 
    . дано       : е: Е, п: номер 
    . получить: нашли : да/нет,  указатель : запись(@до,вза (индекс) 
    . указатель := (п, ©следующий (п)) 
    .  цикл пока указатель.® за ^ п и информация (указатель, 
    .   .    ВЫПОЛНЯТЬ 
    . .     указатель.© до : = указатель.© за 
    . .     указатель.©за := ©следующий (указатель,в8а) 
    . конец цикла 
    . нашли := (указатель.©за ^ п)	•» 
    конец программы 
    программа связать (вх: И 1.И2 : индекс) == 
    ©следующий (И1); «=»Ш 
    программа захватить место (вых: И I индекс) . дано       : есть свободное 
место . получить: 
    .   И !•— в следующий (нил свободного места) 
    .   связать (нил свободного места, ©следующий (И)} 
    конец программы 
    программа освободить место (вх: И: индекс) . дано       : . получить; 
    .   связать (Исследующий (нил свободного меота)) .    связать (нил 
свободного меота, И) конец программы 
    программа кончить работу == 
    информация.кончить работу! ввледующнй.кончить работу 
    конец исполнителя / *а 

    234 ГЛ. S. СТРУКТУРЫ  ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

    Замечание. В этом разделе мы занимались только реализацией .^множества. На 
практике чаще встречаются нагруженные множества, Приведенные выше реализации 
легко модифицируются и для реализации нагруженных множеств — достаточно 
параллельно с вектором «информация» завести вектор «нагрузка» я хранить в 
элементах втого вектора нагрузку влементов множества, 

    ЗАДАЧИ И УПРАЖНЕНИЯ 

    1. Модифицируйте непрерывную реализацию множества (последовательный поиск) 
так, чтобы при выполнении подряд нескольких действий с одним и тем же 
элементом (например, вопрос о принадлежности, а потом добавление) поиск 
элемента производился только один раз. 
    Указание. Введите глобальные объекты, в которых будет храниться информация 
о последнем обрабатывавшемся элементе, о его принадлежности множеству и в 
случае, если элемент принадлежит множеству, его индекс в векторе. 
    2. Решите задачу 1 для бинарного поиска, 
    3. Реализуйте множество М элементов типа Е на базе 
    а) хеш-функции h:E->0 .. р — 1, 
    б) вектора «мощность слоя» элементов типа Z+ с индексом типа 0 ..р — 1, 
    в) вектора «инф» элементов типа Е с индексом типа 0,.р— 1, 
    г) множества «остаток» элементов типа Е 
    «гак, чтобы были выполнены следующие соотношения: 
    1) мощность слоя (1)°= число элементов в 
    Mi = {rnsM:h(m)« 1} 
    2) если MI чь 0, то инф (i) e MI, М1\инф (i) s остаток, инф (i) ф. остаток 
(другими словами, если Mi содержит один элемент, то он помещается в инф(О) 
если MI содержит более одного элемента, то один из них помещается в инф(1), а 
остальные — в остаток), 
    4. Реализуйте нагруженное множество элементов типа Е с нагрузкой типа Y, 
модифицировав непрерывную реализацию множества. 
    5. Реализуйте нагруженное множество элементов типа 1,, максинд с нагрузкой 
типа Y, модифицировав битовую реали-вацию множества, 
    6. Реализуйте нагруженное множество влементов типа Е с нагрузкой типа Y, 
модифицировав хеш-реализацию множества, 
