1. ВЪВЕДЕНИЕ.

Коренно различен подход към търсенето от предишните се състои в продължаване, не чрез сравнения между ключови стойности, а чрез намиране на някаква функция h (k), която ни дава директно местоположението на ключа k в таблицата.

маси

Първият въпрос, който можем да си зададем, е дали е лесно да се намерят такива h функции. Отговорът по принцип е доста песимистичен, тъй като ако приемем за идеална ситуация, че такава функция винаги дава различни местоположения на различни клавиши и мислим например за таблица с размер 40, където искаме да адресираме 30 ключа, откриваме, че в таблицата има 40 30 = 1,15 * 10 48 възможни функции за набор от клавиши и само 40 * 39 * 11 = 40!/10! = 2,25 * 10 41 от тях не генерират дублирани местоположения. С други думи, само 2 от 10 милиона такива функции биха били „перфектни“ за нашите цели. Тази задача е осъществима само в случай, че стойностите, които ще принадлежат на хеш таблицата, са известни априори. Има алгоритми за изграждане на перфектни хеш функции, които се използват за организиране на ключови думи в компилатор, така че търсенето на някоя от тези ключови думи да се извършва в постоянно време.

Функциите, които избягват дублиращи се стойности, са изненадващо трудни за намиране, дори за малки таблици. Например прочутият „парадокс за рождения ден“ гарантира, че ако 23 и повече души присъстват на среща, има голяма вероятност двама от тях да са родени в един и същи ден на същия месец. С други думи, ако изберете случайна функция, която прилага 23 ключа към таблица с размер 365, вероятността два ключа да не попаднат на едно и също място е само 0,4927.

Следователно приложенията h (k), които отсега нататък ще наричаме хеш функции, имат особеността, че можем да очакваме h (k i) = h (k j) за доста различни двойки (k i, k j). Следователно целта ще бъде да се намери хеш функция, която причинява възможно най-малък брой сблъсъци (поява на синоними), въпреки че това е само един аспект на проблема, другият ще бъде да се проектират методи за разрешаване на сблъсъци, когато те се появят.

2. ХАШ ФУНКЦИИ.

Първият проблем, с който трябва да се справим, е изчисляването на хеш функцията, която трансформира ключовете в местата на таблицата. По-конкретно, ние се нуждаем от функция, която трансформира ключовете (обикновено цели числа или низове от символи) в цели числа в диапазон [0.M-1], където M е броят на записите, които можем да обработим с наличната памет. предвид избора на функцията h (k) Те са проектирани да минимизират сблъсъците и да бъдат относително бързи и лесни за изчисляване, въпреки че идеалната ситуация би била да се намери функция з които ще генерират случайни стойности равномерно през интервала [0.M-1]. Двата подхода, които ще видим, са насочени към тази цел и и двата се основават на генератори на случайни числа.

Мултипликативно засичане.

Тази техника работи чрез умножаване на ключа к самостоятелно или от константа, след което се използва част от продуктовите битове като местоположение на хеш таблица.

Когато изборът е да се умножи к Сам по себе си и запазвайки част от средните битове, методът се нарича среден квадрат. Този метод е все още прост и може да отговори на критерия, че битовете, избрани за маркиране на местоположението, са функция на всички оригинални битове на к, Основните му недостатъци са, че клавишите с много нули ще бъдат отразени в хеш стойности също с много нули и че размерът на таблицата е ограничен до степен 2.

Друг мултипликативен метод, който избягва предишните ограничения, се състои в изчисляване на h (k) = Int [M * ​​Frac (C * k)], където M е размерът на таблицата и 0

Hasing по разделение.

В този случай функцията просто се изчислява като h (k) = k mod M като се използва 0 като първи индекс на хеш таблицата с размер M.

Въпреки че формулата е приложима за таблици с всякакъв размер, важно е да изберете внимателно стойността на M. Например, ако M беше четно, всички четни клавиши (нечетни съответно) щяха да бъдат приложени към четни местоположения (нечетни съответно), което би представлявало много силно пристрастие. Едно просто правило за избор на М е да се приема като просто число. Във всеки случай има по-сложни правила за избора на M (вж. Knuth), всички базирани на теоретични изследвания на действието на конгруентните методи за генериране на случайни числа.

3. РЕШЕНИЕ НА СБОРНИТЕ СЛУЧАИ.

Вторият важен аспект, който трябва да се изследва в хеширането, е разрешаването на сблъсъци между синонимите. Ще проучим три основни метода за разрешаване на сблъсъци, единият от които зависи от идеята за запазване на свързани списъци със синоними, а другите два от изчисляването на поредица от местоположения в хеш таблицата, докато се намери празна. Сравнителният анализ на методите ще бъде направен въз основа на проучването на броя на местата, които трябва да бъдат изследвани, докато се определи къде да се постави всеки нов ключ в таблицата.

За всички примери размерът на таблицата ще бъде M = 13 и хеш функцията h 1 (k), която ще използваме, ще бъде:

HASH = Ключ Mod M

и стойностите на ключа k, които ще разгледаме, са показаните в следната таблица:

Ако приемем, че k = 0 не се среща естествено, можем да маркираме всички местоположения на таблицата, първоначално празни, давайки им стойността 0. И накрая и тъй като операциите за търсене и вмъкване са тясно свързани, ще бъдат представени алгоритми за търсене на елемент като го вмъкнете. ако е необходимо (освен ако тази операция не причини преливане на таблицата) връщане на местоположението на елемента или -1 (NULL) в случай на препълване.

Отделно верижно или отворено закрепване.

Най-простият начин за разрешаване на сблъсък е да се създаде, за всяко място в таблицата, свързан списък от записи, чиито ключове попадат в тази посока. Този метод е известен като отделна верига и очевидно времето, необходимо за търсене, ще зависи от дължината на списъците и относителните позиции на ключовете в тях. Има варианти в зависимост от поддръжката, която правим на списъците със синоними (FIFO, LIFO, по ключова стойност и др.), Макар че в повечето случаи и като се има предвид, че отделните списъци не трябва да са твърде големи, обикновено избираме най-простата алтернатива, LIFO.

Във всеки случай, ако списъците се поддържат в ред, това може да се разглежда като обобщение на метода на последователно търсене в списъците. Разликата е, че вместо да поддържат един списък с един заглавен възел, М списъците с М заглавни възли се поддържат по такъв начин, че броят на сравненията на последователното търсене да се намали с коефициент М (средно), използвайки допълнително място за M указатели. За нашия пример и с алтернатива LIFO таблицата ще бъде както е показано на следващата фигура:

Понякога и когато броят на записите в таблицата е сравнително умерен, не е удобно да се дава на записите в хеш таблицата ролята на заглавки на списъци, което би ни довело до друг метод на веригиране, известен като вътрешна верига. В този случай обединението между синонимите е в самата хеш таблица, посредством полета на курсора (указатели), които се инициализират до -1 (NULL) и които ще сочат към съответните им синоними.

Адресиране отворено или затворено затворено.

Друга възможност е да се използва вектор, в който във всеки от неговите полета се поставя ключ. В този случай имаме проблема, че в случай на сблъсък и двата елемента не могат да бъдат част от списък за това поле. За да се реши този проблем, това, което се нарича пресъздаване. Преосмислянето се състои в това, че след като е възникнал сблъсък при вмъкване на елемент, се използва допълнителна функция, за да се определи коя ще бъде съответната клетка в таблицата, ще наречем тази функция преизчисляваща функция.,reh i (k).

Когато се дефинира функция за повторно препрограмиране, има множество възможности, най-простото е да се използва функция, която зависи от броя на направените опити за намиране на безплатно поле, в което да се вмъкне, този вид преизчисляване е известен като линейно хеширане. По този начин функцията за повторно препрограмиране ще бъде както следва:

reh i (k) = (h (k) + (i-1)) mod M i = 2.3.

В нашия пример, след вмъкване на първите 7 клавиша, се появява таблица А (вижте следната таблица). Когато ще вмъкнем ключ 147, той се поставя в клетка 6, (таблица Б), след като полета 4 и 5 не са намерени празни. Вижда се, че преди вмъкването на 147 е имало групи от ключове в местата 4,5 и 7,8, а след вмъкването тези две групи са се присъединили, образувайки по-голяма първична групировка, това означава, че ако се опитате да вмъкнете елемент, който съответства на някои от полетата, които са в началото на това групиране, процесът на повторно пренасочване ще трябва да премине през всички тези полета, което ще влоши ефективността на вмъкването. За да разрешим този проблем, ще трябва да потърсим метод за повторно препрограмиране, който разпределя празните клетки по възможно най-случаен начин.

След извършване на вмъкването на ключовете, разгледани в нашия пример, състоянието на хеш таблицата ще бъде това, което може да се види в таблицата (С), в която също се появява броят на опитите, необходими за вмъкване на всеки един. на ключовете.

За да се опитаме да избегнем проблема с клъстерирането, който току-що видяхме, бихме могли да използваме следната функция за повторно препрограмиране:

reh i (k) = (h (k) + (i-1) * C) mod M C> 1 и относително просто с M

но въпреки че това би предотвратило образуването на първични клъстери, това не би решило проблема с образуването на вторични клъстери (клъстери, разделени с разстояние C). Основният проблем на линейното повторно препрограмиране е, че за два различни ключа, които имат една и съща стойност за хеш функцията, ще се получи точно същата последователност от стойности при прилагане на препрограмирането, когато интересното ще бъде, че последователността от стойности Получено чрез повторно препрограмиране на процеса е различно. По този начин ще трябва да търсим функция за повторно препрограмиране, която отговаря на следните условия:

  • Бъдете лесно изчислими (с постоянна ефективност),
  • които избягват образуването на клъстери,
  • който генерира различна последователност от стойности за два различни ключа, въпреки че има една и съща стойност на хеш функция, и накрая
  • което гарантира, че всички клетки на таблицата са посетени.

Ако това не е изпълнено, може да се случи, че все още има свободни клетки, но не можем да вмъкнем определен елемент, защото стойностите, съответстващи на тези клетки, не се получават по време на повторно препрограмиране.

Преосмисляща функция, която отговаря на горните условия, е препрограмиращата функция. двойно преосмисляне. Тази функция се дефинира както следва:

h i (k) = (h i-1 (k) + h 0 (k)) mod M i = 2.3.

с h 0 (k) = 1 + k mod (M-2) и h 1 (k) = h (k).

Има възможност да се правят други избори за функцията h 0 (k), стига избраната функция да не е постоянна.

Тази форма на двойно повторно препрограмиране е особено добра, когато M и M-2 са относителни прости числа. Имайте предвид, че ако M е просто число, тогава е сигурно, че M-2 е неговото относително просто число (с изключение на тривиалния случай, че M = 3).

Резултатът от прилагането на този метод към нашия пример може да се види в следващите таблици. Първият включва стойностите на h за всеки ключ, а вторият показва крайните местоположения на ключовете в таблицата, както и тестовете, необходими за тяхното вмъкване.

4. ИЗТРИТО И ПРЕМИНАЛНО.

Когато таблица достигне препълване или когато нейната ефективност падне твърде ниска поради изтривания, единственото прибежище е да я преместите в друга таблица с по-подходящ размер, не непременно по-голям, тъй като изтритите местоположения не трябва да бъдат преназначавани, нова таблица тя може да бъде по-голяма, по-малка или дори със същия размер като оригинала. Този процес обикновено се нарича препрограмиране и е много лесен за изпълнение, ако ковчегът на новата таблица е различен от оригиналния, но може да бъде доста сложен, ако искаме да преработим самата таблица.

5. ОЦЕНКА НА МЕТОДИТЕ ЗА РЕЗОЛЮЦИЯ.

Най-важният аспект на търсенето на хеширане е, че ефективността му зависи от така наречения фактор за съхранение У = n/M с н броя на артикулите и М размера на масата.

Ще обсъдим средния брой тестове за всеки от методите за разрешаване на сблъсъци, които сме виждали, по отношение на БЪДА (успешно търсене) и BF (търсене без успех). Доказателствата за получените формули могат да бъдат намерени в Knuth (виж библиографията).

Отделно верижно обвързване.

Въпреки че може да бъде подвеждащо да се сравнява този метод с другите два, тъй като в този случай може да се случи У> 1, приблизителните формули са:

Тези изрази се прилагат дори когато У >> 1, така че за n >> M средната дължина на всеки списък ще бъде У и трябва да се очаква средно обхождане на средата на списъка, преди да се намери определен елемент.

Линейно окабеляване.

Приблизителните формули са:

Както се вижда, този метод, макар и задоволителен за малки параметри, е много лош, когато У -> 1, тъй като границата на средните стойности на БЪДА Y. BF са съответно:

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

Двойно закачане.

Формулите вече са:

със средни стойности, когато У -> 1 на М и М/2, съответно.

За да улесним разбирането на формулите, можем да изградим таблица, в която да ги оценим за различни стойности на У:

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

В сравнение с други техники за търсене, хеширането има предимства и недостатъци. Като цяло, за големи стойности на н (и разумни стойности на У) добрата схема на хеширане обикновено изисква по-малко тестове (от порядъка на 1,5 - 2), отколкото всеки друг метод за търсене, включително търсене в двоични дървета. От друга страна, в най-лошия случай тя може да се държи много зле, като изисква На) тестове. Като предимство може да се счита и фактът, че трябва да имаме някаква априорна оценка на максималния брой елементи, които ще поставим в таблицата, макар че ако нямаме такава оценка, винаги ще имаме възможност за като се използва методът на отделно верижно свързване, където препълването на таблицата не е проблем.

Друг относителен проблем е, че в хеш таблица нямаме нито едно от предимствата, които имаме, когато обработваме подредени връзки и т.н. Не можем да обработваме елементите в таблицата последователно или да завършим след неуспешно търсене нещо за елементите, които имат стойност, близка до тази, която търсим, но във всеки случай най-големият проблем, че хеширането е затворено, е този на изтриванията в таблицата.

6. ПРИЛАГАНЕ НА ХАШ ТАБЛИЦИ.

Внедряване на Open Hasing.

В този раздел ще извършим просто изпълнение на отворено хеширане, което ще послужи като илюстративен пример за това как работи. За това ще предположим тип данни овъглявам * за което ще проектираме проста хеш функция, състояща се от сумата от ASCII кодовете, които съставляват споменатия низ.

Възможна реализация, използваща абстрактния тип данни на списъка, би била следната:

За което можем да проектираме следните функции за създаване и унищожаване:

Както бе споменато по-горе, хеш функцията, която ще се използва, е:

И функции от типа HashMember, InsertHash, DeleteHash може да се програмира:

Както можете да видите, това изпълнение е доста просто, така че може да претърпи много подобрения. Предлага се като упражнение да се извърши тази работа, като се предоставят на типа данни възможности като:

  • Определяне на размера на таблицата по време на създаване.
  • Модификация на използваната хеш функция с помощта на указател на функция.
  • Конструиране на функция, която предава хеш таблица с определен размер в друга таблица с по-голям или по-малък размер.
  • Изграждане на итератор през всички елементи на таблицата.
  • и т.н.

Внедряване на затворен хасинг.

В този раздел ще направим просто изпълнение на затворено хеширане. За това ще предположим тип данниовъглявам * както в предишния раздел, за който ще проектираме същата хеш функция.

Възможно изпълнение на структурата за постигане е следното:

За което можем да проектираме следните функции за създаване и унищожаване:

Хеш функцията, която ще се използва, е същата като тази, която вече сме използвали за внедряването на Open Hasing. И функции от типа HashMember, InsertHash, DeleteHash Те могат да бъдат програмирани по следния начин, като се има предвид, че при това изпълнение ще използваме линейно препрограмиране.

Очевидно това изпълнение, подобно на откритото хеширане, също може да бъде подобрено, така че да бъде предложено упражнението по проектиране и внедряване на подобрена версия с възможности, подобни на изброените в предишния раздел.