Hash tablica

Mali telefonski imenik kao hash tablica

U računarstvu, 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.

Idealno, hash funkcija bi trebala preslikavati svaki mogući ključ u zaseban indeks, ali je ovaj cilj u praksi najčešće nedostupan. Većina implementacija hash tabela podrazumijeva da su hash kolizije — parovi različitih ključeva sa istim hash vrijednostima — normalna pojava, i na neki način se brine da se ovaj problem prevaziđe.

U dobro dimenzioniranoj hash tablici, prosečna cijena (broj računalnih instrukcija) svakog pronalaženja je neovisna od broja elemenata uskladištenih u tablici. Mnoge implementacije hash tablica također omogućavaju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji.

U mnogim situacijama, hash tablice se pokazuju efikasnijim od stabala pretrage ili svih drugih tabelarnih struktura. Zato su hash tabele u širokoj upotrebi u svim vrstama računskog softvera.

Uporaba

Asocijativne tablice

Hash tablice se obično koriste 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 datom ključu, mnoge implementacije hash tablica mogu također odgovoriti i na pitanje da li takav unos postoji ili ne.

Zbog toga se ove strukture mogu koristiti i za implementaciju skupa, koji odgovara na pitanje da li dati ključ postoji u nekom skupu ključeva. U ovom slučaju struktura se može da 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.

Prednosti

Glavna prednost hash tablice nad drugim tabelarnim strukturama podataka je njena brzina. Ova prednost je uočljivija kada je broj podataka u tabeli veliki (tisuće ili više). Hash tablice su posebno efikasne kada se maksimalna količina podataka može predvjeti 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 dozvoljena), 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 tabeli.