Таблицы с вычисляемым адресом

Таблица с вычисляемым адресом (преобразованием ключа в адрес) представляет собой вектор из N ключей с индексами от 0 до N-1. Поиск элемента начинается с индекса i, вычисляемого из его ключа kl по формуле хеширования (hash - перемешать, мешанина):

i = H (kl) (5.9)

где H - функция расстановки (хеш-функция) с целочисленными значениями, удовлетворяющими условию

0 £ H(kl) £ N-1 (5.10)

В частном случае, когда разным ключам всегда соответствуют разные значения функции расстановки:

kl1 ¹ kl2 ==> H(kl1) ¹ H(kl2) (5.11)

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

kl1 ¹ kl2 && H(kl1) = H(kl2) (5.12)

Таблицы с прямым доступом

В таблице с прямым доступом индекс элемента определяется по формуле (5.9) только его ключом (ключи поэтому можно не хранить в таблице), длина поиска всегда 1:

D ^прям = 1 (5.13)

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

Пример 5.3. Таблица перекодировки символов

Ключ x - код символа (x = от 0 до 255), тело t[i] - новый код символа, количество элементов таблицы 256, индекс элемента – от 0 до 255.

Отсюда: функция расстановки: i = H(x) = x; новый код символа

x = t[i] = t[H(x)] = t[x]

/* Новые коды символов: 0, 1, ... , 255 */

char x, t[256] = { 45, 19, ... , 13 };

. . .

x = t[x]; /* Перекодировка символа x */

Пример 5.4. Таблица функции f(x) (x = 2, 2.01, ..., 2.99)

Ключ x - аргумент, тело элемента t[i] = f(x), количество элементов таблицы 100, индекс элемента 0..99.

Отсюда: функция расстановки: i = H(x) = 100*(x-2);

f(x) = t[i] = t[H(x)] = t[100*(x-2)].

/* Таблица функции f(x) (x = 2, 2.01, ... , 2.99): */

/* f(2), f(2.01), ..., f(2.99) */

float t[100] = { 3.51, 3.47, ..., -0.74 };

Перемешанные таблицы

Другие названия: рандомизированные таблицы (таблицы со случайным перемешиванием), рассеянные таблицы, хеш-таблицы.

Пример 5.5. Таблица с открытым перемешиванием (рис. 5.7)

Ключи - названия вузов; на рис. 5.7 а - значения функции расстановки; на рис. 5.7 б - поступающие ключи. Новый ключ помещается в позицию с индексом i = H(kl), а если она занята другим ключом (конфликт), то таблица просматривается циклически (i увеличивается на 1 по модулю N) до ключа, равного искомому, или до ближайшей свободной позиции (рис. 5.7 в). Обнаружение свободной позиции означает отсутствие в таблице поступившего ключа, и этот ключ можно поместить в найденную позицию.

а) Функция расстановки		б) Поступающие ключи: КАИ, МГУ, ТПИ, КГУ, ТГУ, НГУ
kl	H(kl)		в) Расстановочное поле для ключей
ВГУ				МГУ
КАИ				ТГУ
КГУ
ЛГУ				ТПИ
МГУ				НГУ
НГУ
ТГУ				КАИ
ТПИ				КГУ
. . .

Рис. 5.7. Таблица с открытым перемешиванием

Свободные позиции таблицы содержат особое значение, отличающее их от ключей (алг. 5.8, 5.9).

Алгоритм 5.8. Создание перемешанной таблицы t

/* Описание данных для перемешанной таблицы */

#define N ... /* Длина таблицы */

#define SVOB ... /* Свободный элемент */

Тип_ключа t[N]; /* Расстановочное поле */

int ksv; /* Кол-во позиций для включения элементов */

. . .

/* Инициализация пустой перемешанной таблицы */

int i;

. . .

ksv = N-1; /* Одна свободная позиция для поиска */

for (i=0; i<N; i++) t[i] = SVOB;

Алгоритм 5.9. Поиск с включением ключа kl в перемешанной таблице t (линейные пробы с шагом 1)

Тип_ключа kl; /* Ключ нового элемента */

int i; /* Текущий индекс в таблице */

/* Поиск ключа kl в таблице t */

i = H(kl); /* H - функция расстановки */

while (t[i]!=kl && t[i]!=SVOB)

if (i < N-1) i++; else i=0; /* i = (i+1) % N; */

if (t[i] != kl) /* Не нашли */

{ /* Включение элемента с ключом kl в таблицу t */

if (ksv==0) . . . /* Переполнение таблицы */

else /* Есть место для нового элемента */

{ ksv--; /* Занимаем SVOB */

t[i] = kl; /* Создание нового элемента */

}

} else . . . /* Нашли t[i] == kl */

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

Нельзя просто заменять значением "свободный" удаляемые из таблицы ключи. Например, если “удалить” таким образом ключ КГУ из таблицы на рис. 5.7 в, то при последующем поиске будет сделан неверный вывод, что ключа ТГУ нет в таблице. Чтобы не прерывать пути поиска, на место удаляемого элемента перемещается элемент, путь поиска которого проходит через позицию удаляемого элемента. Затем таким же образом освобождается старая позиция перемещенного элемента и т. д. (алг. 5.10). Это удается сделать только при включении элементов по алг. 5.9 для линейного рехеширования.

Алгоритм 5.10. Исключение элемента t[i] из перемешанной таблицы t, получаемой по алгоритму 5.9

int j; /* Индекс удаляемого эл-та */

int i; /* Текущий индекс в таблице */

int r; /* H(t[i]) */

do /* Исключение элемента t[i] */

{ j=i; t[j]=SVOB;

/* Поиск элемента, перемещаемого в освобождаемую позицию */

do

{ if (i<N-1) i++; else i=0;

if (t[i]!=SVOB) r=H(t[i]);

} while (t[i] != SVOB && /* r циклически между j и i : */

(j<r && r<=i || i<j && (r<=i || j<r)));

if (t[i] != SVOB) t[j] = t[i]; /* Перемещение элемента */

} while (t[i] != SVOB);

ksv++; /* Кол-во свободных позиций */

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

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

Для таблицы с открытым перемешиванием и линейными пробами (как в алг. 5.9) при равномерном распределении значений функции расстановки от 0 до N-1 средняя длина поиска приблизительно равна

_перем

D_ср = (2 - s) / (2 - 2*s) (для s £ 0.85) (5.14)

где s = m / N - коэффициент заполнения таблицы,

N - длина расстановочного поля,

m - количество элементов таблицы (занятых позиций).

Например, при s=0.8 Dср =3, т. е. в заполненной на 80% перемешанной таблице, независимо от того, сколько в ней элементов: 100 или 100000, поиск в среднем требует всего трех шагов! Это намного быстрее других методов.

При неравномерном заполнении таблицы длина поиска увеличивается на практике в 2-4 и более раз (все равно это быстро).

Две основные проблемы перемешанных таблиц - выбор функции расстановки и метода преодоления конфликтов.

Для функции расстановки обязательно условие (5.10) и желательно достаточно быстрое вычисление функции и, по возможности, равномерное рассеивание ключей по таблице для уменьшения числа конфликтов. Часто применяют функцию:

H(kl) = (Числовой код kl) % N

При N равном степени двух функцию H(kl) легко вычислять, но она плохо рассеивает символьные ключи, отличающиеся одним-двумя символами, типа: XA, XB, XC. В этом случае в качестве N рекомендуется простое число (делящееся только на себя и на 1). Деление часто заменяют умножением на обратную величину (это быстрее). Если ключ занимает несколько машинных слов, их предварительно можно сложить в одно слово арифметически или поразрядно по модулю 2 (исключающее или, в Си обозначается как ^).

Конфликт возникает, когда позиция i=H(kl) содержит ключ, не равный kl. Для разрешения конфликтов можно связать ссылками в список все конфликтующие ключи с одинаковыми значениями функции расстановки. Элементы списков размещаются в расстановочном поле или в отдельной области переполнения (тогда расстановочное поле может содержать только указатели списков).

Средняя длина поиска последовательным перебором в списке меньше, чем по формуле (5.13), т. к. списки короткие ввиду малого числа конфликтов. При наличии области переполнения размер расстановочного поля уже не ограничивает число элементов таблицы, а влияет лишь на количество конфликтов и скорость поиска. Недостатки метода - дополнительная память для ссылок и необходимость системы управления памятью. Другой метод разрешения конфликтов - открытая адресация (повторное перемешивание, рехеширование). В этом случае для поиска элемента пробуются позиции расстановочного поля i₀, i₁, i₂, ... , где

i₀ = H(kl),

i_k = (i₀+G(k)) % N при k>0, (5.15)

H(kl) - функция первичной расстановки,

G(k) - функция вторичной расстановки.

В простейшем случае G(k) = d*k, G линейно зависит от k. Это называется линейным рехешированием (опробованием) с шагом d (в алг. 5.9 шаг d=1). Его недостаток - скопления ключей в местах конфликтов.

Меньшие скопления возникают при квадратичном рехешировании, например, G(k) = k². При этом можно избежать умножения благодаря рекуррентным соотношениям

G(k+1) = (k+1)² = k²+2*k+1 = G(k)+d(k),

где d(k) = 2*k+1;

Отсюда: d(k+1) = 2*(k+1)+1 = d(k)+2.

Они реализуются в цикле поиска (как в алг. 5.9) операторами

i = i + d; if(i >= N) i = i - N; d = d + 2;

с начальными значениями i = H(kl); d=1;

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

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