În informatică, un hashtable este o structură de date pentru stocarea datelor care constă dintr-o listă de valori, numite chei, care sunt asociate cu o listă corespunzătoare de valori, numită matrice. De exemplu, numele unei afaceri poate fi asociat cu adresa sa. De obicei, fiecare valoare din matrice are un număr de poziție numit hash. Funcția hash este, în general, un set de instrucțiuni sau un algoritm care mapează fiecare valoare cheie la un hash – conectând numele companiei la adresa sa, numărul de telefon și categoria sa de afaceri, de exemplu. Scopul funcției hash este de a atribui fiecărei taste unei valori corespunzătoare unice din matrice; aceasta este denumită în mod obișnuit hashing. Funcțiile hash trebuie să fie formatate corespunzător pentru ca un hashtable să funcționeze corect.
Performanța unui tabel hash pe un set de date depinde de eficiența funcției de hash. O funcție hash bună asigură de obicei o căutare uniformă a cheilor și o distribuție uniformă a mapărilor în matricea corespunzătoare. O coliziune hash are loc atunci când două chei sunt atribuite aceleiași valori corespunzătoare. Când are loc o coliziune hash, funcția hash este de obicei executată din nou până când este găsită o valoare corespunzătoare unică; acest lucru duce de obicei la timpi de hashing mai lungi. Deși numărul de chei dintr-o tabelă hash este de obicei fix, uneori pot exista chei duplicate. Chiar și așa, un hashtable bine conceput are funcții hash eficiente care mapează fiecare cheie la o valoare corespunzătoare unică din matrice.
Uneori, funcțiile hash ineficiente dintr-o tabelă hash pot produce, de asemenea, un grup de mapări. Dacă o funcție hash creează un grup de mapări pentru cheile existente, acest lucru poate crește timpul necesar pentru a căuta valorile corespunzătoare. Acest lucru poate încetini hashing-ul pentru cheile viitoare, deoarece majoritatea funcțiilor hash caută în general următoarea poziție disponibilă în matrice. Dacă un grup mare de valori a fost deja atribuit, de obicei ar dura mult mai mult pentru a căuta o valoare nealocată pentru o nouă cheie.
Factorul de încărcare este un alt concept legat de eficiența unei funcții hash; factorul de încărcare este cantitatea de hashing-uri deja existente în raport cu dimensiunea totală a matricei corespunzătoare dintr-un hashtable. De obicei, este definit prin împărțirea numărului de chei deja atribuite la dimensiunea matricei corespunzătoare. Pe măsură ce factorul de încărcare crește, o funcție hash bună va menține în mod normal un număr constant de coliziuni și grupuri până la un anumit punct. Adesea, acest prag poate fi folosit pentru a determina cât de eficientă este o funcție hash cu un anumit număr de taste și când poate fi necesară o nouă funcție hash.
Mulți cercetători în informatică s-au străduit să producă funcția hash perfectă – una care nu produce coliziuni sau clustere, având în vedere un factor de încărcare în creștere. În teorie, cheia producerii unui tabel hash perfect este producerea unei funcții hash perfecte. În general, cercetătorii cred că o funcție hash perfectă ar trebui să aibă performanță constantă – numărul de coliziuni și clustere – cu un factor de încărcare în creștere. În cel mai rău caz, o funcție de hash perfectă ar permite în continuare hashing constant fără a atinge un prag.