Môžete vysvetliť princíp fungovania hash tabuľky a ako sa v nej ukladajú údaje?

Hash tabuľa je dátová štruktúra, ktorá zabezpečuje veľmi rýchly prístup k údajom pomocou kľúča. Princíp jej fungovania spočíva v použití hash funkcie, ktorá premieňa kľúč na index poľa, kde je uložená príslušná hodnota.

Keď je potrebné uložiť pár kľúč-hodnota, hash funkcia vypočíta index a údaje sú umiestnené v bunke poľa na tomto indexe. Pri vyhľadávaní podľa kľúča hash funkcia znova vypočíta index a rýchlo nájde potrebnú hodnotu.

Ak dva rôzne kľúče dávajú rovnaký index (kolízia), zvyčajne sa používa metóda reťazcov: v bunke je uložený zoznam všetkých prvkov s týmto indexom a vyhľadávanie prebieha v tomto zozname.

Príklad v Dart (Flutter):

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

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

Tu je Map implementáciou hash tabuľky, kde je kľúč reťazec a hodnota je číslo.