User:CehajicIdana123/sandbox

Heš tabela i heš funkcija

Heš tabela (eng. Hash table) ili heš mapa (eng. Hashmap ) je jedna struktura podataka koja koristi heš funkciju (eng. Hash function) za učinkovito preslikavanje određenih ključeva u njima pridružene vrijednosti. Na primjer imena ljudi u telefonske brojeve. Heš tabela se koristi za transformiranje  ključa u indeks (heš), to jeste, mjesto u nizu elemenata gdje treba tražiti odgovarajuću vrijednost.

Vremenska složenost Heš tabele

Heš funkcija je funkcija koja vrši mapiranje ključa u opseg indeksa (adresa) u nizu. Ponekad se ovaj metod heširanja naziva još i tehnikom rasutog adresiranja ili tehnikom direktnog adresiranja. Heš funkcija je funkcija za identificiranje podataka. Takav sažetak naziva se heš vrijednost ili jednostavno heš, a proces izračunavanja te vrijednosti naziva se heširanje (eng. hashing). Heš funkcije koje su injekcija i sirjekcija, a time i bijekcija nazivaju se randomizirajuće funkcije. Domena heš funkcija u većini slučajeva veća je od kodomene, pa nisu bijekcija (citat Wikipedia). Heš funkcija sabiija proizvoljnu poruku na fiksnu veličinu. Najčešće se podrazumijeva da je heš funkcija javna  i ne sadrži ključ.

• Neka je T[i], 0 ≤  i ≤ n-1, heš tabela sa n ulaza i neka ključevi pripadaju nekom skupu mogućih vrijednosti S, tako da K ∈ S. Broj mogućih vrijednosti ključa je tipično veći ili čak mnogo veći od broja ulaza u tabeli. Neka je h heš funkcija koja vrši mapiranje ključeva u adresni prostor tabele. Ovo je ilustrovano slikom 1.1. Tada funckija primijenjena na neki ključ K daje matičnu adresu ključa K, tako da je i = h ( K ).

• 

  Slika 1.1.

Jedan zadatak heš funkcije je kompresija skupa vrijednosti ključeva na manji opseg indeksa ulaza tabele. Prema tome, moguće je da heš funkcija za dva različita ključa ima istu vrijednost, to jeste, da vrijedi da je h(K_i) = h(K_j), K_i ≠ K_j ­.