Funcție hash

În sens matematic, funcțiile hash (clasă de funcții denumite în lucrări de specialitate și funcții de dispersie sau funcții de rezumat) sunt funcții definite pe o mulțime cu multe elemente (posibil infinită) cu valori într-o mulțime cu un număr fix și mai redus de elemente. Funcțiile hash nu sunt inversabile. În informatică, funcțiile hash sunt folosite pentru a accelera căutările în tabele, cum este cazul în bazele de date mari sau comparările de date. Valoarea unei funcții hash este denumită rezumat, valoare hash, cod hash, sumă hash sau doar hash. De asemenea, pot fi folosite drept sume de control sau coduri corectoare de erori (deși nu trebuie confundate cu acestea două), sau, în criptografie, drept componente în schemele de semnătură digitală.

O funcție hash poate lega două sau mai multe chei de la aceeași valoare hash. În multe aplicații, este de dorit minimalizarea șansei apariției unor astfel de coliziuni, ceea ce înseamnă că funcția hash trebuie să lege cheile de valorile hash cât mai uniform posibil. De asemenea, în funcție de aplicație, alte proprietăți pot fi necesare. Deși ideea a fost concepută în anii 1950, proiectarea optimă a funcțiilor hash este încă un subiect activ de cercetare și discuție. Funcțiile hash sunt utilizate și ca sume de control sau funcții hash criptografice, dar nu trebuie confundate cu caracterele de verificare, amprentele numerice, funcțiile de randomizare, codurile de corectare a erorilor. Deși aceste concepte se suprapun într-o oarecare măsură, fiecare are propriile sale utilizări și cerințele și este proiectat și optimizat în mod diferit.

Proprietăți

Funcții hash bune, în sensul originar al termenului, sunt de obicei necesare pentru a satisface anumite proprietăți enumerate mai jos.

Cost scăzut

Costul de calcul a unei funcții hash trebuie să fie suficient de mic pentru a face soluția de criptare bazată pe ea mai eficientă decât alte abordări alternative. De exemplu, un arbore binar autoechilibrat poate localiza un element într-o tabelă de sortat cu n elemente efectuând O(log n) comparații de cheie. Prin urmare, o soluție ce are la bază un tabel de dispersie va fi mai eficient decât un arbore binar de auto-echilibrare în cazul în care numărul de articole este mare și funcția hash produce coliziuni puține și mai puțin eficientă în cazul în care numărul de articole este mic și funcția hash este complexă.

Determinism

O funcție hash trebuie să fie deterministă, în sensul că, pentru o valoare de intrare dată, ea trebuie să genereze întotdeauna aceeași valoare hash. Cu alte cuvinte, trebuie să fie o funcție de datele trunchiate, în sensul matematic al termenului. Această cerință exclude funcții de hash care depind de parametri externi variabili, cum ar fi generatoare de numere pseudoaleatoare sau de ora din zi. De asemenea, exclude funcții care depind de adresa de memorie a obiectului fiind trunchiată, în cazul în care se poate modifica în timpul prelucrării, deși uneori elementul poate fi resupus funcției hash.

Uniformitate

O funcție hash bună ar trebui să lege valorile de intrare cât mai uniform posibil de valorile de ieșire ale sistemului. Aceasta înseamnă că fiecare valoare hash din gama de ieșire ar trebui să fie generată cu aproximativ aceeași probabilitate. Motivul pentru această ultimă cerință este faptul că prețul metodelor bazate pe hash urcă brusc odată ce numărul de coliziuni — perechile de intrări care sunt legate la aceeași valoare hash — crește. Practic, în cazul în care unele valori hash sunt mult mai probabil să apară decât altele, o fracțiune mai mare a operațiunilor de căutare va trebui să caute printr-un set mai mare de intrări în tabelă.

Domeniu de variație mare

În multe aplicații, gama de valori hash poate fi diferită pentru fiecare rulare a programului, sau se pot schimba în timpul rulării (de exemplu, atunci când tabela hash trebuie să fie extinsă). În aceste situații, este nevoie de o funcție hash care are doi parametri de date de intrare - Z, și n numărul de valori hash permise.

Normalizarea datelor

În unele aplicații, datele de intrare pot conține caracteristici care sunt irelevante pentru scopuri de comparație. De exemplu, atunci când caută un nume personal, acesta poate fi de dorit să ignore distincția între litere majuscule și minuscule. Pentru astfel de date, se utilizează o funcție hash compatibilă cu criteriul de echivalență a datelor folosit: orice două intrări care sunt considerate echivalente trebuie să producă aceeași valoare hash. Acest lucru poate fi realizat prin normalizarea intrării (în exemplul de mai sus modificând toate caracterele în majuscule).

Originile termenului

Termenul de hash se traduce, prin analogie cu sensul său non-tehnic, prin „taie și se amestecă”. Într-adevăr, funcțiile hash tipice, cum ar fi utilizarea operației „modulo”, „taie” domeniul de intrare în mai multe subdomenii care se „amestecă” în gama de ieșire pentru a îmbunătăți uniformitatea de distribuție a cheii.

Donald Knuth constată că Hans Peter Luhn de la IBM pare să fi fost primul care a folosit conceptul, într-o notă din ianuarie 1953, și că Robert Morris a folosit termenul într-un document studiu care a ridicat termenul de la jargonul tehnic la terminologia formală.