• Структуры данных для непересекающихся множеств (отношения эквивалентности). [4 гл.21]

Основные принципы организации таких структур данных и методов работы с ними были проиллюстрированы во введении (Пример 3 Связность).

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

• Вливание меньшего множества в большее. Это позволяет поддерживать приемлемую сбалансированность деревьев по их объему (а в результате и по длине путей).

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

4. Рандомизированные структуры данных.

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

• Хеш-таблицы. [4 гл.11; 3 гл.14; 7 п.4.7-8]

Хеш-таблица – это структура данных, предназначенная для хранения и поиска данных с ключом.

Пусть на входе последовательность длины n обрабатываемых данных (с ключами). Пусть хеш-функция h(k) по значению ключа k дает целое в интервале [0..m), причем статистически равномерно отображает ключи элементов входной последовательности в этот интервал. Представим хеш-таблицу вектором H[0..m) с элементами типа обрабатываемых данных и будем хранить данное с ключом k в H[h(k)]. Это откроет нам возможность прямого доступа к данным по ключу. Тогда:

• С одной стороны, при mn высока вероятность того, что каждому элементу входной последовательности найдется свое место в хеш-таблице.

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

• Пока в хеш-таблице не появились коллизии, работа с ней отличается от работы с массивом только вычислением хеш-функции, поэтому операции АТД «Словарь» (Вставить, Удалить, Найти элемент) выполняются за время O(1). Но при наличии коллизий основное время уходит на работу со структурой данных, использованной для разрешения коллизий, например, на работу со списками переполнения. Поэтому в общем случае для операции поиска время в худшем O(n). Однако в среднем размер списков переполнения равен n/m, и при n/m<C время в среднем для операций АТД «Словарь» получается O(1), конечно при условии, что хеш-функция действительно равномерно распределяет ключи по хеш-таблице. Это очень хорошо, если (редко) случающиеся задержки выполнения операций некритичны.

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