Забравена парола?
Начало на реферати

Хеширане, използване на хеш-функции


3. Хеширане


Това е техника Едно от приложенията на хеширането е

за организация на редица от записи, позволяваща ефективно вмъкване, изтриване и търсене. Записите са организирани така, че да съдържат уникален ключ, чрез който се определя позицията им в редицата. Обикновено ключовете са естествени числа или низове. Ако ключовете са естествени числа, разположени в достатъчно малка област, всеки запис може да се съхранява на позицията, зададена чрез неговия ключ. Най-често обаче това не е така, ключовете са естествени числа в интервал по-голям от наличното количество памет. Ако ключовете са низове, може да им се съпоставят естествени числа. Изискването на различни низове да бъдат съпоставени различни естествени числа обикновено води до получаването на големи числа, така че съдържащата ги област ще е твърде голяма.

В резултат от хеширането дадените записи се записват в хеш-таблица. Основни операции с хеш-таблица са вмъкването, изтриването и търсенето на запис с указан ключ. Целта е хеш-таблицата да е организирана така, че тези операции да са от порядъка на константа.

Нека разполагаме с памет за съхранение най-много на N записа, номерирани с 0, 1, ..., N-1. Целта е към ключовете да се приложи функция, наречена хеш-функция, за да се получи стойността на първичния индекс – неотрицателно цяло число i, по-малко от N. Въпреки, че еднозначното съответствие е желателно няма да го изискваме, т.е. няма да искаме на два различни ключа k1 и k2 хеш-функцията hash да съпоставя различни цели числа, т.е. за hash е възможна ситуацията hash(k1) = hash(k2) за k1≠k2, която се нарича колизия.

Два честоизползвани начина за разрешаване на колизиите са прякото свързване и отвореното адресиране.


3.1. Пряко свързване

Построява се едномерен масив от K едно-свързани списъка. K може да е по-голямо, равно или по-малко от N. При прилагане на хеш-функцията към ключа се получава индекс, по който в масива се намира свързаният списък, към който ще се приложи желаната операция (търсене, изтриване или вмъкване). Търсенето в тези списъци е възможно тъй като ключовете са част от записите. Ако хеш-функцията е добра, свъраните списъци ще бъдат къси и методът ще е много бърз.


Пример: Нека разгледаме следната таблица от 7 записа:

Petrov 9123456

Todorov 9943937

Kolev 9121212

Penev 9929292

Lekov 9767688

Dineva 9346523

Хеширане, използване на хеш-функции facebook image
Публикувано от: Наталия Апостолова

Приятелски Функции в C++ 9 out of 10 based on 2 ratings. 2 user reviews.