Hash tablica

Mali telefonski imenik kao hash tablica

U računalstvu, hash tablica (eng. hash table) ili hash mapa (eng. Hash map) je podatkovna struktura koja rabi hash funkciju za učinkovito preslikavanje određenih ključeva (na primjer imena ljudi) u njima pridružene vrijednosti (na primjer telefonske brojeve). Hash funkcija se koristi za transformiranje ključa u indeks (hash) to jest mjesto u nizu elemenata gde treba tražiti odgovarajuću vrijednost.

U najboljem slučaju, hash funkcija preslikava svaki mogući ključ u zaseban indeks, ali je to u praksi gotovo nemoguće. Većina implementacija hash tablica podrazumijeva da su hash kolizije — parovi različitih ključeva s istim hash vrijednostima — obična pojava, i na neki način se brine da se ovaj problem svlada.

U dobro dimenzioniranoj hash tablici, prosječna cijena (broj računalnih naredbi) svakog pronalaženja ne ovisi o broju elemenata uskladištenih u tablici. Mnoge implementacije hash tablica također omogućuju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji.

U mnogim okolnostima, hash tablice se pokazuju učinkovitijim od stabala pretrage ili drugih tabličnih struktura. Zato su hash tablice u širokoj upotrebi u svim vrstama računskog softvera.

Uporaba

Asocijativne tablice

Hash tablice se obično upotrebljavaju za implementaciju svih vrsta tablica koje se čuvaju u memoriji. Koriste se za implementaciju asocijativnih nizova (nizova čiji su indeksi proizvoljne nizove ili drugi kompliciraniji objekti), posebno u interpretiranim programskim jezicima kao što su gawk i perl.

Indeksi u bazama podataka

Hash tablice mogu se koristiti i za perzistentne strukture podataka koje su smještene na disku, i za indekse baza podataka, iako su balansirana stabla popularnija za ove primjene.

Skupovi

Osim vraćanja vrijednosti koja odgovara danom ključu, mnoge implementacije hash tablica mogu također odgovoriti i na pitanje postoji li takav unos ili ne.

Zbog toga se ove strukture mogu rabiti i za implementaciju skupa, koji odgovara na pitanje postoji li dani ključ u nekom skupu ključeva. U ovom se slučaju struktura može pojednostaviti eliminiranjem svih dijelova koji se tiču vrijednosti koje odgovaraju ključevima. Hashiranje se može koristiti za implementaciju bilo statičkih, bilo dinamičkih skupova.

Hashiranje

Hashiranje predstavlja koji omogućuje generiranje jedne ili više vrijednosti iz niza teksta pomoću matematičke formule, čime se dobije kriptirana vrijednost koja podatke čini sigurnima.

Hashiranje je jednosmjerna funkcija enkripcije koja uzima podatke bilo koje veličine i izlazi vrijednost fiksne veličine. Hashiranje je slično enkripciji i soljenju.

Prednosti

Glavna prednost hash tablice nad drugim tabličnim strukturama podataka je njena brzina. Ova je prednost uočljivija kada je broj podataka u tablici velik (tisuće ili više). Hash tablice su posebno učinkovite kada se maksimalna količina podataka može predvidjeti unaprijed, tako da se veličina strukture može unaprijed alocirati tako da bude optimalna, i ne mora se kasnije mijenjati.

Ako su svi parovi ključeva-vrijednosti fiksirani i poznati unaprijed (pa dodavanja i brisanja nisu dopuštena), prosječna cijena pretrage može se smanjiti pažljivim izborom hash funkcije, veličine tablice i unutrašnjih struktura podataka. Štoviše, tada je moguće napraviti hash funkciju koja ne stvara kolizije. U ovom slučaju ključeve nije potrebno čuvati u tablici.

Vidi

• hashiranje