Второй шаг: выделяем старшую цифру (десятки) и распределяем ключи по своим спискам:

ключ 90 в список для 9, ключ 11 в список для 1, ключ 02 в список для 0 и т.д.

0	1	2	3	4	5	6	7	8	9

02 11 27 33 45 56 66 83 90

08 16 37 99

09 17

Объединение этих списков дает отсортированный набор:

02, 08, 09, 11, 16, 17, 27, 33, 37, 45, 56, 66, 83, 90, 99

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

· обнулить все 20 указателей

· циклом по числу элементов (m) распределить элементы по своим спискам, выделяя в ключе необходимую цифру

· циклом по 10 объединить списки в новый набор данных

В целом, поразрядная сортировка не эффективна при малых объемах входных данных, но чем больше этот объем, тем выше эффективность метода. Трудоемкость пропорциональна объему входных данных, что лучше чем у быстрой сортировки. Платой за это являются дополнительные затраты памяти для поддержки вспомогательных списков.

Интересно отметить, что данный метод очень хорошо подходит для современных архитектур вычислительных систем с конвейерной обработкой данных и использованием нескольких процессоров.

3.4 Практическое задание

Реализовать специальные методы сортировки:

· Простейшую карманную с использованием второго массива и без него

· Обобщенную карманную сортировку с повторяющимися ключами и дополнительными списками

· Поразрядную сортировку

Все методы реализуются как подпрограммы и поэтапно добавляются в главную программу.

Контрольные вопросы по теме

1. В чем состоят особенности специальных методов сортировки?

2. Какие условия должны выполняться для применимости простейшего метода карманной сортировки?

3. Как в простейшем случае выполняется карманная сортировка?

4. Как программно реализуется простейшая карманная сортировка?

5. Как реализуется простейшая карманная сортировка без использования второго массива?

6. Приведите практический пример простейшей карманной сортировки массива "на месте".

7. Как программно реализуется простейшая карманная сортировка с использованием только одного массива?

8. Какое обобщение имеет простейшая карманная сортировка?

9. Какие структуры данных необходимы для реализации карманной сортировки с повторяющимися ключами?

10. Как выполняется карманная сортировка для случая повторяющихся ключей?

11. Приведите практический пример использования карманной сортировки с повторяющимися ключами.

12. Какие достоинства и недостатки имеет карманная сортировка массивов?

13. Какие условия необходимы для применения метода поразрядной сортировки?

14. В чем состоит смысл метода поразрядной сортировки массивов?

15. Какие структуры данных необходимы для реализации метода поразрядной сортировки?

16. Приведите практический пример использования поразрядной сортировки.

17. Какие шаги необходимы для реализации метода поразрядной сортировки?

18. Что можно сказать об эффективности метода поразрядной сортировки?

19. Какие достоинства и недостатки имеет поразрядная сортировка?

20. Как программно выполняется поразрядная сортировка?

Тема 4. Поиск с использованием хеш-функций

4.1 Основные понятия

Пусть имеется набор из n элементов а1, а2, а3, . . ., аn с некоторыми ключами (как и раньше, для простоты будем считать, что сам элемент совпадает с его ключом). Требуется этот набор организовать в виде некоторой структуры данных с возможностью многократного поиска в нем элементов с заданным ключом. Эта задача может решаться различными способами:

· если набор элементов никак не упорядочен, то поиск выполняется прямым сравнением всех элементов в массиве или списке с трудоемкостью O(n)

· если элементы упорядочены в массиве или в дереве поиска, поиск более эффективно выполняется как двоичный, с трудоемкостью О(log 2 n)

Возникает вопрос: существуют ли еще более эффективные методы поиска? Оказывается, при выполнении некоторых дополнительных условий можно организовать исходный набор ключей в виде специальной структуры данных, называемой хеш-таблицей, поиск в которой ЛЮБОГО элемента в идеале выполняется за ОДНО сравнение и НЕ зависит от размерности входного набора. Другими словами, трудоемкость такого метода поиска, называемого хеш-поиском, пропорциональна О(1), что является абсолютным рекордом!

Метод хеш-поиска заключается в следующем. Исходные элементы а1, а2, а3, . . ., аn распределяются некоторым специальным образом по ячейкам массива. Пока будем считать, что число ячеек массива m > n. Идеальным поиском можно считать такой, когда по любому входному ключу сразу вычисляется индекс ячейки с этим ключом, без проверки содержимого остальных ячеек. Для вычисления индекса ячейки по входному ключу используется специальная функция, называемая хеш-функцией. Эта функция ставит в соответствие каждому ключу индекс ячейки массива, где должен располагаться элемент с этим ключом:

h (аi ) = j, j = (1, m);

Массив, заполненный элементами исходного набора в порядке, определяемом хеш-функцией, называется хеш-таблицей. Отсюда следует, что решение задачи поиска данным методом во многом зависит от используемой хеш-функции. Предложено довольно много различных хеш-функций. Самой простой, но не самой лучшей хеш-функцией является функция взятия остатка от деления ключа нацело на m:

h (аi ) = (аi mod m) + 1;

Ясно, что каждое значение этой функции лежит в пределах от 1 до m и может приниматься в качестве индекса ячейки массива.

Принято считать, что хорошей является хеш-функция, которая удовлетворяет следующим условиям:

· функция должна быть очень простой с вычислительной точки зрения

· функция должна распределять ключи в хеш-таблице как можно более равномерно

Использование данного метода включает два этапа:

· построение хеш-таблицы для заданного набора ключей с помощью выбранной хеш-функции, т.е. определение для каждого ключа его местоположения в таблице

· использование построенной таблицы для поиска элементов с помощью той же самой хеш-функции

Рассмотрим два примера с целыми и строковыми ключами.

Пример 1. Пусть задан набор из 8 целочисленных ключей:

35, 19, 07, 14, 26, 40, 51,72.

Требуется распределить эти ключи в массиве из 10 ячеек с помощью простейшей хеш-функции.

Для этого каждый ключ делим нацело на 10 и используем остаток в качестве индекса размещения ключа в массиве:

35 mod 10 = 5, индекс размещения ключа 35 равен 6

19 mod 10 = 9, индекс размещения ключа 19 равен 10

07 mod 10 = 7, индекс размещения ключа 07 равен 8

14 mod 10 = 4, индекс размещения ключа 14 равен 5

26 mod 10 = 6, индекс размещения ключа 26 равен 7

40 mod 10 = 0, индекс размещения ключа 40 равен 1

51 mod 10 = 1, индекс размещения ключа 51 равен 2

72 mod 10 = 2, индекс размещения ключа 72 равен 3

Получаем следующую хеш-таблицу:

индекс	1	2	3	4	5	6	7	8	9	10
ключ	40	51	72		14	35	26	07		19

Если требуется найти в этой хеш-таблице ключ со значением 26, то этот поиск выполняется ровно за одно сравнение: делим 26 на 10, берем остаток 6, входим в ячейку с индексом 7 и сравниваем находящееся там значение с заданным ключом.

Пример 2. Пусть ключи являются строковыми. В этом случае предварительно текстовый ключ надо преобразовать в числовой. Например, можно сложить ASCII-коды всех символов, входящих в этот текстовый ключ.

Например, если строковый ключ имеет значение END, то его целочисленный эквивалент будет равен сумме кодов всех трех символов:

ord(E) + ord(N) + ord(D) = 69 + 78 + 68 = 215

Тогда для четырех строковых ключей, являющихся служебными словами языка Паскаль, получим следующие значения простейшей хеш-функции, определяющие размещение этих ключей в десятиэлементной хеш-таблице:

h (END) = (215 mod 10) + 1 = 6

h (VAR) = (233 mod 10) + 1 = 4

h (AND) = (211 mod 10) + 1 = 2

h (NIL) = (227 mod 10) + 1 = 8

В результате для этих четырех строковых ключей получаем следующую хеш-таблицу:

индекс	1	2	3	4	5	6	7	8	9	10
ключ		AND		VAR		END		NIL

Поиск в этой таблице некоторого ключа выполняется очень просто: находится целочисленный эквивалент строкового ключа, вычисляется значение хеш-функции и сравнивается содержимое полученной ячейки с заданным ключом. Например, h (VAR) = 4, сравниваем содержимое ячейки 4 с ключом VAR, фиксируем совпадение и завершаем поиск с признаком успеха.

Приведенные выше примеры носят несколько искусственный характер, поскольку они описывают идеальный случай, когда хеш-функция для всех различных ключей дает РАЗЛИЧНЫЕ значения индексов в массиве. В этом случае каждый ключ имеет свое уникальное расположение в массиве, не конфликтуя с другими ключами. Подобная ситуация возможна, если исходный набор ключей известен заранее и после построения хеш-таблицы не изменяется, т.е. ключи НЕ добавляются и НЕ удаляются из хеш-таблицы. В этом случае за счет подбора хеш-функции и, возможно, небольшого изменения самих ключей можно построить бесконфликтную хеш-таблицу. Важным практическим примером такой ситуации является построение таблицы ключевых слов в программах-трансляторах с языков программирования.

Здесь набор ключевых слов является постоянным, изменяясь только при изменении версии транслятора, а с другой стороны, обработка транслятором входного текста на языке программирования требует многократного и очень быстрого распознавания в этом тексте ключевых слов языка.

К сожалению, идеальный случай возможен весьма редко, и ограничивать применение хеш-поиска только данным случаем было бы неразумно, учитывая выдающиеся потенциальные скоростные возможности метода.

Поэтому были предложены различные усовершенствования хеш-поиска, существенно расширившие область его использования.

Эти усовершенствования так или иначе связаны с обработкой конфликтных ситуаций, когда два РАЗНЫХ ключа претендуют на ОДНО и то же место в хеш-таблице, т.е. хеш-функция дает для этих разных ключей аi и ак одно и то же значение:

h (аi ) = h (ак ) = j

Например, в приведенном выше примере со строковыми ключами простая перестановка символов в ключе приводит к конфликту:

h (VAR) = h (RAV) = h (AVR) = (233 mod 10) + 1 = 4

Для разрешения конфликтов были предложены разные методы, которые можно сгруппировать в две основные группы - открытое хеширование и внутреннее хеширование (необходимо отметить, что данная терминология не является общепринятой и допускает разночтения, поэтому в первую очередь надо обращать внимание на сущность метода разрешения конфликтов).

4.2 Разрешение конфликтов: открытое хеширование

Пусть имеется n элементов а1, а2, а3, . . ., аn , на основе которых требуется построить хеш-таблицу, причем некоторые ключи могут конфликтовать между собой, претендуя на одну и ту же ячейку таблицы. Идея открытого хеширования совершенно прозрачна: связать все элементы с одним и тем же значением хеш-функции во вспомогательный линейный список. Данный метод иногда называют методом цепочек.

Обращаю внимание, что мы еще раз приходим к необходимости использования комбинированной структуры данных - массива указателей. Хеш-таблица как массив записей должна хранить не только ключи элементов, но и по два указателя на начало и конец вспомогательного списка.

Алгоритм построения хеш-таблицы:

· находим значение хеш-функции для очередного ключа и по этому значению как индексу входим в таблицу

· если данная клетка таблицы пустая, то записываем в нее соответствующий ключ

· если ячейка занята, то сравниваем хранящийся там ключ с заданным ключом:

o если ключи совпадают, то каким-то образом обрабатываем повторный ключ (например, просто ничего не выполняем)

o если ключи не совпадают, то добавляем новый ключ в конец списка

Алгоритм поиска в построенной таблице:

· находим значение хеш-функции для искомого ключа и по этому значению как индексу входим в таблицу

· если ячейка с найденным индексом пустая, то поиск заканчивается неудачей

· если ячейка не пустая, то выполняем сравнение ключей:

o если ключи совпадают, то поиск заканчивается за одно сравнение

o если ключи не совпадают, то организуем просмотр линейного вспомогательного списка с положительным или отрицательным результатом

Пример. Задано 10 целочисленных ключей, на основе которых надо построить хеш-таблицу размерности 5, используя для разрешения конфликтов метод открытого хеширования. Поскольку число исходных элементов n=10 больше размерности таблицы (m=5), то без использования вспомогательных списков таблицу построить нельзя.

Набор входных ключей с соответствующими значениями хеш-функции приведены в следующей таблице (использована простейшая хеш-функция):

ключ	33	17	09	04	22	19	42	53	64	25
значение хеш-функции	4	3	5	5	3	5	3	4	5	1

Тогда хеш-таблица будет иметь следующий вид:

Подсчитаем для данного примера среднее число сравнений, которые необходимо сделать для поиска любого из 10 исходных ключей:

· ключ 33 - одно сравнение, т.к. он непосредственно находится в ячейке таблицы

· ключи 17 и 09 - тоже по одному сравнению

· ключ 04 - два сравнения (в ячейке 5 находится ключ 09, идем по списку, совпадение на первом элементе)

· ключ 22 - 2 сравнения

· ключи 19 и 42 - по 3 сравнения (вторые элементы в списках)

· ключ 53 - 2 сравнения

· ключ 64 - 4 сравнения

· ключ 25 - 1 сравнение

Итого - 20 сравнений, т.е. в среднем 2 сравнения на один ключ.

Из примера видно, что для данного метода большое значение имеет равномерность распределения ключей по хеш-таблице, что гарантирует короткие вспомогательные списки и тем самым уменьшает число сравнений при поиске. Наихудшим является случай, когда для всех ключей хеш-функция дает одно и тоже значение, и все элементы выстраиваются в один длинный линейный список.

Другим фактором, влияющим на эффективность открытого хеширования, является размер хеш-таблицы по отношению к числу входных данных. Если эти величины равны, то теоретически можно обойтись без линейных списков, если между ключами нет конфликтов. На практике рекомендуют выбирать размер хеш-таблицы равным n/2.

4.3 Разрешение конфликтов: внутреннее хеширование

Пусть имеется n элементов а1, а2, а3, . . ., аn , на основе которых требуется построить хеш-таблицу, причем некоторые ключи могут конфликтовать между собой, претендуя на одну и ту же ячейку таблицы. Внутреннее хеширование для размещения конфликтующих ключей использует не вспомогательные списки, а свободные ячейки хеш-таблицы. Для этого размер таблицы обязательно должен быть больше числа элементов (m>n).

Если при построении хеш-таблицы для очередного ключа хеш-функция определяет некоторую ячейку j, и эта ячейка оказывается занятой другим ключом, то предпринимается попытка найти в таблице свободную ячейку для размещения конфликтующего ключа. Если хотя бы одна свободная ячейка в таблице есть, то в ней и размещается конфликтующий ключ, в противном случае добавление считается невозможным.

Существуют различные правила поиска свободных мест для конфликтующих ключей. Необходимо подчеркнуть, что правило выбора свободной ячейки должно быть одним и тем же как при построении таблицы, так и при использовании ее для поиска.

Самое простое правило заключается в последовательном круговом просмотре всех ячеек, начиная с индекса j, т. е. ячеек с номерами j+1, j+2, …, m-1, m, 1, 2, …, j-1.

Пример. Пусть задано 6 целочисленных ключей 15, 17, 19, 35, 05, 28. Построим на их основе хеш-таблицу размерности 10 с помощью простейшего правила определения свободных ячеек.

h (15) = 6, размещаем ключ 15 в ячейке 6

h (17) = 8, размещаем ключ 17 в ячейке 8

h (19) = 10, размещаем ключ 19 в ячейке 10

h (35) = 6, но ячейка 6 уже занята, проверяем следующую: ячейка 7 свободна, размещаем ключ 35 в ячейке 7

h (05) = 6, ячейка 6 занята, следующая ячейка 7 тоже занята, ячейка 8 - тоже, поэтому размещаем ключ 05 в ячейке 9

h (28) = 9, ячейка 9 занята, ячейка 10 занята и является последней, проверяем ячейку 1 и размещаем ключ 28 именно в ней.

Получим следующую хеш-таблицу:

индекс	1	2	3	4	5	6	7	8	9	10
ключ	28 (h=9)					15 (h=6)	35 (h=6)	17 (h=8)	05 (h=6)	19 (h=10)

Для поиска любого из шести ключей в этой таблице потребуется в среднем (1+2+1+4+1+6 = 15)/6 = 2,5 сравнений.

Для циклического вычисления индекса ключа аk в простейшем случае можно использовать следующую простую формулу:

j = (h(аk) + i) mod m) + 1, где i = 0, 1, 2, …, m-2

Здесь для целочисленных ключей h(аk) = аk.

Недостатком простейшей формулы определения свободных ячеек является эффект "кучкования" ключей с одинаковыми значениями хеш-функции: эти ключи размещаются в соседних свободных ячейках, тогда как "хорошее" правило должно распределять эти ключи равномерно по таблице.

Поэтому более эффективным является правило, которое позволяет выполнять "перепрыгивание" через несколько соседних ячеек. Например, можно воспользоваться следующей функцией вычисления индексов размещения ключей:

j = ((h (аk) + i2) mod m) + 1, где i = 0, 1, 2, …, m-2

Эта функция дает не постоянный шаг приращения индекса (+1), а переменный: +1, +4, +9, +16 и т.д.

Алгоритм построения хеш-таблицы:

· находим значение хеш-функции для очередного ключа и по этому значению как индексу входим в таблицу

· если данная клетка таблицы пустая, то записываем в нее соответствующий ключ

· если ячейка занята, то сравниваем хранящийся там ключ с заданным ключом:

o если ключи совпадают, то каким-то образом обрабатываем повторный ключ (например, просто ничего не выполняем)

o если ключи не совпадают, то с помощью выбранного правила организуем циклический поиск свободной ячейки, который завершается либо при обнаружении свободной ячейки, либо по достижению конца цикла, что говорит об отсутствии в таблице свободных ячеек и невозможности добавления нового ключа

Алгоритм поиска:

· находим значение хеш-функции для искомого ключа и по этому значению как индексу входим в таблицу

· если ячейка с найденным индексом пустая, то поиск заканчивается неудачей

· если ячейка не пустая, то выполняем сравнение ключей:

o если ключи совпадают, то поиск заканчивается за одно сравнение

o если ключи не совпадают, то с помощью выбранного правила организуем циклический просмотр ячеек, который завершается либо при обнаружении свободной ячейки (поиск неудачен), либо по совпадению ключей (поиск удачен)

Эффективность внутреннего хеширования существенно зависит от наличия в хеш-таблице пустых ячеек, поэтому на практике идут на искусственное увеличение размерности таблицы на. 10-20% для обеспечения достаточного количества свободных клеток.

Многочисленные эксперименты показывают, что для заполненной на 50% таблицы (половина ячеек пустые) для поиска любого ключа в среднем требуется лишь 1,5 сравнения, причем это число не зависит от количества элементов. Это еще раз подтверждает высочайшую эффективность хеш-поиска!

В заключение дадим общие рекомендации по применению хеш-поиска.

1. Наиболее целесообразно использовать данный метод для постоянного и не меняющегося набора ключей, т.к. в этом случае за счет подбора хеш-функции и самих ключей можно построить бесконфликтную таблицу и достичь максимально возможной скорости поиска - ровно 1 сравнение для любого ключа независимо от их количества

2. Если набор ключей может меняться и заранее неизвестен, то важным становится выбор хеш-функции для равномерного распределения ключей по таблице. Одной из лучших хеш-функций считается следующая: исходный целочисленный ключ возводится в квадрат, преобразуется в двоичное представление в виде набора битов и из середины этого набора извлекается необходимое число битов в соответствии с размерностью таблицы (например, для таблицы размерности 1024 необходимо извлечь 10 битов)

3. При использовании открытого хеширования рекомендуется размер таблицы выбирать равным n/2, что в среднем должно обеспечивать короткие вспомогательные списки (1-2 элемента), которые могут просматриваться только последовательно

4. При использовании внутреннего хеширования рекомендуется размер таблицы выбирать равным 1,2*n для обеспечения достаточного количества свободных ячеек.

5. В обоих случаях, если в процессе использования хеш-поиска происходит добавление в таблицу новых элементов и из-за этого нарушаются приведенные выше рекомендации, целесообразно выполнить реструктуризацию хеш-таблицы, добавив в базовый массив необходимое число ячеек

6. Некоторые сложности возникают при удалении элементов из хеш-таблицы, особенно - при использовании внутреннего хеширования, т.к. при этом за счет появления "незапланированных" пустых ячеек может нарушится работа алгоритма поиска

7. Ну и, наконец - ложка дегтя в бочке меда: метод совершенно непригоден для обработки упорядоченных наборов.

4.4 Практические задания

Задание 1. Построить бесконфликтную хеш-таблицу для заданного набора текстовых ключей. Число ключей (и размер таблицы) равен 10. В качестве ключей взять 10 любых служебных слов языка Паскаль. Для преобразования текстовых ключей в числовые значения использовать суммирование кодов символов текстового ключа: код (End) = код (E) + код (n) + код (d). Преобразование числового кода ключа в значение индекса выполнить с помощью простейшей хеш-функции, которая берет остаток от целочисленного деления кода на размер хеш-таблицы (в задании - 10).

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

Если некоторые исходные ключи будут конфликтовать друг с другом, можно изменить исходное слово, например - сменить регистр начальной буквы или всех букв в слове, полностью заменить слово на близкое по значению (End на Stop и.т.д.), ввести какие-либо спецсимволы или придумать другие способы

После подбора неконфликтующих ключей написать основную программу, которая должна:

· ввести подобранные ключи и расположить их в ячейках хеш-таблицы в соответствии со значением хеш-функции

· вывести хеш-таблицу на экран

· организовать циклический поиск разных ключей, как имеющихся в таблице (с выводом местоположения), так и отсутствующих: вычислить для ключа значение хеш-функции и сравнить содержимое соответствующей ячейки таблицы с исходным ключом

Задание 2. Реализовать метод внутреннего хеширования. Исходные ключи - любые слова (например - фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция - такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле

j = (( h (ключ) + i ) mod m ) + 1, где i = 0, 1, 2, . . . , m-2

Программа должна выполнять следующие действия:

· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений

· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений

· вывод текущего состояния таблицы на экран

После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 10 ключей и разместить их поочередно в таблице размерности 11, 13 и 17. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии количества пустых мест в таблице на эффективность поиска.

Задание 3. Реализовать метод открытого хеширования. Исходные ключи - любые слова (например - фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция - такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух указателей на начало и конец вспомогательного списка.

Программа должна выполнять следующие действия:

· добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений

· поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений

· вывод текущего состояния таблицы на экран

· удаление заданного ключа из таблицы

Алгоритм удаления:

· вычислить хеш-функцию и организовать поиск удаляемого элемента в таблице

· если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее записывается значение из первого элемента списка с соответствующим изменением указателей

· если удаляемый элемент найден в списке, то производится его удаление с изменением указателей

После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23.

Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска.

Сделать вывод о влиянии размерности таблицы на эффективность поиска.

Контрольные вопросы по теме

1. В чем заключается метод хеш-поиска?

2. Для чего используется хеш-функция и какие к ней предъявляются требования?

3. Что такое хеш-таблица и как она используется?

4. Как по трудоемкости соотносятся между собой основные методы поиска (полный перебор, двоичный поиск, хеш-поиск)?

5. Как с помощью простейшей хеш-функции находится расположение в таблице строковых ключей?

6. Какие проблемы могут возникать при построении хеш-таблиц с произвольными наборами ключей?

7. В каких ситуациях можно построить бесконфликтную хеш-таблицу?

8. Где на практике и почему можно использовать бесконфликтные хеш-таблицы?

9. Что такое открытое хеширование и для чего оно применяется?

10. Какие структуры данных используются для реализации открытого хеширования?

11. Какие шаги выполняет алгоритм построения хеш-таблицы при открытом хешировании?

12. Какие шаги выполняет алгоритм поиска в хеш-таблице при открытом хешировании?

13. Какие проблемы могут возникать при использовании открытого хеширования?

14. Как влияет размер хеш-таблицы на эффективность открытого хеширования?

15. Что такое внутреннее хеширование и для чего оно применяется?

16. Какие правила можно использовать для поиска свободных ячеек при внутреннем хешировании?

17. Какие шаги выполняет алгоритм построения хеш-таблицы при внутреннем хешировании?

18. Какие шаги выполняет алгоритм поиска в хеш-таблице при внутреннем хешировании?

19. Как влияет размер хеш-таблицы на эффективность внутреннего хеширования?

20. В каких задачах НЕ следует применять метод хеш-поиска?

Тема 5. Внешний поиск и внешняя сортировка

5.1 Особенности обработки больших наборов данных

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

Решение подобных задач неизбежно связано с учетом особенностей взаимодействия ОП и внешней памяти. Главное их отличие - время доступа. Поскольку доступ к внешней памяти выполняется значительно медленнее, то главным критерием при разработке алгоритмов становится не количество элементарных операций с расположенными в ОП данными, а число обращений к внешней памяти. Методы внешнего поиска и сортировки должны быть такими, чтобы время обращения к внешней памяти было как можно меньше.

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

На этих принципах построен ряд методов внешнего поиска и сортировки. Среди них одним из наиболее известных методов поиска является метод Б-деревьев (B-tree).

5.2 Организация внешнего поиска с помощью Б-деревьев

Данный метод использует понятие двоичного дерева поиска, но модифицирует это понятие таким образом, что дерево получает страничную организацию. Поэтому Б-деревья часто называют деревьями со страничной организацией.

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

В качестве примера рассмотрим обычное дерево поиска из 15 вершин. Пусть для простоты оно является идеально сбалансированным. Выделим в нем 5 элементарных поддеревьев по 3 вершины в каждом и логически объединим эти вершины вместе в виде страниц. Если в дереве необходимо найти какую-либо терминальную вершину, и вершины считываются в ОП по одной, то для этого в обычном дереве потребуется 4 обращения к внешней памяти. А в дереве со страничной организацией потребуется считать из внешней памяти лишь 2 страницы - корневую и одну из терминальных. Даже в этом простейшем примере страничная организация дерева позволяет уменьшить число обращений к диску в два раза. Для сверхбольших деревьев этот эффект становится еще более заметным.

Для эффективной страничной организации сверхбольшого дерева поиска очень важным условием является равномерность его роста, максимальное соответствие идеальной сбалансированности. К сожалению, условие идеальной сбалансированности приводит к очень сложным алгоритмам, поэтому Байером и было введено понятие дерева со страничной организацией (Б-дерево).

Б-дерево порядка m со страничной организацией - это структура данных, удовлетворяющая следующим условиям:

· весь набор из n элементов разбивается на отдельные страницы, причем каждая страница может содержать от m до 2m вершин, за исключением корневой страницы, для которой число вершин может изменяться от 1 до 2m

· каждая страница является либо терминальной (потомков нет), либо имеет ровно на одного потомка больше по сравнению с текущим числом вершин на этой странице

· все терминальные страницы находятся на одном уровне

Пример. Рассмотрим простейшее Б-дерево порядка m=2 с ключами целого типа. В соответствии с приведенными выше правилами, каждая страница такого дерева содержит от 2 до 4 вершин, а корневая - от 1 до 4. Каждая нетерминальная страница может иметь от 3 до 5 потомков. Пример дерева - на рисунке (к сожалению, терминальные страницы приходится располагать на разных уровнях).

Поскольку Б-дерево является обобщением классического дерева поиска, то оно обладает следующими свойствами:

· на каждой странице элементы упорядочены по возрастанию ключей

· каждая страница-потомок содержит ключи в строго определенном диапазоне, который задается родительскими ключами

Последнее свойство является обобщением основного правила дерева поиска. Например, страница с ключами 40, 50 и 60 имеет четырех потомков, причем самый левый потомок содержит ключи меньше 40 (но больше 30), более правая страница содержит ключи в диапазоне от 40 до 50, еще более правая - в диапазоне от 50 до 60, а самая правая - больше 60.

Эффективность использования Б-дерева для поиска ключей в сверхбольших наборах данных можно оценить следующим образом.. Если Б-дерево имеет порядок m, а число элементов - n, то самым наихудшим случаем будет случай, когда на каждой странице находится минимально возможное число элементов, а именно - m. В этом случае высота Б-дерева определяется величиной logmn, а именно высота и определяет количество обращений к внешней памяти.

Например, если число элементов в наборе данных n = 1 миллион, а порядок Б-дерева m = 100, то log1001000000 = 3, т.е. максимум может потребоваться 3 обращения к внешней памяти. С другой стороны, даже в этом наихудшем случае оперативная память используется достаточно эффективно (примерно половина памяти от заявленного объема).

5.3 Б-дерево как структура данных

Базовым элементом Б-дерева является страница, поскольку именно она содержит всю основную информацию. Поэтому, прежде всего, необходимо описать структуру страницы Б-дерева.

Каждая страница должна содержать следующие данные:

· текущее количество элементов на странице (оно изменяется от m до 2m)

· указатель на страницу, являющуюся самым левым потомком данной страницы

· основной массив элементов страницы, размерность массива 2m, каждый элемент - это запись со следующими полями:

o ключ некоторого типа

o указатель на страницу, являющуюся потомком текущей страницы и содержащую ключи, большие ключа данного элемента

o информационная часть (как некоторая структура или указатель на область памяти)

Соответствующие описания типов можно сделать следующим образом:

type pPage = ^Page;{ссылочный тип для адресации страниц}

TItem = record{описание структуры элемента массива}

key : integer;{ключ вершины дерева}

cPage : pPage;{указатель на страницу-потомка}

inf : <описание информационной части>;

end;

Page = record{описание структуры страницы}

nPage : word;{число вершин на странице}

leftPage : pPage;{указатель на самого левого потомка}

mas : array [1 . . 2m] of TItem;{основной массив}

end;

Из переменных достаточно ввести два указателя: на корневую страницу (pRoot) и текущую обрабатываемую в данный момент страницу (pCurrent).

Схематично структуру страницы можно представить следующим образом (для краткости указатель pCurrent заменен идентификатором pC):

Видно, что Б-дерево является достаточно сложной комбинированной структурой, представляя собой набор связанных указателями записей. Для использования Б-дерева необходим стандартный набор операций: поиск заданного элемента, добавление вершины, удаление вершины.

5.4 Поиск элемента в Б-дереве

Пусть имеется Б-дерево порядка m, в котором требуется найти вершину с ключом x. Алгоритм поиска:

· считываем в ОП корневую страницу и организуем на этой странице поиск заданного элемента; если порядок Б-дерева небольшой, то можно применить обычный поиск прямым перебором; для деревьев большого порядка можно использовать метод двоичного поиска в упорядоченном массиве

· если заданный элемент на корневой странице найден, то обрабатываем его и завершаем поиск

· если заданного элемента на корневой странице нет, то возможно появление одной из трех следующих ситуаций:

Ш искомый элемент меньше самого левого ключа (x<pRoot^.mas[1].key); в этом случае поиск надо продолжить на странице, определяемой самой левой ссылкой (pRoot^.leftPage), для чего в ОП загружается вторая страница и поиск на ней повторяется описанным выше образом

Ш искомый элемент находится между двумя элементами (pRoot^.mas[j].key < x < pRoot^.mas[j+1].key); в этом случае поиск надо продолжить на странице, которая определяется ссылкой pRoot^.mas[j].cPage

Ш искомый элемент больше самого правого элемента (x > pRoot^.mas[nPage].key); поиск продолжаем на странице, определяемой ссылкой в последнем элементе массива (pRoot^.mas[nPage].cPage)

Если при этом какая-либо ссылка на страницу оказывается пустой, то это является признаком того, что искомого элемента в Б-дереве нет.

Для ускорения обработки Б-деревьев рекомендуется корневую страницу постоянно держать в ОП. Поскольку одновременно в ОП может находиться несколько страниц, то это накладывает ограничения на размер страницы и на порядок Б-дерева.

Как обычно, поиск можно реализовать как рекурсивно, так и итеративно (с помощью цикла). Программная реализация приводится как составляющая процедуры добавления новой вершины в Б-дерево.

Например, для рассмотренного выше Б-дерева поиск элемента с ключом 43 будет выполнен следующим образом:

· заходим на корневую страницу и устанавливаем, что ключ 43 больше всех ключей на корневой странице

· загружаем в ОП новую страницу, определяемую самой правой ссылкой на корневой странице

· организуем поиск ключа 43 среди элементов новой страницы (40, 50, 60) и фиксируем ситуацию расположения ключа 43 между ключами 40 и 50

· загружаем в ОП третью страницу, определяемую ссылкой у элемента 40 и организуем ее просмотр

· на этой странице (41, 42, 43, 44) находим искомый элемент

Наоборот, поиск ключа 45 приведет на последнем шаге к необходимости перехода на страницу, являющуюся самым правым потомком третьей страницы, но соответствующая ссылка является пустой и поиск заканчивается неудачно.

5.5 Добавление вершины в Б-дерево

Пусть имеется Б-дерево порядка m, в которое требуется добавить новый элемент с ключом х. Как обычно, прежде всего организуется поиск элемента с этим ключом.

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

При этом возможны следующие две ситуации:

· текущая страница, в которую должен быть вставлен новый элемент, заполнена не полностью (pCurrent^.nPage < 2m); в этом случае новый элемент просто вставляется в данную страницу в нужное место, с увеличением счетчика числа элементов на странице

· пусть текущая страница заполнена полностью, т.е. pCurrent^.nPage = 2m; добавление элемента на полностью заполненную страницу реализуется за счет разделения этой страницы на две страницы; создается новая страница, и после этого старая и новые страницы заполняются равномерно:

Ш левые m элементов передаются на новую страницу

Ш правые m элементов остаются на старой странице

Ш центральный (серединный) элемент передается наверх на родительскую страницу

При этом вытолкнутый наверх элемент вставляется на родительской странице в нужное место, если для этого есть свободное место. В противном случае, происходит расщепление родительской страницы на две, с выталкиванием центрального элемента еще выше и т.д. Такой процесс расщепления и выталкивания может дойти до корневой страницы. Если корневая страница заполнена полностью, то она расщепляется на две, с выталкиванием центрального элемента наверх, т.е. создается новая корневая страница, которая будет содержать единственный вытолкнутый снизу элемент. В этом случае высота Б-дерева увеличивается на 1.

Пример. Пусть в Б-дерево порядка 2 надо добавить вершину с ключом х = 32

Страница, на которую надо добавить ключ 32, заполнена полностью, поэтому создается новая страница с элементами 32 и 35, на старой остаются ключи 42 и 46, а элемент 40 выталкивается на родительскую страницу, занимая в ней крайнее правое место.

Такой алгоритм добавления сохраняет структуру Б-дерева, т.к. синхронно на 1 увеличивается число элементов на родительской странице и число ее страниц-потомков.

Если в данном примере добавить еще элементы 36 и 38, то при попытке добавления элемента 33 опять придем к необходимости расщепления страницы:

Поскольку корневая страница заполнена полностью, происходит ее расщепление на две страницы, выталкивание наверх элемента 30 и создание новой корневой страницы.

Рассмотрим вопрос программной реализации алгоритма добавления. Поскольку добавление элемента на терминальной странице может привести к необходимости добавления и на ее родительской странице, а там, в свою очередь - на своей родительской странице и т.д., вплоть до корневой, в процессе поиска надо запоминать пройденный путь, т.е. пройденные на каждой странице точки разветвления. Как обычно, подобное запоминание можно реализовать либо неявно с помощью механизма рекурсии, либо явно с помощью стековой структуры.

Для рекурсивной реализации надо ввести подпрограмму Add, которая должна использовать три параметра:

· адрес новой текущей страницы, используемый как в процессе движения от корневой страницы к терминальной, так и обратно; поскольку этот адрес автоматически должен запоминаться и восстанавливаться, ссылочный параметр надо объявить как параметр-значение

· выходной логический параметр, который определяет факт расщепления текущей страницы и, следовательно, необходимость добавления выталкиваемого элемента на родительскую страницу

· выходной параметр-переменная, через который на родительскую страницу передается сам выталкиваемый элемент.

Схематично подпрограмма Add описывается следующим образом

procedure Add ( pCurrent : pPage; var IsUp : boolean; var Item : TItem);

begin

if pCurrent = nil then {элемента в дереве нет}

begin

"формирование полей нового элемента Item";

IsUp := true;

end

else begin {продолжаем поиск на странице pCurrent}

"загрузка новой страницы";

"поиск на странице элемента с заданным ключом";

if "элемент найден" then "обработка элемента"

else begin

"определение адреса страницы для продолжения поиска";

Add ( "адрес страницы", IsUp, Item);

if IsUp then {добавить элемент на текущую страницу }

if pCurrent^.nPage < 2m then

begin

pCurrent^.nPage := pCurrent^.nPage + 1;

IsUp := false;

"добавление элемента Item в страничный массив"

end

else begin

"создание новой страницы";

"формирование полей новой страницы";

"корректировка полей старой страницы";

"формирование выталкиваемого наверх элемента"

end;

end;

end;

end;

Как обычно, начальный вызов подпрограммы Add выполняется из главной программы, причем после возврата обратно в главную программу, возможно, придется создавать новую корневую страницу:

begin

Add (pRoot, IsUp, Item);

if IsUp then

begin

pTemp := pRoot; New(pRoot);

pRoot^.nPage := 1; pRoot^.LeftPage := pTemp;

pRoot^.mas[1] := Item;

end;

end;

5.6 Удаление вершины из Б-дерева

Пусть имеется Б-дерево порядка m, из которого требуется удалить элемент с ключом х. Прежде всего, организуется поиск удаляемого элемента последовательным просмотром страниц, начиная с корневой. Пусть удаляемый элемент найден на некоторой странице. При этом возможны следующие две ситуации:

· если найденная страница является терминальной, то элемент просто удаляется с нее с последующей проверкой количества оставшихся на этой странице элементов; если после удаления на странице остается слишком мало элементов, предпринимаются некоторые дополнительные действия, описываемые немного позже

· если страница нетерминальная, то на место удаляемого элемента надо поставить элемент-заменитель, который находится также, как и в обычном дереве: входим в левое (правое) поддерево и спускаемся как можно ниже, придерживаясь максимально правых (левых) поддеревьев; после этого надо проверить страницу, с которой был взят элемент-заменитель и при необходимости предпринять корректирующие действия для восстановления структуры Б-дерева

Например, пусть в простейшем Б-дереве порядка 2 на рисунке ниже требуется удалить элемент с ключом х = 40. Левое поддерево для ключа 40 определяется ссылкой, связанной с его левым соседом, т.е. элементом 20. Просматриваем новую страницу (26, 35), выбираем самый правый элемент 35 и по его ссылке выходим на страницу (36, 37, 38). На этой странице крайний правый элемент 38 не имеет потомка и поэтому именно он должен быть элементом-заменителем. Ясно, что он является ближайшим меньшим элементом по отношению к удаляемому. Путь к элементу-заменителю показан жирной линией.



В обоих случаях после удаления элемента с некоторой страницы надо эту страницу проверить на число оставшихся элементов. По правилам построения Б-деревьев на каждой странице (кроме корневой) не может быть меньше m элементов. Если это условие после удаления не выполняется, т.е. на странице остается лишь m-1 элемент, необходима ее корректировка за счет привлечения одной из соседних страниц. Для этого с помощью родительской страницы определяется адрес соседней страницы и выполняется ее загрузка в ОП. Совместная обработка двух соседних страниц выполняется следующим образом.

1. Если на соседней странице имеется более m элементов (хотя бы m+1), то выполняется перераспределение элементов: с более "богатой" соседней страницы некоторое число элементов передается на "бедную" текущую страницу. В простейшем случае достаточно передать один элемент, но на практике чаще всего передается столько элементов, чтобы на этих двух страницах их было почти поровну. Здесь есть один тонкий момент - элементы с одной страницы на другую передаются не прямо, а через родительскую страницу, т.е. происходит как бы перетекание элементов с дочерней страницы на родительскую с вытеснением с нее элементов на текущую страницу.

2. Если соседняя страница сама является "небогатой", т.е. содержит ровно m элементов, используется другой прием. В этом случае происходит объединение двух "бедных" страниц с созданием одной полной страницы. Полная страница создается следующим образом: m-1 элемент берется с текущей страницы, m - с соседней и один элемент - с родительской страницы. Интересно, что этот прием заимствования одного элемента с родительской страницы позволяет сохранить необходимую структуру Б-дерева, т.к. синхронно на 1 уменьшается число элементов на родительской странице и число страниц-потомков.

Поскольку число элементов на родительской странице уменьшилось, то надо и эту страницу проверить на "бедность", и, при необходимости, выполнить ее корректировку. Это, в свою очередь, может привести к заимствованию элемента с еще более верхней страницы и т.д. В худшем случае этот процесс распространится до корневой страницы, что может потребовать корректировки самой корневой страницы. Правда, эта корректировка выполняется чуть по-другому, т.к. корневая страница может содержать и меньше m элементов. Особенность возникает лишь тогда, когда до удаления на корневой странице был лишь один элемент, и после удаления она становится пустой. В этом случае эта пустая страница просто удаляется, и тем самым на 1 уменьшается высота Б-дерева.

Пример. Пусть в простейшем Б-дереве порядка 2 удаляется вершина 12 и страница становится "бедной". Соседняя страница (22, 25, 28) может отдать один элемент, и поэтому ключ 22 передается на родительскую страницу, вытесняя с нее ключ 20.

Если в этом дереве удалить, например, вершину 7, то придется объединять две страницы (5) и (10, 20) вместе и добавлять элемент 8 с родительской страницы для создания одной полной страницы.



Программная реализация удаления имеет те же особенности, что и добавление, т.е. необходимо запоминать траекторию движения от корневой странице к текущей. Для этого можно ввести рекурсивную подпрограмму Delete с тремя параметрами:

· x - ключ удаляемого элемента (параметр-значение)

· pCurrent - ссылка на текущую страницу (параметр-значение)

· IsPure - признак того, что текущая страница после удаления содержит слишком мало элементов (параметр-переменная).

Псевдокод подпрограммы Delete:

procedure Delete (x : <тип ключа>; pCurrent : pPage; var IsPure : boolean);

begin

if pCurrent = nil then "элемента x в дереве нет"

else begin

"поиск x на странице pCurrent";

if "x найден" then

begin

if "страница pCurrent^ терминальная"

then begin

"удалить элемент";

"уменьшить счетчик числа элементов";

"установить признак IsPure";

end

else begin

"найти элемент-заменитель";

"вставить элемент-заменитель на место удаленного x";

"уменьшить счетчик числа элементов";

"установить признак IsPure";

end

end

else begin

Delete (x, "адрес дочерней страницы", IsPure);

if IsPure then "вызов вспом. подпрограммы Pager( )";

end;

end;

end;

Здесь используется вспомогательная подпрограмма Pager, выполняющая корректировку страницы после удаления с нее элемента x в случае ее "обеднения". Эта подпрограмма имеет 4 параметра:

· адрес текущей "бедной" страницы (pCurrent)

· адрес родительской страницы (pParent)

· номер элемента на родительской странице, который является непосредственным предком "бедной" страницы (nParent)

· логический признак (IsPure)

Псевдокод подпрограммы Pager:

procedure Pager (pCurrent, pParent : pPage; nParent : integer; var IsPure : boolean);

var pTemp : pPage; {адрес соседней страницы}

begin

"определение адреса pTemp соседней вершины";

"определение числа элементов, удаляемых с соседней страницы";

"пересылка одного элемента с родительской страницы на текущую";

if "со страницы pTemp пересылается более одного элемента" then

begin

"пересылка элементов со страницы pTemp на pCurrent";

"пересылка одного элемента на родительскую страницу";

"сдвиг влево элементов в массиве на странице pTemp";

"установка счетчиков числа элементов на соседних страницах";

IsPure := false;

end

else begin {объединение страниц}

"пересылка всех эл-тов со страницы pTemp на страницу pCurrent";

"сдвиг влево элементов в массиве на родительской странице";

"изменение счетчиков числа эл-тов на тек. странице и ее родителе";

"удаление пустой страницы pTemp";

"установка признака IsPure для родительской страницы";

end;

end;

Главная программа должна вызвать подпрограмму Delete, а после возврата из цепочки рекурсивных вызовов - удалить опустевшую корневую страницу.

5.7 Внешняя сортировка

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

Основой большинства алгоритмов внешней сортировки является принцип слияния двух упорядоченных последовательностей в единый упорядоченный набор.

Например, пусть имеются две упорядоченные числовые последовательности: (5, 11, 17) и (8, 9, 19, 25)

Их слияние выполняется следующим образом:

· сравниваются первые числа 5 и 8, наименьшее (5) помещается в выходной набор: (5)

· сравниваются 11 и 8, наименьшее (8) - в выходной набор: (5, 8)

· сравниваются 11 и 9, наименьшее (9) - в выходной набор: (5, 8, 9)

· сравниваются 11 и 19, наименьшее (11) - в выходной набор: (5, 8, 9, 11)

· сравниваются 17 и 19, наименьшее (17) - в вых. набор: (5, 8, 9, 11, 17)