6. Таблицы с вычисляемыми входами
 
   6.1. Понятие таблицы с вычисляемыми входами
 

Метод двоичного поиска, как мы знаем, обеспечивает время поиска порядка O(log ₂ n), т.е. зависит от размера таблицы. Естественное стремление человека к экономии привело к разработке теории и практике применения таблиц с вычисляемыми входами . Любой элемент такой таблицы имеет свой адрес, известный (доступный) программе обработки таблицы. Время обращения к элементам таблицы с вычисляемыми входами не зависит или почти не зависит от размеров таблицы.

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

Зависимость между адресом записи в таблице А и ее ключом k называется функцией расстановки (адресной функцией) А =f(k). В зависимости от характера функции f методы вычисления адреса по ключу можно разделить на две группы:

а) методы, в которых функция расстановки реализует взаимно однозначное соот-ветствие между адресом А и ключом k;
б) методы перемешивания (хеширования, рандомизации), в которых для различ-ных ключей k ₁ ! = k ₂ функция расстановки может дать одно и то же значение, т.е. один и тот же адрес в таблице: f(k ₁ )=f(k ₂ ),k ₁ ! = k ₂ .

Такая ситуация носит название коллизии (конфликта), а ключи k ₁ и k ₂ являются синонимами функции f. Естественным является стремление к уменьшению числа коллизий. Выбор функции расстановки и нахождение способов разрешения коллизий во многом зависят от решаемой прикладной задачи и вызывают немало трудностей, однако это оправдывается конечным результатом - быстротой обработки таблицы.

Подбор функции расстановки f(k), обеспечивающей взаимную однозначность преобразования ключа записи в адрес ее хранения, в общем случае весьма затруднителен. Этот случай является идеальным, и таблица с вычисляемым входом представляется в виде массива из N элементов T[i], i = 0, 1, ..., N - 1, где N — число возможных значений ключей, т.е. число элементов таблицы совпадает с числом возможных значений ключей. Предполагается, что функция расстановки f(k) ставит в соответствие всякому ключу k _j некоторое целое i, различное для разных k _j , и такое, что 0≤ i≤ N-l. Тогда элемент с ключом k _j достаточно разместить в T[i], и время поиска становится постоянным 0(1). Наиболее простым является случай, когда значение ключа к равно i или i + const.

Пример 1 . Имеется список студентов учебной группы, хранящийся в виде таблицы. Каждый студент имеет свой фиксированный порядковый номер i в списке (i = 1, 2, ..., N). Тогда доступ к данным i-го студента в таблице можно осуществлять по индексу записи в таблице T[i - 1]. Число элементов в таблице равно числу студентов в учебной группе. Здесь учитывается тот факт, что состав учебной группы остается неизменным. Таким образом, в рассмотренном примере ключом доступа является номер студента в списке, адресом входа в таблицу — индекс строки массива, функция расстановки А = f(k) = к - 1.
Пример 2 . Учет числа свободных мест в вагонах поездов. Пусть осуществляется продажа билетов за 30 дней до отправления поезда. Всего имеется 50 номеров поездов, каждый поезд имеет не более 15 вагонов. Таблица обновляется каждый день. Составим таблицу, в которой для каждого поезда Р (1 ...50) на каждый день отправления D (1...30) имеется одна запись со структурой: номер поезда, всего свободных мест — в вагоне 1, 2, ..., 15. Размер таблицы будет равен m = P*D записей. Ключом записи является пара значений Р и D, а функция расстановки будет иметь вид: f(P,D) = (Р- l)*30 + (D- 1).

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

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

С другой стороны, число реальных значений ключа m бывает значительно меньше числа возможных значений N: m « N. Тогда таблица заполняется лишь частично, т.е. коэффициент заполнения к = m/N <<1. Действительно, даже в простейшем случае, когда в качестве ключа использовался 8-битовый символ, число возможных значений N = 256, а число реальных ключей вряд ли превысит 100.

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

1) как лучше выбрать функцию расстановки f, чтобы уменьшить число коллизий;
2) где разместить конфликтные записи: внутри самого массива или вне его.