Porozprávaj o hash tabuľkách a ich hlavnom princípe fungovania.

Hash-tabulka (hash-map) je dátová štruktúra, ktorá implementuje asociatívny poľ a mapuje kľúče na hodnoty.

Hlavný princíp práce:

1. Hashovanie: Pre každý kľúč sa vypočíta hash-kód — číselná hodnota pevného veľkosti pomocou hash funkcie. Dobrá hash funkcia rovnomerne rozdeľuje hash kódy po celom rozsahu výstupov.
2. Indexovanie: Vypočítaný hash kód sa použije na určenie indexu (polohy) v poli, kde bude uložená príslušná hodnota. Často hash kód modulo veľkosti poľa (hash(key) % array_size) dáva konečný index.
3. Uloženie: V poli na vypočítanom indexe je uložená dvojica (kľúč, hodnota).
4. Hľadanie: Pre nájdenie hodnoty podľa kľúča sa opäť vypočíta hash kód kľúča, určí sa index a podľa tohto indexu sa extrahuje hodnota.
5. Kolízie: Vznikajú, keď rôzne kľúče majú rovnaký hash kód. Existujú rôzne metódy na riešenie kolízií:
   • Metóda reťazcov (Separate Chaining): Pre každý index poľa sa udržiava zoznam (alebo iná dátová štruktúra), obsahujúci všetky dvojice (kľúč, hodnota), ktorých hash kódy viedli k tomuto indexu.
   • Metóda otvorenej adresácie (Open Addressing): Pri kolízii sa hľadá iné voľné miesto v poli podľa určitého pravidla (lineárne sondovanie, kvadratické sondovanie, dvojité hashovanie).

Výhody:

• Priemerné operácie vkladania, odstraňovania a hľadania majú zložitosť O(1), ak je hash funkcia dobrá a kolízie sú zriedkavé.

Nevýhody:

• Najhorší prípad výkonu môže byť O(n), ak sú všetky kľúče hashované do rovnakého indexu (napríklad pri zlej hash funkcii alebo veľkom počte kolízií).
• Vyžaduje si dodatočnú pamäť pre pole a možno aj na riešenie kolízií.

V Swifte sú hash-tabulky implementované typom Dictionary.

// Príklad použitia Dictionary v Swifte
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Prístup podľa kľúča
let value = myDictionary["banana"] // Získa Optional(2)

// Pridanie/aktualizácia
myDictionary["grape"] = 4 // Pridá novú dvojicu
myDictionary["apple"] = 10 // Aktualizuje hodnotu pre kľúč "apple"

// Odstránenie
myDictionary["orange"] = nil // Odstráni dvojicu s kľúčom "orange"