Ar galite paaiškinti hash lentelės veikimo principą ir kaip joje saugomi duomenys?

Žemės įdėklas yra duomenų struktūra, kuri užtikrina labai greitą prieigą prie duomenų pagal raktą. Veikimo principas pagrįstas naudojimu hash funkcijos, kuri paverčia raktą į masyvo indeksą, kur saugoma atitinkama reikšmė.

Kai reikia išsaugoti raktas-reikšmė porą, hash funkcija apskaičiuoja indeksą, ir duomenys yra įdedami į masyvo langelį pagal tą indeksą. Paieškos pagal raktą metu, hash funkcija vėl apskaičiuoja indeksą, ir greitai randama reikalinga reikšmė.

Jei du skirtingi raktai duoda tą patį indeksą (kollizija), dažniausiai naudojama grandinėlės metodas: langelyje saugomas visų elementų sąrašas su šiuo indeksu, ir paieška vyksta šiame sąraše.

Pavyzdys Dart (Flutter):

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

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

Čia, Map yra hash lentelės įgyvendinimas, kur raktas yra eilutė, o reikšmė — skaičius.