Хеш функции - Studiopedia
Нека се обърнем към въпроса как да изберем добра хеш функция. Ясно е, че тази функция трябва да създава възможно най-малко сблъсъци при хеширане, т.е. трябва да разпределя равномерно ключовете към наличните индекси в масива. Разбира се, невъзможно е да се определи дали определена хеш функция ще разпредели правилно ключовете, ако тези ключове не са известни предварително. Въпреки това, въпреки че самите ключове рядко са известни преди избора на хеш функция, някои свойства на тези ключове, които влияят на тяхното разпределение, обикновено са известни.
Ясно е, че за различните типове ключове трябва да се използват различни хеш функции. Хеш функцията за целочислен ключ ще бъде различна от хеш функцията за низов ключ. В идеалния случай хеш функцията трябва да произвежда индексни стойности, които не са външно свързани с ключовете по никакъв начин. С други думи, много подобни ключове трябва да водят до различни хеш стойности.
12.4.1 Хеш функции за целочислени ключове
1) Най-известната хеш функция (която използвахме в примерите в този раздел) използваdivision,, където някакъв целочислен ключ се разделя на размера на таблицата и остатъкът от делението се приема като стойност на хеш функцията. Тази хеш функция е
h(Клавиш) = КлавишМод N.
Да приемем обаче, че N е 1000 и че всички ключове завършват с едни и същи три цифри (например, последните три цифри от номера на част може да са фабричният номер и програмата се пише за тази фабрика). Тогава остатъкът след разделянето на 1000 за всички ключове ще бъде един и същ, така че за всички записи с изключение на първия ще има хеш колизия. Ясно е, че с такъв набор от ключове трябва да се използва различна хеш функция. Установено е, че най-добриятрезултатите за метода на разделяне, както и за повечето други методи, се получават, когато размерът на таблицата N е просто число (т.е. N не се дели на никое положително цяло число, различно от 1 и N).
2) Стойността на хеш функцията с помощта наметода на умножениесе генерира по следния начин. Да приемем, че броят на позициите в таблицата, означен като N, е равен на цяло число на степен 2, т.е. N =2 n, където n е цяло число. Нека представим хеширания ключ Key като двоично число, умножете го по някаква предварително избрана стойност a и изберете дробната част в продукта Key*a. Нека означим тази дробна част като . При метода на умножение стойността, представена от n най-значимите цифри на двоичното представяне, се приема като стойност на хеш функцията. С други думи,
където ]x[ е най-голямото цяло число, което не превишава x.
Имайте предвид, че в метода на умножение, първо, се препоръчва да се използва ирационално число, което е близко до дължината на машинна дума, като стойност на a; a=(Sqrt(5)-1)/2 дава добри резултати, където Sqrt е функцията за квадратен корен; второ, изискването N да е цяло число на две не е задължително.
3) Вметода за преобразуване на бройната системаключът е представен в някаква p-ична бройна система:
Основата q на новата бройна система е избрана така, че q 2 + ... + dS-1×q S-1 .
Очевидно s ограничава реда на хеш стойността в q-ичната бройна система. Сложността на този метод е по-голяма от тази на предишните методи, тъй като s операции на умножение и събиране са необходими за изчисляване на стойността на h(Key).
4) За хеш функция, използващаметода на полиномно деление, се разглежда ключовата стойност, изразена в двоична система, която се записва, както следва:
Иключът е представен като полином
и се запазват същите коефициенти. Нека коефициентите на спомагателния полином са дадени предварително
Стойността на хеш функцията е остатъкът от деленето на Key(t) на C(t), разглеждан в двоичната бройна система. Ако изберем прост нередуцируем полином като C(t), тогава за key1 ¹ key2 условието h(key1) ¹ h(key2) е задължително изпълнено, т.е. тази хеш функция има силно свойство за разсейване на струпване.
5) Когато използвате метод, известен катометод на средния квадрат, ключът се умножава сам по себе си и няколко средни цифри от този квадрат се използват като индекс. Ако даденият квадрат се счита за десетично число, тогава размерът на таблицата трябва да бъде някаква степен на 10, а ако се счита за двоично число, тогава размерът на таблицата трябва да бъде степен на 2. Причината за повдигане на квадрат на числото преди извличане на средните цифри е, че всички цифри на оригиналното число допринасят за стойността на средните цифри на квадрата.
6) Сметод-сгъване, ключът е разделен на няколко сегмента, върху които се извършва операцията за добавяне или неидентичност, за да се формира хеш функция. Да предположим например, че вътрешното представяне на последователност от битове на ключ е 010111001010110 и индексът е пет бита. Над три последователности от битове 01011, 10010 и 10110 се извършва операцията за неидентификация:
11001 01111 - резултатът от прилагането на операцията за неидентификация,
което дава01111 или двоичното представяне на числото 15. (Операцияnot-identicalна два бита дава 1, ако стойностите на тези два бита са различни, и 0, ако стойностите им са равни.)
Има много други хеш функции, всяка от тяхсъс своите предимства и недостатъци в зависимост от набора хешируеми ключове. При избора на хеш функция е важна ефективността на нейното изчисляване, тъй като търсенето на някакъв обект в един опит няма да бъде по-ефективно, ако този опит отнема повече време от няколко опита с алтернативен метод.
12.4.2 Хеш функции за низови ключове
Ако ключовете не са числа, тогава те трябва да бъдат преобразувани в цели числа, преди да се приложат хеш функциите, описани по-горе. Има няколко начина да направите това. Например, за символен низ, вътрешното двоично представяне на кода на всеки знак може да се интерпретира като двоично число. Недостатъкът на това е, че за повечето компютри двоичните представяния на всички букви или числа са много сходни едно с друго.
Методътmergeизползва поредния номер в ANSI последователността на всяка буква, за да създаде някакво цяло число. И така, главната буква на българската азбука 'I' е представена от числата 200, а малката буква 'v' е представена от числата 226. Ключът "Иван" след обединяването на всички цифри на буквите е представен от цяло число 200226224237. Когато има някакво цяло число на символен низ, тогава методът на навиване или средния квадрат може да се използва, за да го редуцира до приемливо способен размер.
Методътweightingsизползва стойността на позицията на всеки знак, за да избегне сблъсъци при използване на анаграми като ключове (анаграмата е дума, получена от друга дума чрез пренареждане на нейните букви). Този метод се изпълнява от рутината SimpleHash, която изглежда така:
Функция SimpleHash(Const aKey: String; N: Integer): Integer;
Var i: Цяло число;
Не намерихте това, което търсихте? Използвайте търсачката: