Vai jūs varat izskaidrot hash tabulas darbības principu un kā tajā tiek glabāti dati?

Hēša tabula ir datu struktūra, kas nodrošina ļoti ātru piekļuvi datiem pēc atslēgas. Tās darbības princips ir balstīts uz hēša funkcijas izmantošanu, kas pārvērš atslēgu masīva indeksā, kur tiek glabāta atbilstošā vērtība.

Kad nepieciešams saglabāt atslēgas-vērtības pāri, hēša funkcija aprēķina indeksu, un dati tiek ievietoti šī indeksa masīva šūnā. Meklējot pēc atslēgas, hēša funkcija vēlreiz aprēķina indeksu, un nepieciešamā vērtība tiek atrasta ātri.

Ja divi dažādi atslēgas dod to pašu indeksu (kolīzija), parasti tiek izmantota ķēžu metode: šūnā tiek glabāta visu elementu saraksts ar šo indeksu, un meklēšana notiek šajā sarakstā.

Piemērs Dart (Flutter):

void main() {
  Map<String, int> hashTable = {};
  hashTable['apple'] = 5;
  hashTable['banana'] = 3;

  print(hashTable['apple']); // 5
}

Šeit, Map ir hash tabulas realizācija, kur atslēga ir virkne, un vērtība ir skaitlis.