Pověz o hash tabulkách a jejich základním principu fungování.

Hash tabulka (hash mapa) je datová struktura, která implementuje asociativní pole, mapující klíče na hodnoty.

Princip fungování:

1. Hashování: Pro každý klíč se vypočítá hash kód — číselná hodnota pevné velikosti pomocí hash funkce. Dobrá hash funkce rovnoměrně rozděluje hash kódy po celém rozsahu výstupů.
2. Indexování: Vypočítaný hash kód se používá k určení indexu (pozice) v poli, kde bude uložen odpovídající hodnotu. Často hash(key) % velikost_pole dává finální index.
3. Uložení: V poli se na vypočítaném indexu uloží pár (klíč, hodnota).
4. Vyhledávání: Pro nalezení hodnoty podle klíče se znovu vypočítá hash kód klíče, určí se index a z tohoto indexu se extrahuje hodnota.
5. Kolize: Vznikají, když různé klíče mají stejný hash kód. Existují různé metody řešení kolizí:
   • Metoda řetězení (Separate Chaining): Na každý index pole se udržuje seznam (nebo jiná datová struktura), obsahující všechny páry (klíč, hodnota), jejichž hash kódy vedly k tomuto indexu.
   • Metoda otevřeného adresování (Open Addressing): Při kolizi se hledá jiné volné místo v poli podle určitého pravidla (lineární sondování, kvadratické sondování, dvojité hashování).

Výhody:

• Průměrně operace vkládání, mazání a hledání mají složitost O(1), pokud je hash funkce dobrá a kolize jsou vzácné.

Nevýhody:

• Nejhorší případ výkonu může být O(n), pokud jsou všechny klíče hashovány do stejného indexu (například při špatné hash funkci nebo velkém počtu kolizí).
• Vyžaduje dodatečnou paměť pro pole a možná i pro řešení kolizí.

V Swift jsou hash tabulky implementovány typem Dictionary.

// Příklad použití Dictionary ve Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Přístup přes klíč
let value = myDictionary["banana"] // Získá Optional(2)

// Přidání/aktualizace
myDictionary["grape"] = 4 // Přidá nový pár
myDictionary["apple"] = 10 // Aktualizuje hodnotu pro klíč "apple"

// Odstranění
myDictionary["orange"] = nil // Odstraní pár s klíčem "orange"