Открытая адресация с линейным перебором

Отображения.

Отображение — это функция, определенная на множестве элементов (области определения) одного типа (будем обозначать его domaintype — тип области определения функции) и принимающая значения из множества элементов (области значений) другого типа, этот тип обозначим rangetype — тип области значений (конечно, типы domaintype и rangetype могут совпадать). Тот факт, что отображение М ставит в соответствие элемент d типа domaintype из области определения элементу rтипа rangetype из области значений, будем записывать как M(d) = r.

Некоторые отображения, подобные square(i) = i², легко реализовать с помощью функций и арифметических выражений языка Pascal. Но для многих отображений нет очевидных способов реализации, кроме хранения для каждого d значения M(d).

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

Команды роботы с отображениями:

1. MAKENULL(M). Делает отображение М пустым.

2. ASSIGN(M, d, r). Делает M(d) равным r независимо от того, как M(d) было определено ранее.

3. COMPUTE(M, d, r). Возвращает значение true и присваивает переменной rзначение M(d), если последнее определено, и возвращает false в противном случае.

Во многих случаях тип элементов области определения отображения является простым типом, который можно использовать как тип индексов массивов. В языке Pascal типы индексов включают все конечные интервалы целых чисел, например 1..100 или 17..23, строковый тип, диапазоны символов, подобные 'A'...'Z", и нечисловые типы, например север, восток, юг, запад. В частности, в программах кодирования можно применить отображение crypt (шифратор) с множеством 'A'...'Z' и в качестве области определения, и в качестве области значений, так что сrур1(текст) будет кодом текста текст.

Такие отображения просто реализовать с помощью массивов, предполагая, что некоторые значения типа rangetype могут иметь статус "неопределен". Например, для отображения crypt, описанного выше, область значений можно определить иначе, чем 'A'...'Z и использовать символ '?' для обозначения "неопределен".

Тип MAPPING (Отображение) можно объявить следующим образом:

Type

MAPPING = array[domaintype] of rangetype;

 

Отображения с конечной областью определения можно представить в виде списка пар (d₁,r₁), (d₂, r₂),..., (dk, rk), где d1, d2 … dn - все текущие элементы области определения, a r1, r2,..., rk — значения, ассоциированные с rf; (t = 1, 2,..., k). Далее можно использовать любую реализацию списков.

Абстрактный тип данных MAPPING можно реализовать как список типа elementtype, если сделано объявление

Type

elementtype = record

domain: domain type

range: rangetype

End;

и затем объявлен тип MAPPING так, как мы ранее объявляли тип LIST (элементов типа elementtype), и в соответствии с той реализацией списков, которую мы выбрали.

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

1. Каково назначение отображения?

Назовите команды работы с отображениями.

3. Как реализовываются отображения?

 

Словари.

Применение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы объединения и пересечения. Часто достаточно только хранить в множестве "текущие" объекты с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве. Абстрактный тип множеств с операторами INSERT, DELETE и MEMBER называется DICTIONARY (Словарь).

Словари можно представить посредством сортированных или несортированных связанных списков.

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

1,..., N для некоторого N или элементы множества можно сопоставить с таким множеством целых чисел.

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

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

1. Каково назначение словарей?

2. Какие есть способы представления словарей?

Разрешение коллизий

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

Открытая адресация с линейным перебором

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

Проиллюстрируем линейный перебор на примере семи записей.

Предположим, что данные имеют тип DataRecord и хранятся в 11-элементной таблице.

struct DataRecord

{

int key;

int data;

};

В качестве хеш-функции HF используется остаток от деления на 11, принимающий значения в диапазоне 0-10.

HF(item) = item.key % 11

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

Список: {54,1}, {77,3}, {94,5}, {89,7}, {14,8}, {45,2}, {76,9}

Хеширование первых пяти ключей дает пять различных индексов, по которым эти ключи запоминаются в таблице. Например, HF({54,1}) = 10, и этот элемент попадает в Table[10]. Первая коллизия возникает между ключами 89 и 45, так как оба они отображаются в индекс 1.

Элемент данных {89,7} идет первым в списке и занимает позицию Table[1]. При попытке записать {45,2} оказывается, что место Table[1] уже занято. Тогда начинается последовательный перебор ячеек таблицы с целью нахождения свободного места. В данном случае это Table[2]. На ключе 76 эффективность алгоритма сильно падает. Этот ключ хешируется в индекс 10 – место, уже занятое. В процессе перебора осуществляется просмотр еще пяти ячеек, прежде чем будет найдено свободное место в Table[4]. Общее число проб для размещения в таблице всех элементов списка равно 13, т.е. в среднем 1,9 проб на элемент.

Метод цепочек

При другом подходе к хешированию таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Эта стратегия разрешения коллизий называется методом цепочек (chaining with separate lists).

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

Проиллюстрируем метод цепочек на семи записях типа DataRecord и хеш-функции HF.

Список: {54,1}, {77,3}, {94,5}, {89,7}, {14,8}, {45,2}, {76,9}

HF(item) = item.key % 11

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

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

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

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