Структуры данных, основанные на указателях, также, видимо, относятся к «фольклору». Согласно Кнуту, указатели использовались еще в первых компьютерах с магнитными барабанами. В 1951 году Хоппер (СМ. Hopper) разработал язык А-1, в котором алгебраические формулы представлялись в виде двоичных деревьев. Тот же Кнут указывает, что систематическое использование указателей началось с языка IPL-II, который разработали в 1956 году Ньюэлл, Шоу и Саймон (A. Newell, J.C.Shaw, H.A.Simon). В разработанном теми же авторами в 1957 году языке IPL-III появились в явном виде операции со стеками.

12Хеш-таблицы

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

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

Мы увидим, что хеширование - эффективный и удобный способ выполнять основные словарные операции (среднее время 0(1) при некоторых предположениях).

12.1. Прямая адресация

Прямая адресация применима, если количество возможных ключей невелико. Пусть возможными ключами являются числа из множества U = {0,1,..., то - 1} (число то не очень велико). Предположим также, что ключи всех элементов различны.

Для хранения множества мы пользуемся массивом Г[0 . .то - 1], называемым таблицей с прямой адресацией (direct-address table).

Переводы надписей на самой картинке: universe of keys - всевозможные ключи, actual keys - используемые ключи, key - ключ, satellite data - дополнительные данные.

Рис. 12.1 Реализация динамического множества с помощью таблицы Т с прямой адресацией. Множество возможных ключей есть U = {О, 1, . . . , 9}. Каждому из этих ключей соответствует своё место в таблице. В позициях таблицы с номерами 2, 3, 5 и 8 (фактически используемые ключи) записаны указатели на элементы множества, а в неиспользуемых позициях таблицы (тёмно-серые) записан nil.

Каждая позиция, или ячейка, (по-английски slot или position) соответствует определённому ключу из множества U (рис. 12.1: Т[к] - место, предназначенное для записи указателя на элемент с ключом к; если элемента с ключом к в таблице нет, то Т[к] = nil). Реализация словарных операций тривиальна:

Direct-Address-Search (Г, к) return Т[к]

Direct-Address-Insert (Г, ж) Т[&е?/[ж]] <- ж

Direct-Address-Delete (Г, ж) Т[&е?/[ж]] <- nil

Каждая из этих операций требует времени 0(1).

Иногда можно сэкономить место, записывая в таблицу Г не указатели на элементы множества, а сами эти элементы. Можно обойтись и без отдельного поля «ключ»: ключом служит индекс в массиве. Впрочем, если мы обходимся без ключей и указателей, то надо иметь способ указать, что данная позиция свободна.

Упражнения

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