Beszélj a hash-táblákról és fő működési elvükről.

A hash-tábla (hash térkép) egy adatszerkezet, amely egy asszociatív tömböt valósít meg, kulcsokat értékekhez rendel.

Működési elv:

1. Hash-elés: Minden kulcs esetén kiszámítunk egy hash-kódot — egy fix méretű numerikus értéket egy hash-függvény segítségével. Egy jó hash-függvény egyenletesen osztja el a hash-kódokat a kimeneti tartományon belül.
2. Indexelés: A kiszámított hash-kódot arra használjuk, hogy meghatározzuk az indexet (pozíciót) a tömbben, ahol a megfelelő érték tárolódik. Gyakran, hash(key) % tömb_méret adja a végső indexet.
3. Tárolás: A tömbben, a kiszámított indexen, egy (kulcs, érték) pár tárolódik.
4. Keresés: Egy érték megtalálásához a kulcs alapján, újra kiszámítjuk a kulcs hash-kódját, meghatározzuk az indexet, és ebből az indexből kivesszük az értéket.
5. Ütközések: Akkor fordulnak elő, amikor különböző kulcsok ugyanazt a hash-kódot kapják. Különböző módszerek léteznek az ütközések kezelésére:
   • Külön láncolás (Separate Chaining): Minden tömbindexen egy lista (vagy más adatstruktúra) tartalmazza az összes (kulcs, érték) párt, amelyek hash-kódja ehhez az indexhez vezetett.
   • Nyitott címzés (Open Addressing): Ütközés esetén más szabad helyet keresünk a tömbben egy meghatározott szabály szerint (lineáris szondázás, kvadratikus szondázás, dupla hash-elés).

Előnyök:

• Átlagosan az beszúrás, törlés és keresés műveletek komplexitása O(1), ha a hash-függvény jó és az ütközések ritkák.

Hátrányok:

• A legrosszabb esetben a teljesítmény O(n) lehet, ha minden kulcs ugyanabba az indexbe hash-elt (például rossz hash-függvény vagy sok ütközés esetén).
• További memória szükséges a tömb számára, és esetleg az ütközések kezeléséhez.

Swiftben a hash-táblák a Dictionary típusban vannak megvalósítva.

// Dictionary használatának példája Swiftben
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Hozzáférés kulcs alapján
let value = myDictionary["banana"] // Optional(2) értéket kap

// Hozzáadás/frissítés
myDictionary["grape"] = 4 // Új párt ad hozzá
myDictionary["apple"] = 10 // Frissíti az "apple" kulcs értékét

// Törlés
myDictionary["orange"] = nil // Törli az "orange" kulcsú párt