Открытая адресация. Метод линейных проб

Можно попробовать использовать для хранения данных таблицу без ссылок. Будем дополнительно в каждой ячейке таблицы хранить информацию о том – занята ли ячейка или нет. Если при занесении в таблицу нового элемента хэш-функция от заносимого значения укажет на пустую ячейку, то проблем никаких нет. Иначе, получается ситуация, называемая коллизией. Разрешение коллизий является основной целью при создании алгоритмов работы с хешируемыми множествами.

Простейший способ разрешения коллизий в таблице следующий: если элемент, на который указывает хэш-функция, занят, то мы рассматриваем последовательно все элементы таблицы от текущего, пока не найдем свободной место. Новый элемент помещается в найденное свободное место.

 

Отметим, что можно рассматривать и другие алгоритмы поиска свободного места в хэш-таблице (а следовательно, и алгоритма поиска элементов с тем же значением хеш-функции). Единственное ограничение на метод перебора элементов таблицы: перебор должен гарантировать просмотр всех элементов таблицы.

Например, вместо того, чтобы брать следующий элемент, можно брать элемент с шагом h, где h взаимно-просто с длиной таблицы (=линейное пробирование).

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

Можно увеличивать шаг с каждым шагом поиска следующего элемента (=квадратичное пробирование). В этом случае шаги могут вычисляться, например, по формулам: h1= 1, h2= 2, …, hk= k для таблицы длины 2P (соответствует индексам ik= i0+k2/2+k/2 (mod 2P)). В общем случае, шаги могут увеличиваться каждый раз на нечетное целое: h1= 2h+1, h2= 2(2h+1), …, hk= k(2h+1) (где h≥0) для таблицы длины 2P. Докажем, что при таком выборе шагов полученные подряд 2P целых чисел будут различны и, следовательно, покроют весь набор целых чисел от 0 от 2P (не включительно).

Сначала выведем явную формулу соответствующих xi таких, что xi - xi-1 =(2h+1)i. Легко получить, что

xi= x0+(h+1/2)i2+(h+1/2)i    (mod 2P).

Отметим, что, несмотря на дробные коэффициенты, xi целые. Осталось решить уравнение

 (h+1/2)i2+(h+1/2)i =  (h+1/2)j2+(h+1/2)j    (mod 2P)

для 0≤i,j<2P

Имеем:

(h+1/2)i2+(h+1/2)i - (h+1/2)j2-(h+1/2)j = t 2P

(2h+1)(i-j)(i+j+1) = t 2P+1

 (i-j)(i+j+1) = 2P+1 t/(2h+1)

Возможны два случая: либо i-j четно и i+j+1 нечетно, либо i-j нечетно и i+j+1 четно.

a)      i-j четно и i+j+1 нечетно
в этом случае i-j должно делиться на 2P+1и в силу ограничений на i,j получаем, что i=j.

b)      i-j нечетно и i+j+1 четно
в этом случае i+j+1 должно делиться на 2P+1 , но в силу ограничений на i,j получаем, что i+j+1≤2P-1+2P-1+1=2P+1-1 , следовательно i=j.

 

Таким образом мы доказали следующую теорему:

Теорема. Квадратичное пробирование с шагами hk= k(2h+1) (где h≥0) для таблицы размером 2P гарантирует, что первые 2P перебираемых элементов будут различны и покроют все значения таблицы. Данный перебор соответствует прямой формуле для вычисления индекса i-го элемента: ki= k0+(h+1/2)i2+(h+1/2)i    (mod 2P).

 

Чтобы отследить ситуацию с переполнением таблицы, мы введем переменную M – счетчик количества занятых ячеек в таблице. Если значение M достигло величины N-1, то мы считаем, что наступило переполнение. Это гарантирует нам, что в таблице всегда будет в наличии хотя бы одна пустая позиция.

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

На языке С алгоритм поиска элемента value в таблице из Nmax целых чисел можно реализовать следующим образом.

 

#define Nmax 1000

typedef struct CNode_{int value; int is_empty;} CNode;

CNode node[Nmax];

int hash(int value);

int search(CNode node[])

{

 int  i;

 for(i=hash(value); !node[i].is_empty; i=(i==0? Nmax-1 : i-1))

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

 return –1;

}

 

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

Чтобы сэкономить память признаки  пустоты элементов таблицы можно реализовать отдельно от самой таблицы. Тогда под каждую ячейку можно будет отвести ровно 1 бит информации:

 

#define Nmax 1000

int value[Nmax], is_empty[(Nmax+31)/32];

int hash(int value);

int search(CNode node[])

{

 int  i;

  for(i=hash(value); !(is_empty[i/32]&(i%32)); i=(i==0? Nmax-1 : i-1))

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

 return –1;

}

 

Удаление элемента из таблицы несколько более сложное, чем добавление и поиск. Нельзя просто объявить позицию i, в которой требуется удалить элемент, пустой. Если это сделать, то элемент value[j] с индексом j<i, для которого h(value[j])≥i и для которого все элементы с индексами между j и i заняты, окажется потерянными для последующего поиска (здесь мы рассматриваем случай отсутствия `перескока’ в конец массива при поиске очередного элемента). Действительно, при поиске этого элемента мы обязательно натолкнемся на пустую позицию value[i] и поиск будет завершен.

Чтобы исправить ситуацию мы должны найти первый такой элемент value[j], перенести его значение в позицию i и свести задачу к удалению элемента value[j]. Естественно, мы должны учитывать возможность `перескока’ в конец массива при поиске такого value[j]. Т.е., более строго, условия переноса value[j] в позицию i следующее:

h(value[j])≥i>j (отсутствие перескока)

 

или

j>h(value[j])≥i (перескок)

     

или

i>j>h(value[j]) (перескок)

 

Условием остановки алгоритма является пустота позиции j.

Подпрограмма удаления элемента с индексом i из списка может выглядеть следующим образом

void remove(CNode node[], int  i)

{int j; node[i].is_empty=1;

 for(j=(i==0? Nmax-1 : i-1); !node[j].is_empty; j=(j==0? Nmax-1 : j-1))

 if( (hash(value[j])>=i && i>j) || (hash(value[j])>=i && j>hash(value[j])) ||

  (i>j && j>hash(value[j])))

 {

  node[i].is_empty=0; node[i].value=node[j].value;

  remove (node,j);

  break;

 }

}

 

 

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

Мы будем использовать следующее предположение: все расположения m элементов в хешированной таблице, состоящей из n записей равновероятны.

 

Лемма. Si=0 M CL+iL = CL+M+1L+1

Доказательство.

M=0: CLL = CL+1L+1

M:  Si=0 M CL+iL =Si=0 M-1 CL+iL + CL+ML = CL+ML+1 + CL+ML =

=(L+M)!/((L+1)!M!) + ((L+M)!/(L!M!))= (L+M+1)!/((L+1)!M!)= CL+M+1L+1

¢

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

Если вслед за позицией, на которую указала хэш-функция следует k-1 занятая запись (включая запись, на которую указала хэш-функция), то время вставки есть Q(k) (т.к. для поиска свободной позиции надо будет осуществить k проб). Пусть вероятность того, что начиная с данной позиции следует k-1 занятых позиций, а следующая позиция свободна, равна pk. Тогда, учитывая то, что количество подряд занятых позиций не может превзойти M, среднее время вставки элемента пропорционально

TM = Si=1 M+1 k pk

Согласно вышеприведенному предположению, вероятность pk равна количеству перестановок оставшихся M-k+1 занятых позиций среди оставшихся N-k записей, деленное на общее число перестановок CNM. Итак

pk= CN-kM-k+1 / CNM

 

TM = Sk=1 M+1 k pk =

(учитывая (N+1)Si=1 M+1 pi=(N+1) )

N+1-Sk=1 M+1 (N+1-k) pk =

N+1-Si=1 M (N+1-k) CN-kM-k+1 / CNM =

(учитывая Cnk=Cnn-k)

=N+1 - Sk=1 M+1 (N + 1- k ) CN-kN-M-1 / CNM =

=N+1 - Sk=1 M+1  ( (N-k+1)! / ((N-M-1)!(M-k+1)!) ) / CNM =

=N+1 - Sk=1 M+1 (N -M) CN-k+1N-M / CNM =

(замена i=M-k+1, k=M-i+1)

=N+1 - Si=0 M (N -M) CN-M+kN-M / CNM =

(согласно лемме)

N+1 -(N -M) CN-M+M+1N-M+1 / CNM= N+1 -(N -M) CN+1N-M+1 / CNM

=N+1-(N-M) ((N+1)!/((N-M+1)!M!))  M!(N-M)!/N! =

= N+1 – (N-M)(N+1)/(N-M+1) = (N+1)/(N-M+1)

 

 


Оценим теперь время удачного поиска. Легко увидеть, что все операции, производимые для удачного поиска некоторого элемента списка, совпадают с операциями, которые производились для вставки этого элемента в список. Среднее время удачного поиска равно среднему из всех средних времен, затрачиваемых на поиск каждого элемента в списке. Поэтому, среднее время удачного поиска равно среднему из времен вставки элементов, находящихся на данный момент в списке,  в список. Т.о., если рассматривать элементы в списке в порядке их поступления в список, то получим, что среднее время удачного поиска равно

TM = 1/(M+1) Si=0 M Ti = 1/(M+1) Si=0 M (N+1)/(N-i+1)=

= 1/(M+1) Si=0 M (N+1)/(N-i+1)= 1/(M+1) Sj=N-M+1 N+1(N+1)/j£

(N+1)/(M+1)òt=N-M+1 N+11/t dt=(N+1)/(M+1) log((N+1)/(N-M+1))

 

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

Т.о. если ввести коэффициент заполненности таблицы a=M/N, то верна следующая теорема

Теорема. Среднее время неудачного поиска элемента в таблице (=время добавления нового элемента), состоящей из N записей, M из которых заполнены

ТM=Q(1/(1-a)), где a=M/Nкоэффициент заполненности таблицы.

Среднее время удачного поиска имеет следующую оценку

ТM =Q( (1/a) log(1/(1-a)) )

Среднее время удаления элемента равно

SM=O(1/(1-a)).