Помощничек
Главная | Обратная связь


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

Дозвіл колізій при хешуванні методом ланцюжків



 

Він є організацією зв'язаного списку зі|із| всіх записів, чиї ключі|джерела| хешуються| в одне і те ж значення.

 

75 66 42 192 91 40 49 87 67 16 417 130 372 227

 

Мал. Дозвіл колізій при хешуванні методом ланцюжків.

 

type|

link| = ^node;

node| = record|

key|: integer|;

st|: string|;

next|: link|;

end|;

 

var|

mas|: array|[0..9] of| link|;

 

function| h(key|: integer|): integer|;

begin|

h:=key| mod| 10;

end|;

 

function| search|(key1|: integer|; st1|: string|): link|;

var|

i: integer|;

q, p, s: link|;

begin|

i:=| h(key1|);

q:=nil|;

p:=mas|[i];

while| p <> nil| do|

begin|

if| p^|.key = key1| then|

begin|

search:=p|;

exit|;

end|;

q := p;

p := p^|.link;

end|;

{Якщо ключ|джерело| не знайдений, вставляємо новий запис}

new|(s);

s^|.key:=key1;

s^|.st:=st1;

s^|.next:=nil;

if| q = nil| then|

mas|[i]:=s

else|

q^|.next:=s;

search:=s|;

end|;

 

Видалення|віддалення| вузла з|із| таблиці, яка побудована|спорудити| по методу ланцюжків, полягає просто у виключенні|винятку| вузла із|із| зв'язаного списку. Видалений|віддалений| вузол ніяк не впливає на ефективність алгоритму пошуку. Алгоритм працюватиме так, як якби|аби| цей вузол ніколи не вставлявся в таблицю. Відзначимо, що ці списки можуть бути динамічно переупорядковані для отримання|здобуття| більшої ефективності пошуку.

 

Основним недоліком|нестачею| методу ланцюжків є|з'являється| те, що для вузлів покажчиків потрібний додатковий простір|простір-час|.

 

Вибір хеш-функції|

 

Звернемося|обертатимемося| тепер до питання про те, як вибрати хорошу|добру| хеш-функцію. Ясно, що ця функція повинна створювати якомога менше колізій при хешуванні, тобто вона повинна рівномірно розподіляти ключі|джерела| на наявні індекси в масиві. Звичайно, не можна визначити, чи буде деяка конкретна хеш-функція розподіляти ключі|джерела| правильно, якщо ці ключі|джерела| заздалегідь|наперед| не відомі. Проте|однак|, хоча до вибору хеш-функції| рідко відомі самі ключі|джерела|, деякі властивості цих ключів|джерел|, які впливають на їх розподіл, зазвичай|звично| відомі.

 

- Метод ділення|поділу|. Деякий цілий ключ|джерело| ділиться на розмір таблиці і залишок|остачу| від ділення|поділу| береться як значення хеш-функції|. Ця хеш-функція позначається|значить| h (key|) := key| mod| m.

- Метод середини квадрата. Ключ |джерело| множиться сам на себе і як індекс використовується декілька середніх цифр цього квадрата.

 

Function| h(key|: integer|): integer|;

Begin|

Key:=key*key|; {Звести в квадрат}

Key:=key| shl| 11;{Відкинути 11 молодших біт}

H:=| key| mod| 1024;{Повернути 10 молодших біт}

End|;

 

- Адитивний метод для рядків (розмір таблиці дорівнює 256). Для рядків цілком|сповна| розумні результати дає сумування всіх символів і повернення залишку|остачі| від ділення|поділу| на 256.

 

Function| h(st|: string|): integer|;

Var|

Sum|: longint|;

I: integer|;

Begin|

For| i:=0| to| length|(st|) do|

Sum| := sum| + ord|(st|[i]);

H:=sum| mod| 256;

End|;

 

- Вилучення АБО для рядків (розмір таблиці дорівнює 256). Цей метод аналогічний адитивному, але|та| успішно розрізняє схожі слова і анаграми (адитивний метод дасть одне значення для XY| і YX|). Метод полягає в тому, що до елементів рядка послідовно застосовується операція що "виключає або". У алгоритмі додається|добавляє| випадкова компонента, щоб|аби| ще поліпшити результат.

 

var|

rand8|: array|[0..255] of| integer|;

 

procedure| init|;

var|

i: integer|;

begin|

randomize|;

for| i:=0| to| 255 do|

rand8|[i]:=random(255);

end|;

 

function| h(st|: string|): integer|;

Var|

Sum|: longint|;

I: integer|;

Begin|

For| i:=0| to| length|(st|) do|

Sum| := sum| + ord|(st|[i]) xor| rand8|[i];

H:=sum| mod| 256;

end|;

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.