No kā sastāv hash tabula?

Hash tabula sastāv no fiksēta izmēra masīva (kaste vai slota) un hash funkcijas.

• Masīvs (Kastes/Slotas): Attēlo secību no šūnām, kurās tiek glabāti "atslēga-vērtība" pāri. Masīva izmērs nosaka iespējamās vietas elementu glabāšanai.

• Hash funkcija: Pārvērš atslēgu veselos skaitļos (hash kods), kas tiek izmantots, lai noteiktu šūnas indeksu masīvā (kastē), kur tiks glabāta vai no kuras tiks izvilkta atbilstošā vērtība.

Papildus var būt:

• Saskares risināšanas stratēģija: Mehānisms situācijām, kad dažādi atslēgas ģenerē to pašu hash kodu un norāda uz to pašu masīva šūnu. Biežākās stratēģijas:
  • Saites ķēde (Separate Chaining): Katras masīva šūnas glabā norādi uz saistītu sarakstu (vai citu datu struktūru), kas satur visus "atslēga-vērtība" pārus, kuru hash kodi norāda uz šo šūnu.
  • Atvērta adrešu izmantošana: Gadījumā, ja ir sadursme, tiek meklēta brīva šūna masīvā pēc noteiktas noteikuma (piemēram, lineāra vai kvadrātiska sondēšana).