Метод цепочек

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

Для локализации свободного места введем переменную P, которая изначально указывает на конец списка: P=N+1. При возникновении коллизии свободную ячейку мы будем брать исходя из значения P: для этого P уменьшается на 1 до тех пор, пока ячейка с индексом P не станет свободной. Найденная ячейка будет использована для нового значения, заносимого в таблицу. Таким образом, все ячейки с индексами больше P всегда заняты.

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

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

Более формально, для хранения хэшированной методом цепочек таблицы, состоящей из не более чем 1000 целых чисел, необходимо определить следующие данные

#define Nmax 1000

Typedef struct CNode_

{int value; int is_empty; int next;} CNode;

CNode node[Nmax];

Int P;

Int hash(int value);

Здесь мы использовали те же самые обозначения, что и раньше, плюс к тому, появился член структуры next, служащий номером следующей ячейки в данной цепочке и целая переменная P для указания на номер последнего включенного в список элемента, при включении которого произошла коллизия.

Функция инициализации данных может выглядеть следующим образом

void Init(CNode node[])

{int i;

for(i=0;i<Nmax;i++){node[i].is_empty=1; node[i].next=-1;} P=Nmax;

}

здесь мы использовали информацию о том, что ячейки в таблице имеют индексы от 0 до Nmax-1 и, поэтому, P указывает на первую (не существующую) ячейку после таблицы.

Процедура поиска в таблице будет иметь следующий вид

int search(CNode node[])

{

int i; i=hash(value);

if(node[i].is_empty)return –1;

for(; node[i].next>=0; i=node[i].next)

if(node[i].value==value)return i;

return –1;

}

Процедура занесения значения value в таблицу будет иметь следующий вид

int add(CNode node[], int value)

{

int i; i=hash(value);

if(node[i].is_empty)// если нет коллизии

{node[i].value=value; node[i].next=-1; return 0;}

// иначе – если коллизия есть: ищем конец цепочки:

for(; node[i].next>=0; i=node[i].next);

// ищем свободное место:

do{ P--;

if(P<0)return –1;// переполненние

}while(!node[P].is_empty);

// помещаем элемент на найденное место:

node[P].value=value; node[P].is_empty=0; node[P].next=-1;

node[i].next=P;

Return 0;

}

Для того, чтобы понять преимущество метода цепочек над методом линейных проб, рассмотрим следующую ситуацию. Пусть таблица сильно заполнена. Пусть в данный момент в таблицу еще не заносились элементы в позицию с индексом i. При первом появлении элемента x₁ такого, что h(x₁)=i все происходит почти также, как и в методе проб: элемент заносится в таблицу, ссылка на следующий элемент устанавливается в пустоту:

node[i].value= x₁

node[i].next=-1

node[i].is_empty=0

Если же появится еще один элемент x₂ такой, что h(x₂)=i, то сразу станет ясно отличие от метода проб: для нового элемента ищется свободное место с помощью уменьшения P до тех пор, пока не станет выполняться is_empty[P]==1; новый элемент помещается в позицию P и ссылка next[i] устанавливается на позицию P.

Т.о., с одной стороны, мы не просматриваем в поисках свободного места заведомо заполненную часть таблицы, а с другой - поиск элемента x₂ теперь займет всего два сравнения. Вообще, переменная P может смежаться на одну позицию не более, чем N раз, а т.к. в таблицу заносится не более, чем N элементов, то получается, что в среднем для поиска свободного места для одного элемента переменная P изменяется всего на 1, т.е. в среднем проводится не более одной проверки на пустоту очередной позиции с индексом P.

Хэш-функции

Существует два наиболее простых метода построения хэш-функций: на основе деления и на основе умножения.

Дата добавления: 2015-10-30