Hash tablica

Izvor: Wikipedija
Skoči na: orijentacija, traži
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 tabela 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.[1]

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[uredi VE | uredi]

Asocijativne tablice[uredi VE | uredi]

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[uredi VE | uredi]

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[uredi VE | uredi]

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.

Prednosti[uredi VE | uredi]

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.

Izvori[uredi VE | uredi]

  1. Donald Knuth (1998.). The Art of Computer Programming', 2. izd., str. 513.–558., Addison-Wesley. ISBN 0-201-89685-0