Лекции по информатике (984119), страница 24
Текст из файла (страница 24)
Такие ситуации называются коллизиями или конфликтами, а метод прямой адресации таблиц па основании функции ключа получил название хеширование (ссааЫпя). 6.3.1 Выбор хеш-функции Хорошая функция преобразования ключей должна равномерно распределять их по всему диапазону значений индекса. При этоъс гсреобразование может быть весьма случайным.
Второе, не менее важное требование к хеш-функции — она должна эффективно вычисляться при сюмощи небольшого числа аппаратно поддерживаемых операций. В качестве первого примера хеш-функции возьмем функцию огс1®, обозначающую порядковый номер ключа А в множестве всевозможных ключей. Если таблица должна быть реализована в массиве из Лс элементов с индексами от О до Ж вЂ” 1, то хеш-функция НЯ = огс1(А;) шос1 1сс равномерно отображает значения ключа на весь диапазон изменения индекс:ов. Неоднозначность этого отображения пропорциональна количеству оборотов, накручиваемому на, длину мас:сив мощностью типа клкъча.
Чеъс болыпе кратность, тем болыпе коллизий, Кроме того, если ссс является степенью 2, то эта функция эффективно вычисляется арифметическим сдвигом, а не делением. Однако, для часто встречакнцегося клкнса-слова слова, отличающиеся только несколькими буквами, с большой вероятностью будут адресоваться одним и тем же индексом и не будут равномерно распределены по всему отрезку.
Придется тратить дополнительные ресурсы на многократное ретесаированае. Поэтому на практике в качестве Х рекомендуют брать простое число и заменять сдвиг более сложным делением. Еще один эффективный способ вычисления функции расстановки -- применение битовых аппаратно-поддерживаемых операций к части ключа в двоичном представлении. Правда, этот эффективный способ нередко проигрывает в равномерности. Другие примеры хеш-функций: е размер таблипы выбирается как степень,(н)ойки, из двоичного представления ключа вырезается середина (см. л.
р, №12). Этот способ обладает хорошей равномерностью распределения ыри равномерном поступлении ключей; ° умножение ключа на, некоторую константу. 6.3.2 Рехеширование Если ыри поиске в хеш-таблице обнаружилось, что строка, соответствующая заданному ключу, пе содержит искомого элемента (с этим же ключом), то необходима вторая попытка переадресовать этот ключ внутри таблицы.
Эта переадресация должна быть такой же быстрой, как первичное хеширование. Существует несколько методов генерации вторичного индекса: 1. ОрГапизовать списОк строк (.' иденти")ным !юрвичным клк)чом .У1(с). Элементы этОГО списка размещаются либо в основной таб'пще, либо вне ее в области переполнения. Недостаток этого способа в том, что необходимо обеспечивать управление этими вторичными списками с их хоть и малым, по линейным временем поиска: 2. искать желаемый элемент или пустую строку в окрестности этого ключа 1Т.
н. открьнпая адресаиия). Во второй ыопьггке последовательность индексов должна однозначно вырабатываться из любого заданного ключа.. Схема алгоритма поиска в хепь таблице такова: Ы: — Н®; О; геренов 11' Т~Ы).1еу -- 1( ФЬеп 1' Элемент найден у е1ве 11' Т[Ь1 ~. 1(еу -- 1гее ФЬеп 1' Элемента в таблице нет 1 е1ве Ьеи1п 1( Кон4ликт 3 1; 1П: Н(1() ~ СЯ; еп(1; ппЫ 1' .либо найден, либо его яелп в таблице,,либо она переполнена 1 Функция рехеширования ('11) так же важна, как и сама функпия хе)пирования. Если эта функция линейная, .то мы смотрим следующую строку таблипы ~строки закольцованы) и т. д. до тех пока не будет найден элемент с указанным ключом либо не встретится пустая строка (при вставке в таблицу .-.
наоборот). Следовательно, С = г, а вторичные индексы 6(, употребляемые при последующих попытках, вычисляются по следующему рекуррентному соотношению: 1) = О(Л) 6 =(Ьо (1)шо(1Х, 1=1...Ж вЂ” 1. Недостатком линейного рехеширования является концентрация строк вокруг первичных клк)чей, в то время ка,к желательно равномерное рассеивание вторичных клн)чей по ь(а.с(.'иву.
Другой распространенный спосоо рехеширования кеадрасиичное. В этом случае последовательность пробных индексов такова: ба=о® 6с = (6в + 7, ) шос1 .~~~, 7, = 1,, % — 1, Еще с тех времен, когда умножение было медленнее сложения, вычисление квадратов членов последовательности заменяют сложением с помощью рекуррентного соотношения, расписывая разность квадратов: 6,, = г~, .с1с = 21 + 1, начиная с 6о = О, до = 1 6ьы = 6с -~ с1с И,.сс = с1, + 2, г > О. Квадратичное рсхеширование позволяет избежать кучности метода линейных проб, причем практически за ту жс.
цену. Недостатком этого метода является то, что при поиске пробуются пе все строки таблицы и во вклквсспии элемента может быть отказано, в то время как в таблице есть свободные элементы. Можно доказать, что если Х простое число, то при квадратичном рехешировании просматривается не меньшс половины таблицы. После составления хсш-таблицы нас ожидает разочарование: напечатать так быстро заполненную таблицу в упорядоченном виде, да, егце с'охраняя естественный хронологический порядок равнозначных элементов, не удастся: организация массива в хеш-таблицу никак не упорядочивает его. Нужна с:ортировка. Но упорядочив элемснты, мы тут же потеряем возможность быстрого доступа к данным по ключу с помощью хеш-функции.
Третий способ рехеширования -- слйчайное. К вычисленному индексу добавляется случайная величина, масштабированная под длину таблицы. Главное в таком методе - - суметь восстановить случайную последовательность при поиске в таблипе. Эта проблема решается последовательностями псевдослучайных чисел, генерируемых линейным конгруэнтным датчиком ~64~. В стандартной библиотке С/С+ — есть функция эгапд(), устанавливающая начальное положение датчика дж| генерации новой последовательности по заданному начальному числу, полностью определяющему эту последовательность.
Очередное псевдослучайное число инициированной с помощью и аис1О последовательности можно получить посредством функциии без параметров гаис11 ). Проанализируем метод прямого доступа к таблицам. Нетрушю себе представить наиболее неблагоприятные случаи метода при ьключении элементов и при их поиске. Существуют резонансные примеры, которые будут кучно стрелять по небольшому числу индексов и пропускать альтернативы гсри разрешении коллизий. Любое существенно неравномерное распределение исходных ключей неудобно лля хеш-функций.
составленных в обратном предположении. Для сложностной оценки метода. хеширования необходимо убедиться в том, что среднее число проб будет несюлыпим. Если и, размер таблицы, а ьч число занятых строк в ней, то среднее число попыток Е для доступа. к таблице к некоторому сп(1 — а) ич случайному ключу. равно— , где а = — коэффициент заполнения таблицы.
а ' и,+1 Табулируя эту функцию, получим зависимость среднего числа попыток от коэффициента заполнения: а Е 362 0,1 1,.05 02з 1. 1.5 0,5 1,39 0,75 1,85 09 256 0,95 3,15 0,99 4,.66 0,1 1,06 0,25 1,17 0,5 1,50 0,75 2,50 0,9 5,50 0,95 10,50 Сведем в таблипу оценки различных методов доступа ~9Ц: Операция Размер таблицы Формулы 10 50 200 1000 Метод Вектор вклк) п.пие 5,50 25,5 101 501 поиск 5,50 25,5 101 501 включение 9,3 31,7 108 511 поиск 2,7 4,8 7,.0 9,0 Дерево поиска на, векторе Дерево поиска, на дин. структурах включениг 5,7 8,9 11,7 15 поиск 4,.2 7,1 10,,2 13,0 Хеш-таблицы включение 2,.25 2,25 2,25 2,25 (заполнены наполовину) поиск 1,25 1,25 1,25 1,.25 Из таблицы видно, что даже такой простой способ разрешения коллизий как линейное рехсширование существенно лу ппе поисковых деревьев в их самом изощренном варианте.
Основной недостаток таблиц с функциями расстановки по сравнению с динамическими древовидными структурагии фиксированный размер таблиц и трудность настройки на реальные требования. Успех метода хеширования обуславливается хорошей априорной оценкой классифицируемых элементов, которая позволяет с одной стороны не завышать размер массива, а с другой стороны — избежать трудоемких линейных рехеширований. !"рубо говоря, размер таблицы представляет собой несколько завышенную оценку максимального числа, элементов.
Эти цифры конкретно доказывают высокую производительность метода, хеширования. Даже при 95% заполнении таблицы необходимо лишь 3 попытки стоимостью в постоянное время каждое, чтобы найти свободное, место или обнаружить искомый ключ. При этом число попыток зависит лишь от коэффициента заполнения, а не от числа пустых строк в таблице. Детальное рассмотрение линейного рехеширования дает несколько худшее чиси 1 —— 2 ло попыток Ь' = . Табулируя Ь(а) с тем же шагом, получаем: 1 — а Не менее существенным недостатком таблиц прямого доступа является неудобство изъятия строк из расстановочпой таблицы, если имело место линейное, квадратичное или случайное рехеширование.
Древовидные структуры для этой цели остаются более привлекательными. Глава 7 Методы программирования 7.1 Модульное программирование К настоящему времени нам известны две простые технологии программирования 60-х годов: структурное программирование или программирование с ограниченным набором конструкций ~и без ио$о!). элементами которой являются нисходящая разработка структуры программы, пошаговая детализация и псевдокод ~19~, и процедурное программирование, основанное на широком использовании процедур и функций в том числе и для реализации операций и отношений реализуемых программистом типов данных ~271.
Процедурное программирование позволяет оперировать крупными прикладными понятиями, укрывая детали рсализав ии в телах процедур. Вспоминая определение типа данных вообще. мы можем вновь констатировать, что набор процедур и функций может быть использован для реализации нового типа данных, нс поддерживаемого ни аппаратурой, ни системой программирования. Такие типы данных принято называть абсшракшиыми типомп да~гсых (АТД) ~40~. Рассмотрим средства стандарта Паскаля для реализации ЛТД. Во-первых, Паскаль рассчитан на составление монолитных программ (ргоигагп) одним человеком за небольшое время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
