Kas yra žemės lentelė?

Hesh lentelė yra duomenų struktūra, kuri įgyvendina asociatyvųjį masyvą (žodyną). Ji saugo "raktas-reikšmė" poras, kur rakta yra unikali.

Pagrindiniai principai:

• Hesh funkcija: Paverčia raktą į skaičių (hesh kodą arba indeksą). Šis indeksas nurodo saugojimo vietą masyve (krepšelyje).
• Masyvas (krepšeliai): Faktinis "raktas-reikšmė" porų saugojimas.
• Kolizijos: Situacija, kai skirtingi raktai generuoja tą patį hesh kodą.

Kolizijų sprendimas:

• Atjungimo metodas (Separate chaining): Kiekviename krepšelyje saugoma sąrašas (ar kita duomenų struktūra) elementų su tuo pačiu hesh kodu.
• Atviras adresavimas (Open addressing): Kolizijos atveju ieškoma laisvo krepšelio naudojant įvairias strategijas (linijinis sondavimas, kvadratinis sondavimas, dvigubas heshavimas).

Savybės:

• Greitas prieiga: Idealiu atveju O(1) įterpimui, paieškai ir ištrynimui.
• Priklausomybė nuo hesh funkcijos: Hesh funkcijos kokybė ir kolizijų sprendimo strategija stipriai veikia našumą.
• Atminties naudojimas: Reikalauja papildomos atminties krepšelių masyvui.

Naudojimas QA:

• Testinių duomenų saugojimas (raktas - parametro pavadinimas, reikšmė - tikėtina arba faktinė reikšmė).
• Elementų unikalumo patikrinimas (pvz., naudotojų ID).
• Krovinių (cache) įgyvendinimas.