Heš tabela

Mali telefonski imenik u vidu heš tabele.

U računarstvu, heš tabela (engl. Hash table) ili heš mapa (engl. Hash map) je struktura podataka koja koristi heš funkciju za efikasno preslikavanje određenih ključeva (na primer imena ljudi) u njima pridružene vrednosti (na primer telefonske brojeve). Heš funkcija se koristi za transformisanje ključa u indeks (heš) to jest mesto u nizu elemenata gde treba tražiti odgovarajuću vrednost.

Idealno, heš funkcija bi trebalo da preslikava svaki mogući ključ u zaseban indeks, ali ovaj cilj je u praksi najčešće nedostupan. Većina implementacija heš tabela podrazumeva da su heš kolizije — parovi različitih ključeva sa istim heš vrednostima — normalna pojava, i na neki način se stara da se ovaj problem prevaziđe.

U dobro dimenzionisanoj heš tabeli, prosečna cena (broj računarskih instrukcija) svakog pronalaženja je nezavisna od broja elemenata uskladištenih u tabeli. Mnoge implementacije heš tabela takođe omogućavaju proizvoljna unošenja i brisanja parova ključeva i vrednosti uz konstantnu prosečnu (amortizovanu) cenu po operaciji.

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

Upotrebe

Asocijativne tabele

Heš tabele se obično koriste za implementaciju svih vrsta tabela koje se čuvaju u memoriji. Koriste se za implementaciju asocijativnih nizova (nizova čiji su indeksi proizvoljne niske ili drugi komplikovaniji objekti), posebno u interpretiranim programskim jezicima kao što su gawk i perl.

Indeksi u bazama podataka

Heš tabele mogu da se koriste i za perzistentne strukture podataka koje su smeštene na disku, i za indekse baza podataka, mada su balansirana stabla popularnija za ove primene.

Skupovi

Osim vraćanja vrednosti koja odgovara datom ključu, mnoge implementacije heš tabela mogu takođe da odgovore na pitanje da li takav unos postoji ili ne.

Zbog toga ove strukture mogu da se koriste za impelentaciju skupa, koji prosto odgovara na pitanje da li dati ključ postoji u nekom skupu ključeva. U ovom slučaju struktura može da se pojednostavi eliminisanjem svih delova koji se tiču vrednosti koje odgovaraju ključevima. Hešovanje može da se koristi za implementaciju bilo statičkih, bilo dinamičkih skupova.

Prednosti

Glavna prednost heš tabela nad drugim tabelarnim strukturama podataka je njena brzina. Ova prednost je uočljivija kada je broj podataka u tabeli veliki (hiljade ili više). Heš tabele su posebno efikasne kada maksimalna količina podataka može da se predvidi unapred, tako da veličina strukture može unapred da se alocira tako da bude optimalna, i ne mora posle da se menja.

Ako su svi parovi ključeva-vrednosti fiksirani i poznati unapred (pa dodavanja i brisanja nisu dozvoljena), prosečna cena pretrage može da se smanji pažljivim izborom heš funkcije, veličine tabele i unutrašnjih struktura podataka. Štaviše, tada je moguće napraviti heš funkciju koja ne stvara kolizije. U ovom slučaju ključeve nije potrebno čuvati u tabeli.

Literatura

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „11: Hash Tables”. Introduction to Algorithms (2. izd.). -IT Press and McGraw-Hill. str. 221-252. ISBN 978-0-262-53196-2. 
• Knuth, Donald (1998). „6.4: Hashing,”. The Art of Computer Programming'. 3: Sorting and Searching (2nd izd.). Addison-Wesley. str. 513—558. ISBN 978-0-201-89685-5.