4.4. Методы вычисления адреса

Пусть в каждом из М элементов массива Т содержится элемент списка (например целое положительное число). Если имеется некоторая функция H(V), вычисляющая однозначно по элементу V его «адрес» - целое положительное число из интервала [0, M-1],то V можно хранить в массиве T с номером H(V) т.е. V=T(H(V)). При таком хранении поиск любого элемента происходит за постоянное время не зависящее от M.

Массив T называется массивом хеширования, множество его индексов 1,…,М – пространством адресов, а функция H: V1,…,M – функцией хеширования.

При конкретном применении хеширования обычно имеется определенная область возможных значений элементов списка V и некоторая информация о них. На основе этого выбирается размер массива хеширования M и строится функция хеширования. Критерием для выбора M и H является возможность их эффективного использования.

Пусть нужно хранить линейный список из элементов K₁, K₂ ,..., K_n, n26 таких, что при K_iK_j, mod(K_i,26)mod(K_j,26) и работы с ними.

Для хранения списка выберем массив хеширования T(26) с пространством адресов 0-25 и функцию хеширования H(V)= mod(V,26).

Массив T заполняется элементами T(H(K_i))= K_i и T(j)=0, если j{H(K₁), H(K₂),..,H(K_n)}.

Поиск элемента V в массиве T с присваиванием Z его индекса если V содержится в T, или 0, если V не содержится в T, осуществляется следующим образом:

int t[26],v,z,i;

i=(int)fmod((double)v,26.0);

if(t[i]==v) z=i;

elsez= -1;

Добавление нового элемента V в список с возвращением в Z индекса элемента массива T, где он будет храниться, реализуется фрагментом

z=(int)fmod((doule)v,26.0);

t[z]=v;

а исключение элемента V из списка присваиванием

t[(int)fmod((double)v,26)]=0;

Теперь рассмотрим более сложный случай, когда условие K_iK_j H(K_i)H(K_j) не выполняется. Пусть V - множество возможных элементов списка (целые положительные числа), в котором максимальное число элементов равно 6. Возьмем M=8 и в качестве функции хеширования выберем функцию H(V)=Mod(V,8).

Предположим, чтоB=<K₁, K₂, K₃, K₄, K₅>, причемH(K₁)=5, H(K₂)=3, H(K₃)=6, H(K₄)=3, H(K₅)=1, т.е. H(K₂)=H(K₄) хотяK₂K₄. Такая ситуация называется коллизией, и в этом случае при заполнении массива хеширования требуется метод для ее разрешения. Обычно выбирается первая свободная ячейка за собственным адресом. Для нашего случая массив T[8] может иметь вид

T=<0, K5, 0, K2, K4, K1, K3, 0> .

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

intstatict[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;

Поиск в массиве 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 исключить элемент K₂, то получим массив хеширования в виде T=<0, K₅,0,0, K₄, K₁, K₃,0>, в котором невозможно найти элемент K₄, поскольку H(K₄)=3, а T(3)=0. В таких случаях при исключении элемента из списка можно записывать в массив хеширования некоторое значение, не принадлежащее области значений элементов списка и не равное нулю. При работе с таким массивом это значение будет указывать на то, что нужно просматривать со средние ячейки.

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