Pasakok apie maišos lenteles ir jų pagrindinį veikimo principą.

Žemės-lauko lentelė (hash-map) yra duomenų struktūra, įgyvendinanti asociatyvų masyvą ir susiejanti raktus su reikšmėmis.

Pagrindinis darbo principas:

1. Hashavimas: Kiekvienam raktui apskaičiuojamas hash kodas — skaitinė reikšmė, naudojant hash funkciją. Gera hash funkcija tolygiai paskirsto hash kodus visame išėjimo diapazone.
2. Indeksavimas: Apskaičiuotas hash kodas naudojamas indeksui (pozicijai) masyve nustatyti, kur bus saugoma atitinkama reikšmė. Dažnai hash kodas imamas moduliu iš masyvo dydžio (hash(key) % array_size), gaunant galutinį indeksą.
3. Saugojimas: Masyve pagal apskaičiuotą indeksą saugomas (raktas, reikšmė) pora.
4. Paieška: Norint rasti reikšmę pagal raktą, vėl apskaičiuojamas rakto hash kodas, nustatomas indeksas, ir iš šio indekso išgaunama reikšmė.
5. Kolizijos: Atsiranda, kai skirtingi raktai turi tą patį hash kodą. Yra įvairių metodų kolizijoms spręsti:
   • Atskirų grandinių metodas (Separate Chaining): Kiekviename masyvo indekse saugomas sąrašas (ar kita duomenų struktūra), kuriame yra visi (raktas, reikšmė) poros, kurių hash kodai nulėmė tą indeksą.
   • Atvirosios adresacijos metodas (Open Addressing): Kolizijos atveju ieškoma kitos laisvos vietos masyve pagal tam tikrą taisyklę (tiesinė sondavimas, kvadratinis sondavimas, dvigubas hashavimas).

Privalumai:

• Vidutiniškai įterpimo, ištrynimo ir paieškos operacijos turi sudėtingumą O(1), jei hash funkcija gera ir kolizijos retos.

Trūkumai:

• Blogiausiu atveju našumas gali būti O(n), jei visi raktai yra hash'inami į tą patį indeksą (pavyzdžiui, blogos hash funkcijos ar didelio kolizijų skaičiaus atveju).
• Reikalinga papildoma atmintis masyvui ir galbūt kolizijų sprendimui.

Swift kalboje hash-lentelės įgyvendintos Dictionary tipu:

// Pavyzdys, kaip naudoti Dictionary Swift kalboje
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Prieiga per raktą
let value = myDictionary["banana"] // Gauna Optional(2)

// Pridėjimas/atnaujinimas
myDictionary["grape"] = 4 // Prideda naują porą
myDictionary["apple"] = 10 // Atnaujina reikšmę "apple" raktui

// Ištrynimas
myDictionary["orange"] = nil // Ištrina "orange" porą