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.[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 | uredi kôd]
Asocijativne tablice[uredi | uredi kôd]
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 | uredi kôd]
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 | uredi kôd]
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[uredi | uredi kôd]
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.[2]
Hashiranje je jednosmjerna funkcija enkripcije koja uzima podatke bilo koje veličine i izlazi vrijednost fiksne veličine. [3] Hashiranje je slično enkripciji i soljenju.[4]
Prednosti[uredi | uredi kôd]
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[uredi | uredi kôd]
Izvori[uredi | uredi kôd]
- ↑
Donald Knuth. 1998. The Art of Computer Programming'. 3: Sorting and Searching 2. izd. izdanje. Addison-Wesley. str. 513.–558. ISBN 0-201-89685-0 Nepoznati parametar
|note=
zanemaren (pomoć) - ↑ Google Ads pomoć Hashiranje: definicija / pristupljeno 26. srpnja 2020.
- ↑ Heritage Offshore Inačica izvorne stranice arhivirana 26. srpnja 2020. Brayan Jackson: Što je kontrolni zbroj i kako ga koristiti? (Upute za Windows i Mac) / pristupljeno 26. srpnja 2020.
- ↑ Heritage Offshore Brayan Jackson / Šifriranje, hashing, soljenje – u čemu je razlika? / pristupljeno 26. srpnja 2020.