Hash tablica
From Wikipedia, the free encyclopedia
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.[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.