Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I. 2.3. Табличный симплекс-метод.
  2. I. 3.2. Двойственный симплекс-метод.
  3. I. Передача параметров запроса методом GET.
  4. II. Методика работы
  5. II. Методика работы.
  6. II. Методика работы.
  7. II. Методика работы.

Для разрешения коллизий метод проб можно немного модифицировать. В каждый элемент таблицы, состоящей из 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. При первом появлении элемента x1 такого, что h(x1)=i все происходит почти также, как и в методе проб: элемент заносится в таблицу, ссылка на следующий элемент устанавливается в пустоту:

node[i].value= x1

node[i].next=-1

node[i].is_empty=0

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

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

 

 

 


Хэш-функции

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


Дата добавления: 2015-10-30; просмотров: 110 | Нарушение авторских прав


Читайте в этой же книге: Добавление элемента | Сбалансированные и идеально сбалансированные бинарные деревья поиска | Добавление элемента в дерево | Разбиение дерева по разбивающему элементу | Добавление элемента в красно-черное дерево | Однопроходное добавление элемента в красно-черное дерево | Удаление элемента из красно-черного дерева | Отступление на тему языка С. Быстрый поиск и сортировка в языке С | Удаление вершины из B-дерева | Метод линейных проб |
<== предыдущая страница | следующая страница ==>
Доказательство.| Хэш-функции на основе деления

mybiblioteka.su - 2015-2024 год. (0.009 сек.)