ХАШ МАСИ
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) и които ще сочат към съответните им синоними.