U informatici, hashtable je struktura podataka za pohranu podataka koja se sastoji od popisa vrijednosti, nazvanih ključevi, koji se uparuju s odgovarajućim popisom vrijednosti, koji se naziva niz. Na primjer, naziv tvrtke može biti uparen s njegovom adresom. Obično svaka vrijednost u nizu ima broj pozicije koji se naziva hash. Hash funkcija je općenito skup uputa ili algoritam koji preslikava svaku vrijednost ključa u hash — povezujući naziv tvrtke s adresom, telefonskim brojem i poslovnom kategorijom, na primjer. Svrha hash funkcije je dodijeliti svakom ključu jedinstvenu odgovarajuću vrijednost u nizu; ovo se obično naziva haširanjem. Hash funkcije moraju biti pravilno formatirane da bi hashtable ispravno funkcionirala.
Izvedba hashtable na skupu podataka ovisi o učinkovitosti njezine hash funkcije. Dobra hash funkcija obično osigurava ujednačeno traženje ključeva i ravnomjernu distribuciju preslikavanja u odgovarajućem nizu. Hash kolizija se događa kada se dva ključa dodijele istoj odgovarajućoj vrijednosti. Kada dođe do sudara raspršivanja, hash funkcija se obično ponovno izvršava dok se ne pronađe jedinstvena odgovarajuća vrijednost; to obično rezultira duljim vremenima raspršivanja. Iako je broj ključeva u hashtable obično fiksiran, ponekad mogu postojati duplicirani ključevi. Čak i tako, dobro dizajnirana hashtable ima učinkovite hash funkcije koje mapiraju svaki ključ u jedinstvenu odgovarajuću vrijednost u nizu.
Ponekad, neučinkovite hash funkcije u hashtable također mogu proizvesti klaster preslikavanja. Ako hash funkcija stvara klaster preslikavanja za postojeće ključeve, to može povećati količinu vremena potrebnog za traženje odgovarajućih vrijednosti. To može usporiti raspršivanje za buduće ključeve jer većina hash funkcija općenito traži sljedeću dostupnu poziciju u nizu. Ako je već dodijeljen veliki skup vrijednosti, obično bi trebalo mnogo duže da se traži nedodijeljena vrijednost za novi ključ.
Faktor opterećenja je još jedan koncept povezan s učinkovitosti hash funkcije; faktor opterećenja je količina već postojećih hashiranja u odnosu na ukupnu veličinu odgovarajućeg niza u hashtable. Obično se definira dijeljenjem broja već dodijeljenih tipki s veličinom odgovarajućeg niza. Kako se faktor opterećenja povećava, dobra hash funkcija će normalno i dalje održavati konstantan broj sudara i klastera do određene točke. Često se ovaj prag može koristiti za određivanje koliko je učinkovita hash funkcija s danim brojem ključeva i kada može biti potrebna nova hash funkcija.
Mnogi istraživači računalne znanosti nastojali su proizvesti savršenu hash funkciju – onu koja ne proizvodi kolizije ili klastere s obzirom na sve veći faktor opterećenja. U teoriji, ključ za stvaranje savršene hashtable je proizvesti savršenu hash funkciju. Općenito, istraživači vjeruju da bi savršena hash funkcija trebala imati stalne performanse – broj sudara i klastera – uz sve veći faktor opterećenja. U najgorem slučaju, savršena hash funkcija i dalje bi omogućila konstantno raspršivanje bez dostizanja praga.