Алгоритмы и структуры данных на С++. Аксёнова Е.А - 79 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

6.5. Хеширование 79
Алгоритм:
C1: i = h(K) + 1;
C2: если table[i].p=0, то перейти к шагу C6;
C3: если table[i].key= K, то УДАЧА;
C4: если table[i].link6= 0,
то i =table[i].link и перейти к шагу C3;
C5: уменьшаем R до тех пор, пока table[R].p6= 0;
если R = 0, то ПЕРЕПОЛНЕНИЕ;
иначе table[i].link= R, i = R;
C6: table[i].p=1; table[i].key= K; table[i].link=0.
Обозначим C(n) – среднее время поиска в случае, если алгоритм
заканчивается удачей, а C
0
(n) – среднее время поиска, если алгоритм
заканчивается неудачей. Тогда для приведенного алгоритма C(n) =
= 1 +
1
8α
(e
2α
− 1 − 2α) +
1
4
α, C
0
(n) = 1 +
1
4
(e
2α
− 1 − 2α) , где α =
M
n
–
коэффициент заполнения таблицы размера n, содержащей M ключей.
Алгоритм поиска по рассеянной таблице с цепочками можно мо-
дифицировать – хранить несколько связных списков, по одному на
каждый хеш-адрес. При такой модификации необходимо хранить на-
чальные адреса списков. После хеширования выполняется последо-
вательный поиск в соответствующем списке. Можно ускорить поиск,
если для каждого хеш-адреса хранить не связный список, а дерево
поиска.
Поиск со вставкой по открытой рассеянной таблице
Рассмотрим другой алгоритм организации хеш-таблицы, в котором
коллизии разрешаются простым перебором соседних мест в таблице.
Пусть элементы таблицы поиска имеют следующий вид:
struct node{int p; int key;},
где p – признак занятости узла (p=0 – узел свободен, p=1 – узел занят),
key – ключ. Таблица элементов хранится в массиве node table[n].
Пусть M – число занятых элементов в таблице. В начале работы
M = 0. Таблица будет считаться переполненной, если M = n − 1.
Пожертвуем одной ячейкой для того, чтобы внутренний цикл был
быстрее. В противном случае необходимо будет заводить счетчик для
числа повторений шага L2.
6.5.    Хеширование                                                       79


   Алгоритм:

       C1: i = h(K) + 1;
       C2: если table[i].p=0, то перейти к шагу C6;
       C3: если table[i].key= K, то УДАЧА;
       C4: если table[i].link6= 0,
           то i =table[i].link и перейти к шагу C3;
       C5: уменьшаем R до тех пор, пока table[R].p6= 0;
           если R = 0, то ПЕРЕПОЛНЕНИЕ;
           иначе table[i].link= R, i = R;
       C6: table[i].p=1; table[i].key= K; table[i].link=0.
   Обозначим C(n) – среднее время поиска в случае, если алгоритм
заканчивается удачей, а C 0 (n) – среднее время поиска, если алгоритм
заканчивается неудачей. Тогда для приведенного алгоритма C(n) =
       1
= 1 + 8α (e2α − 1 − 2α) + 14 α, C 0 (n) = 1 + 14 (e2α − 1 − 2α) , где α = M
                                                                          n –
коэффициент заполнения таблицы размера n, содержащей M ключей.
   Алгоритм поиска по рассеянной таблице с цепочками можно мо-
дифицировать – хранить несколько связных списков, по одному на
каждый хеш-адрес. При такой модификации необходимо хранить на-
чальные адреса списков. После хеширования выполняется последо-
вательный поиск в соответствующем списке. Можно ускорить поиск,
если для каждого хеш-адреса хранить не связный список, а дерево
поиска.

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

   struct node{int p; int key;},

где p – признак занятости узла (p=0 – узел свободен, p=1 – узел занят),
key – ключ. Таблица элементов хранится в массиве node table[n].
Пусть M – число занятых элементов в таблице. В начале работы
M = 0. Таблица будет считаться переполненной, если M = n − 1.
Пожертвуем одной ячейкой для того, чтобы внутренний цикл был
быстрее. В противном случае необходимо будет заводить счетчик для
числа повторений шага L2.

Страницы