Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 76
Текст из файла (страница 76)
Хитрость заключаешься в способе размещения кажлого нового элемента в выделенном блоке памяти таким образом, чтобы позже его присутствие или отсутствие можно было определить без организации поиска по блоку. Рассмотрим, как это может быть слслано. Допус> пм, нам требуется добавить в множество 5, представленное блоком памяти !>ь новый элемент х, представленный битовой строкой В,, Сначала нам нужно определить, пе солсржится ли уже в этом множестве 5 элемент х; если не содержится, тогда нужно сто добавить. Мы отводим некоторос место в блоке и; для строки В., применяя так называемую <1>уякцию >кэшировиния к битовой строке В..
Эта функция хзш пруст (то есть разбивает на маленькие кусочки и затем перемешивает) строку В, и в результате выдает некоторый хэш-адрсс 1,. Этот хэш-адрес используе>ся как индекс, указывающий на местоположение ланной строки в блоке >ч,. Если элемент х солсржнтся в множестве 5, то он лолжен находиться в том месте, на который указывает хэш-адрес 1,. Если элемента х в множестве нет, то в это место следует поместить строку В.. Если впослелствии нужно узнать, содержится лп элемент х в множестве 5, то это можно сделать посредш.вом хэширования новой строки битов В„представляющей элемент х, и опрелеления хэш-алреса !., П<> полученному адресу отыскивается нужная позиция в блоке иь и размещенная там ранее битовая строка сравнивается со значением В, элемента х.
Таким образом, никогда нс требуется проводить какой-либо поиск в таблице. 6.1, Структурированные типы данных 271 Пока функция хзширования вычисляется относительно быстро и генерирует хзш-адреса, расположенные достаточно произвольным и равномерным образом, не требуется точного знания того, как именно работает зта функция. Данную мысль можно проиллюстрировать на следующем примере. Предположим, что мы отвели в памяти место под блок гь размером в 1024 слова (наиболее удобным вариантом для длины блока в двоичных компьютерах является степень 2). Предположим так- же, что объекты данных, которые нужно разместить в этом блоке, являются стро- ками символов, представленнымн битовыми строками длиной в два слова каждая.
В выделенном блоке памяти можно разместить до 511 различных элементов тако- го типа. Пусть начальный адрсс этого блока памяти равен а. Подходящим хэш- адресом для такой таблицы будет строка 1, длиной девять бит, так как формула а ~ 2 х !.всегдабудет генерироватьадрес в пределах этого блока. Мы можем вы- числить адрес 1, для данной битовой строки В. длиной в два слова с помощью сле- дующего алгоритма (предполагая, что В, хранится в словах з и Ь), 1. Умножаем з на Ь, получаем с (строка, состоящая также из двух слов). 2 Складываемдваслова,представляющихстрокус,получаемзначепиес,представимое одним словом. 3.
Возводим с в квадрат, получаем е. 4. Извлекаем центральные девять битов из е, полученная последовательность представляет собой адрес 1,. Даже самая лучшая функция хзширования не может гарантировать, что для различных элементов данных будут сгенерированы различныс хзш-адреса. Хотя желательно, чтобы функция хзширования распределяла адреса по блоку макси- мально равномерно, тем не менее почти неизбежно происходят гак называемые кшыизии, при которых дза элемента получают одгщ и тот же хзш-адрес.
1(оллизия обычно случается прп добавлении некоторого элемента к множеству. Мы обраща- емся к блоку пагияз и, указанному вычисленным для элемента хзш-адресом, и об- наруживаем, что он содержит данные, отличные от тех, которые мы хотим раз- местить (по для которых алгоритм хэшировапия сгенерировал точно такой же хэш-адрес). (Иначе говоря, различные элементы х и у получили один и тот же хзш- адрес ! ..) Суп!сствует много различных способов разрешения подобных коллизий. 1. Г!овторяое хэшпрование, Мы можем модифицировать исходную строку битов В. (например, умножив ее на постоянную величину) и затем заново применить к ней алгоритм хзширования, получив тем самым новый хзш-адрес. Если при этом снова случится кось пзия, то проводи~ся повторное хзширование до тех пор, пока не отыщется свободное место в блоке памяти или не обнаружится, что точно такой же элемент уже содержится в множестве.
2. Последовательный поиск. Начиная от той позиции в блоке, где случилась коллизия, можно начать последовательный (циклический) поиск до тех пор, пока не отыщется свободное место в блоке памяти нлн не обнаружится, что точно такой же элемент уже содержится в множестве. 3, Группирование данных. Вместо непосредственного хранения данных в блоке памяти можно подставить указатели, связанные со списками групп элементов с одинаковыми хэш-адресами.
После хэширования значения 6, и по- 272 Глава 6. Инкапсуляция лучения указателя на соответствующий список групп осуществляется поиск значения В, в этом списке, и в случае его отсутствия оно лобавляется в конец списка. Выбор той или иной функции хэширования зависит от свойств представления сохраняемых данных в виде битовых строк. Если функция хэширования достаточно хороша, а таблица заполнена не более чем наполовину, коллизии достаточно редки. Необходимость разрешения коллизий является причиной того, что в приведенном примере таблица лля размешения 512 элементов может использоваться только лля размещения 511 элементов.
В конце концов, алгоритаи разрешения коллизий должен найти своболное место, иначе этот процесс никогда не завершится. 6.1.9. Выполняемые объекты данных В большинстве языков программирования, особенно в компилируемых языках, таких как С или Ас!а, исходные выполняемые программы и объекты данных, которыми они манипулирук~т, являются отдельными структурами. По это не всегда так. В языках, полобных 1!ЯР и Рго!ой, выполняемые операторы могут являться ланными, которые доступны программе и которыми она может манипулировать.
Например, в языке 115Р все данные хранятся в виде списков. Выражение, лопустимое в версии 5с!аеше, Иеуапе вутопсг~оп (соса (а Ь с) (В е О) просто опрелеляет функцию с именем ааутилс11оп как операцию сопз, описанную выше. Эта функция хранится как связанный список, во многом похожий на любой другой список, То же самое можно сказать о языке Рго!ой и его операции солзо11, определенной Лля его списков правил. Хотя управление такими данными достаточно просто осушествляется при нш1 ольэо ванин описанных здесь спи оков ых структур, возможность запустить программу, молифицировать ее и снова запустим в течение одного ее запуска оказывает большое влияние на структуру ее выполнения.
Эта тема булет обсуждаться более подробно в разделе 6.3. 6.2. Абстрактные типы данных В ранних языках программирования, таких как РОК РКАХ и СО ВО!., возможность создавать новые (определяемые программистом) типы ланных ограничивалась определением подпрограмм. По мере развития концеппии типов ланнгях в новых языках программирования стали появляться средства для определения и реализации полностью абстрактных типов данных. В качестве примера можно привести конструкцика раскрасе языка Ас!а и с1ааз языков!ана и С++. В этой главе мы изучим более близкий к классическому подход к определяемым программистом типам ланных посредством исслелования конструкции подпрограмм: как определяются и реализуются процедуры, подпрограммы и функции.
В главе 7 мы рассмотрим, как язык Ас!а расширяет эту концепцию, вводя возможность инкапсуляции лан- 6,2. Абстрактные типы данных 273 ных, называемых пакетами (рэс~айез). Мы также разовьем эти идеи, используя понятие классов и возможность связывать исполняемые процедуры (например, методы) с этими объектами данных для создания того, что сегодня называется объектно-ориентированными программами, 6.2.1. Эволюция понятия типов данных Поскольку обычно аппаратура компьютера не предоставляет возможностей для определения и отслеживания ограничений на тины данных (наприме1х с помощью аппаратных средств невозможно определить различие между строками битов, представляющими вещестиенное число, символ или целое число), в языках высокого уровня предусматривается набор базовых типов данных, таких как вещественные и целые числа и строки символов. Для того чтобы арифметические операции сложения или умножения не применялись к объектам несоответствующего типа, осуществляется контроль типов.
Первоначально тип данныхоп ределялся какмножество значений, которые может принимать некоторая переменная. Типы данных непосредственно ассоциировались с отдельными переменными, так что каждое объявление определяло имя переменной и ее тиц. Если в программе использовалось несколько массинон, каждый из которых содержал 20 вещественных чисел, каждый массив объявлялся отдельно и для каждо~о нз них повторялось полное описание массива. Приблизительно в 1970 г. язык Разса1 расширил понятие типов данных до общего определения типа, применимого к множеству переменных. Определение типа задает сгруктуру объекта данных вместе с возможными связываемыми с ней значениями.
Для объявления конкретного объекта данных как принадлежащего определен ному типу требуется указать только имя переменной и название этого тина. В 70-х и. понятие типов данных расширилось еще дальше и переросло представления о типе просто как о множестве обьектов данных. В понятие типа данных был включен также набор операций над этими объектами.
Для элементарных типов данных, таких как целочисленные и вещественные, в языке предусмотрены средства объявления переменных этих тшюв и набор операций пад ними, представляющие единственный способ обработки программистом вещественных и целых чисел. Таким образом, представление целых и вещественных чисел в языке эффективно инкапсулировапо (то есть скры го от программиста). Программист может использовать пелые и пещественныс числа, не вникая н то, как именно онп реализованы и представлены в памяти.
Программист видит лишь назнание типа и список определенных для этого типа операций, посредством которых можно манипулировать объектами данных этого типа. Абстракции данных. Для того чтобы распространить ннеденное понятие инкапсуляции на определяемые программистом типы данных, мы определяем абстрактные типы данных как; 1) множество объектов данных (обычно используется одно или более определений типов); 2) набор абстрактных операций над этими обьектами данных; 2т4 Глава 6. Инкапсуляция 3) инкапсуляцию этих объектов н операций таким образом, чтобы пользователь нового типа данных не мог манипулировать объектами данных этого типа иначе, как только с помощью определенных абстрактных операций. Само определение в целом должно быть инкапсулировано таким образом, чтобы пользователю необходимо было знать лишь название типа и семантику доступных операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
