Kas ir hash tabula?

Hesh tabula ir datu struktūra, kas īsteno asociatīvo masīvu (vārdu krājumu). Tā glabā "atslēga-vertība" pārus, kur atslēgas ir unikālas.

Pamatprincipi:

• Hesh funkcija: Pārvērš atslēgu skaitlī (hesh kodā vai indeksā). Šis indekss norāda uz glabāšanas vietu masīvā (groziņā).
• Masyvs (groziņi): Faktiska "atslēga-vertība" pāru glabāšana.
• Kolīzijas: Situācija, kad dažādi atslēgas ģenerē to pašu hesh kodu.

Kolīziju risinājums:

• Atdalīšanas metode (Separate chaining): Katram groziņam ir saraksts (vai cita datu struktūra) ar elementiem ar to pašu hesh kodu.
• Atvērta adresēšana (Open addressing): Kolīzijas gadījumā meklē brīvu groziņu, izmantojot dažādas stratēģijas (līnijas sondēšana, kvadrātiska sondēšana, dubultā heshēšana).

Īpašības:

• Ātra piekļuve: Ideālā gadījumā O(1) operācijām pievienošana, meklēšana un dzēšana.
• Atkarība no hesh funkcijas: Hesh funkcijas kvalitāte un kolīziju risināšanas stratēģija būtiski ietekmē veiktspēju.
• Atmiņas izmantošana: Prasa papildu atmiņu groziņu masīvam.

Izmantošana QA:

• Testa datu glabāšana (atslēga - parametra nosaukums, vērtība - gaidītā vai faktiskā vērtība).
• Elementu unikāluma pārbaude (piemēram, lietotāju ID).
• Kešu (cache) īstenošana.