10 (1). Hashing. Căutați, activați și excludeți elemente. Funcția de randare (hash) și proprietățile sale.
Colecțiile anterioare considerate pe baza arborilor de căutare vă permit să construiți un tip de date abstract "Tabel". Dar aceste colecții au complexitatea logaritmică a operațiilor, în funcție de numărul de elemente din tabel. Există aplicații care necesită o execuție rapidă și garantată în timp, independentă de cantitatea de date din tabel. În acest caz, se folosește o organizație specială de masă cu un timp constant pentru efectuarea operațiilor - o tabelă de tip hash.
Tabelul hash necesită memorie O (# 9474; m # 9474;), unde m este setul de înregistrări incluse în tabel. Timpul de căutare din tabelul hash este încă O (1).
În tabelul hash, elementului i se atribuie indexul h (k), unde k este cheia elementului h (k) - funcția hash (sau funcția de randomizare). Numărul h (k) se numește valoarea hash a tastei k. Procesul de conversie a unei chei de element într-un index al unei tabele hash se numește hashing.
Funcția Hash (funcție aleatorie) și proprietățile acesteia
1. O funcție hash bună trebuie să furnizeze hashing uniform, adică, pentru orice cheie, toate valorile hash-ului trebuie să fie echivalente.
2. Funcția de randomizare nu trebuie să mențină nicio legătură între valorile cheie. Îndeplinirea acestei cerințe exclude (sau cel puțin diminuează) dependența "calității" randomizării de valorile-cheie utilizate.
4. Funcția hash trebuie să fie deterministă, în sensul că atunci când apelurile repetate cu aceeași cheie trebuie să returneze aceeași valoare hash.
Schema funcției de randomizare este prezentată în Fig.
· Metoda de divizare cu restul (hashing modular) oferă funcții de hash simple și eficiente. Cheia k este atribuită restului divizării k cu m. Funcția hash este calculată ca ecuația h (k) = k mod m.
De exemplu, dacă m = 13, k = 100, atunci h (k) = 9.
· Metoda de multiplicare (multiplicativă) calculează o funcție hash de formula
unde A este o constantă care satisface condiția 0 Avantajul metodei de multiplicare constă în faptul că calitatea funcției hash depinde foarte puțin de alegerea lui m. Dar, de obicei, gradul doi este ales ca m, deoarece în majoritatea computerelor multiplicarea prin puterea a două se realizează rapid, ca o schimbare de cuvânt. Metoda de multiplicare funcționează pentru orice alegere a constantei A. Dar unele valori ale lui A pot fi mai bune decât altele. O valoare bună este numărul Fibonacci. A = 0,6180339887 Să ilustrăm metoda utilizând un exemplu concret. Fie ca mărimea tabelului hash să fie m = 10000. Dacă introduceți cheia 123456, veți obține o valoare hash: funcția hash (cheie șir [4]): integer; f: = ord (tasta [1]) - ord (cheie [2]) + ord (tasta [3]) - ord (cheie [4]); f: = (f * 10000) div (255 * 4); Metode de rezolvare a coliziunilor Procedura de ștergere din tabel este să căutați un element și să îl eliminați din lanțul de suprasarcină. Figura 3.2. Varietăți de metode de rezolvare a coliziunilor Figura 3.3. Rezolvarea coliziunilor la adăugarea elementelor prin metoda lanțului Eșantionarea liniară este redusă la căutarea secvențială a elementelor de tabel cu un anumit pas fix unde i este numărul încercării de a rezolva coliziunea. La un pas egal cu unul, toate elementele după cel curent sunt căutate secvențial. Analiza quadratică diferă de eșantionarea liniară prin faptul că etapa de enumerare a elementelor nu depinde liniar de numărul de încercare pentru a găsi un element liber Activați și căutați Descriim algoritmii de inserție și de căutare pentru metoda de testare liniară. · A = h (cheie) + i * c · Dacă t (a) = este liberă, atunci t (a) = cheie. elementul de înregistrare, elementul de oprire adăugat · I = i + 1, treceți la pasul 2 · A = h (cheie) + i * c · Dacă t (a) = cheie. atunci elementul de oprire este găsit · Dacă t (a) = liber, atunci elementul stop nu este găsit · I = i + 1, treceți la pasul 2 Alegeți pasul q. Când încercăm să adăugăm un element celulei ocupate, începem prin scanarea secvențială a celulelor și așa mai departe până când găsim o celulă liberă. În ea, și scrie elementul. De fapt, căutarea secvențială este un caz special al unei linii lineare, unde q = 1. Pasul q nu este fix, ci se schimbă în mod cvadrat: q = 1,4,9,16. În consecință, atunci când încercăm să adăugăm un element celulei ocupate, începem prin scanarea secvențială a celulelor și așa mai departe până când găsim o celulă liberă. Hashing dublu Se afișează o tabelă de tip hash cu dimensiunea de 13 celule, în care sunt utilizate funcțiile auxiliare: Vrem să introducem cheia 14. Inițial i = 0. Apoi. Dar celula cu indexul 1 este ocupată, deci creștem cu 1 și recalculează valoarea hash. Facem asta până ajungem la o celulă goală. Pentru i = 2 obținem. Numărul de celule 9 este gratuit, așa că scriem cheia noastră acolo. (etapa 2). Cu procedura de îndepărtare, situația nu este atât de simplă, deoarece în acest caz nu va fi procedura de introducere inversă. Faptul este că elementele mesei sunt în două state: libere și ocupate. Dacă ștergeți un element mutându-l într-o stare liberă, după această eliminare, algoritmul de căutare nu va funcționa corect. Să presupunem că tasta elementului de șters are în tabel sinonimele. Dacă elementele cu alte chei au fost plasate în spatele elementului șters ca urmare a rezolvării coliziunilor, atunci căutarea acestor elemente după ștergere va da întotdeauna un rezultat negativ, deoarece algoritmul de căutare se oprește la primul element care este în stare liberă. Puteți corecta această situație în mai multe moduri. · Cea mai simplă dintre ele este de a căuta un element care să nu se găsească până la primul spațiu liber, dar până la sfârșitul mesei. Cu toate acestea, această modificare a algoritmului va nega întregul câștig în accelerarea accesului la date, obținut ca urmare a hashing-ului. · Există o abordare care este lipsită de deficiențele enumerate. Esența lui este că pentru elementele tabelului hash, statul este eliminat. Această stare în timpul căutării este interpretată ca ocupată și în procesul înregistrării în mod liber. Să formuleze algoritmi pentru inserarea unei căutări și ștergeri pentru o tabelă hash care are trei stări elementare. 2. a = h (cheie) + i * c 3. Dacă t (a) = este liber sau t (a) = șters, atunci t (a) = cheie. elementul de înregistrare, elementul de oprire adăugat 4. i = i + 1, mergeți la pasul 2 · A = h (cheie) + i * c · Dacă t (a) = cheie. atunci t (a) = este eliminat. elementul de oprire eliminat · Dacă t (a) = liber, atunci elementul stop nu este găsit · I = i + 1, treceți la pasul 2 · A = h (cheie) + i * c · Dacă t (a) = cheie. atunci elementul de oprire este găsit · Dacă t (a) = liber, atunci elementul stop nu este găsit · I = i + 1, treceți la pasul 2 Algoritmul de căutare pentru o tabelă hash care are trei stări este practic același cu algoritmul de căutare fără a lua în considerare ștergerile. Diferența este că atunci când organizați masa în sine, trebuie să marcați articolele libere și șterse. Puteți face acest lucru rezervând două valori ale câmpului cheie. Un alt exemplu de realizare poate asigura introducerea unui câmp suplimentar în care starea elementului este fixată. Lungimea unui astfel de câmp poate fi doar doi biți, ceea ce este suficient pentru a rezolva una dintre cele trei stări.