Программирование на языке C


Методы вычисления адреса - часть 2


T= .

При наличии коллизий усложняются все алгоритмы работы с массивом хеширования. Рассмотрим работу с массивом T[100], т.е. с пространством адресов от 0 до 99. Пусть количество элементов N не более 99, тогда в T всегда будет хотя бы один свободный элемент равный нулю. Для объявления массива используем оператор

int static t[100];

Добавление в массив T нового элемента Z с занесением его адреса в I и числа элементов в N выполняется так:

i=h(z); while (t[i]!=0 && t[i]!=z) if (i==99) i=0; else i++; if (t[i]!=z) t[i]=z, n++;

Поиск в массиве T элемента Z с присвоением I индекса Z, если Z имеется в T, или I=-1, если такого элемента нет, реализуется следующим образом:

i=h(z); while (t[i]!=0 && t[i]!=z) if (i==99) i=0; else i++; if (t[i]==0) i=-1;

При наличии коллизий исключение элемента из списка путем пометки его как пустого, т.е. t[i]=0, может привести к ошибке. Например, если из списка B исключить элемент K2, то получим массив хеширования в виде T=, в котором невозможно найти элемент K4, поскольку H(K4)=3, а T(3)=0. В таких случаях при исключении элемента из списка можно записывать в массив хеширования некоторое значение непринадлежащее области значений элементов списка и не равное нулю. При работе с таким массивом это значение будет указывать на то, что нужно просматривать со средние ячейки.

Достоинство методов вычисления адреса состоит в том, что они самые быстрые, а недостаток в том, что порядок элементов в массиве T не совпадает с их порядком в списке, кроме того довольно сложно осуществить динамическое расширение массива T.




Начало  Назад  Вперед



Книжный магазин