10 (1). Хеширане. Търсене, включващи и изключващи елементи. Случаен функция (хеш) и неговите свойства.
По-рано се счита за събиране въз основа на търсенето дървета позволяват да се изгради един абстрактен тип данни "маса". Но тези колекции са логаритмична операция отнема време, в зависимост от броя на елементите в таблицата. Има приложения, които изискват бързо и гарантирано изпълнение на време, независимо от обема на данните в таблицата. В този случай специална организация на таблицата с постоянен операции време - хеш таблица.
Hash маса изисква памет О (# 9474; т # 9474), където m - многото включени в таблицата на записи. Търсене време в хеш таблицата все още е O (1).
хеш таблица индекс часа е даден елемент (к), където К - ключ Н (к) елемент - разбъркващата функция (или произволност функция). ч номер (к), се нарича хеш стойност на ключ к. Процесът на превръщане на ключов елемент в индекса на хашиш - на масата се нарича хеширане.
Hash функция (рандомизиране функция) и неговите свойства
1. Една добра хеш функция трябва да се осигури еднакво хеширане, това е, за всички ключови всички хеш стойности м трябва да са еднакво вероятни.
2. по произволен функция не трябва да се поддържа някаква връзка между стойностите на ключовете. Това изискване елиминира (или поне намалява) зависимостта на "качество" рандомизацията на ключови стойности, използвани.
4. Hash - функция трябва да бъде детерминирана в смисъл, че след многократни разговори към един и същи ключ, тя трябва да се върнат на същата хеш стойност.
Управление функция действие Randomize е показано на фиг.
· Разделяне Метод остатък (модулна хеширане) дава прост и ефективен разбъркваща функция. Ключ к се получава остатък на разделяне к с т. Функцията хеш се изчислява като уравнение Н (к) = к мод m.
Например, ако m = 13, к = 100, след това часа (к) = 9.
· Метод умножение (множител) изчислява хеш - функция с формула
където А е константа отговаря 0 Силата на размножаване на метода е, че качеството на разбъркващата функция зависи малко от избора на м. Но обикновено като м изберете степен на две, като в повечето компютри умножаване с мощност от два се осъществява бързо, тъй като промяната на думата. метод за умножение работи за всеки избор на постоянен А. но някои стойности на А може да са по-добри от други. Най-добрата стойност е числото на Фибоначи. А = ,6180339887 Ние илюстрира метода с конкретен пример. Да предположим, че хеш размер - маса M = 10000. При поставяне на ключа ще хеширате 123456 - това означава: разбъркваща функция (ключ низ [4].): цяло число; е: = РСР (клавиш [1]) - РСР (ключ [2]) + РСР (клавиш [3]) - РСР (клавиш [4]); е: = (е * 10000) DIV (255 * 4); Методи за разрешаване на конфликти Процедурата за отстраняване от таблицата се редуцира до намирането на елемент и отстраняването му от веригата за преливане. Фигура 3.2. Разнообразие от методи за разрешаване на конфликти Фигура 3.3. Резолюция Сблъсък добавяне на елементи от вериги Линеен тестване се редуцира до последователно сканиране на таблицата на елементи с определена стъпка където аз - брой опити за разрешаване на конфликта. В стъпка равна на един е пореден търсене на всички елементи, след ток. Квадратичен тест различава от линейната стъпката на следващите стъпки не линейно в зависимост от броя на опитите да се намери свободен елемент Активирането и търсене Ние описваме вмъкване алгоритми и метод за извличане на линеен тестване. · А = Н (ключ) + I * в • Ако т (а) = свободно, т (а) = ключ. напиши елемент се добавя стоп елемент · I = I + 1, преминете към стъпка 2 · А = Н (ключ) + I * в • Ако т (а) = ключ. ограничителният елемент е намерена • Ако (а) = свободно, ограничителният елемент не е намерен т · I = I + 1, преминете към стъпка 2 Изборът стъпка р. Когато се опитате да добавите елемент към една заета клетка започне да се последователно сканиране на клетките и така нататък, докато не се намери свободно клетка. В него, и пишат елемент. По същество последователно търсене - специален случай на линейна, където р = 1. Етап Q не е фиксирана, но варира от втора: Q = 1,4,9,16. Съответно, когато се опитате да добавите елемент към една заета клетка започне да се последователно сканиране на клетките и така нататък, докато не се намери свободно клетка. двойно хеширане Тя показва размера на хеш таблица 13 клетки, който използва помощни функции: Искаме да въведете ключ 14. Първоначално I = 0. След това. Но с индекс 1 и съща клетка, затова решихме да увеличим и с 1 и преизчисляване на стойността на хашиш. Ние правим така, докато не достигнем празна клетка. Когато аз = 2, ние получаваме. Клетката с номера 9 е безплатно, а след това ви пишем, за да бъде основното ни. (Етап 2). С процедурата по отстраняване значение, че не е толкова просто, тъй като в този случай няма да е процедура обратна вмъкване. Фактът, че елементите на таблицата са в две състояния: свободен и зает. Ако изтриете даден елемент, като го поставите в свободна, след отстраняване на алгоритъма за търсене няма да работи коректно. Да приемем, че ключовият елемент е отстранен в синоними на ключове маса. В случай на сменяем елемент, в резултат на сблъскване елементи за разрешаване били поставени с други клавиши, списъкът на тези елементи след отстраняване винаги ще даде отрицателен резултат, тъй като алгоритъм за търсене спира на първия елемент се намира в състояние свободно. За да коригирате тази ситуация по различни начини. · Най-простият от тях е за търсене на елемент не е до първото място, а до края на масата. Въпреки това, такава модификация на алгоритъма ще унищожи цялата печалба в ускоряване на достъп до данните, което се постига чрез хеширане. · Налице е един подход, който е свободен от тези недостатъци. Същността му се състои в това, че добавената състоянието отстранени елементи на хеш таблицата. Това състояние на процеса на търсене се тълкува като заетост, както и безплатен достъп до курса. Формулиране вмъкване търсене и алгоритми за отстраняване на хеш-таблица с три държави елементи. 2. А = Н (ключови) + I * в 3. Ако т (а) = свободна или т (A) = заличава, т (а) = ключ. напиши елемент се добавя стоп елемент 4. I = I + 1, преминете към стъпка 2 · А = Н (ключ) + I * в • Ако т (а) = ключ. След тона (A) = изтрит. ограничителната опора е отстранен • Ако (а) = свободно, ограничителният елемент не е намерен т · I = I + 1, преминете към стъпка 2 · А = Н (ключ) + I * в • Ако т (а) = ключ. ограничителният елемент е намерена • Ако (а) = свободно, ограничителният елемент не е намерен т · I = I + 1, преминете към стъпка 2 Алгоритъмът за търсене на хеш таблица с три държави, не се различава от алгоритъма за търсене на изключение заличавания. Разликата е, че вие трябва да празнуват на свободните и изтрити елементи в организацията на самата маса. Това може да стане като се запазват тези две стойности на ключовото поле. Друго изпълнение може да включва въвеждането на допълнително поле, където неподвижната член състояние. Дължината на тази област може да бъде само два бита, което е достатъчно, за да се определи една от трите държави.