Kaip veikia žodynas Swift?

Swift žodynas (Dictionary) yra kolekcija nesutvarkytų porų "raktas-reikšmė".

Pagrindinės savybės:

• Nesutvarkytumas: Elementų tvarka nėra garantuota.
• Unikalūs raktai: Kiekvienas raktas žodyne turi būti unikalus.
• Heshable raktai: Raktų tipas turi būti heshable (t.y., atitikti Hashable protokolą). Tipai kaip String, Int, Double, Bool ir dauguma struktūrų yra heshable pagal numatytuosius nustatymus.
• Tipizacija: Žodynas griežtai tipizuotas, tiek pagal raktus, tiek pagal reikšmes.
• Saugojimas: Įgyvendintas remiantis hesh lentyna, užtikrinančia aukštą efektyvumą įterpimo, šalinimo ir prieigos operacijose pagal raktą (vidutiniškai O(1)).

Žodyno kūrimas:

// Tuščias žodynas
var emptyDictionary: [String: Int] = [:]

// Su pradine reikšme
let cities: [String: String] = [
    "London": "UK",
    "Paris": "France",
    "Tokyo": "Japan"
]

Prieiga ir modifikacija:

// Prieiga pagal raktą (grąžina Optional)
let country = cities["Paris"] // Optional("France")

// Pridėjimas arba atnaujinimas
var scores: [String: Int] = ["Alice": 100, "Bob": 85]
scores["Charlie"] = 90 // Pridėjimas
scores["Alice"] = 105 // Atnaujinimas

// Reikšmės šalinimas
scores["Bob"] = nil // Elemento šalinimas pagal raktą "Bob"

Iteracija:

for (city, country) in cities {
    print("\(city) yra \(country)")
}

for city in cities.keys {
    print("Miestas: \(city)")
}

for country in cities.values {
    print("Šalis: \(country)")
}

Vidinė struktūra (bendroji):

Swift naudoja modifikuotą hesh lentynos įgyvendinimą. Kai įdedama "raktas-reikšmė" pora:

1. Apskaičiuojama rakto hesh reikšmė.
2. Hesh reikšmė naudojama "krepšio" (bucket) nustatymui, į kurį turi būti įdėtas elementas.
3. Jei krepšyje jau yra elementų, naudojamas kolizijų sprendimo mechanizmas (pvz., grandinės arba atvira adresacija) tinkamai vietai rasti.

Daugumos operacijų (įdėjimas, šalinimas, prieiga) efektyvumas yra arti O(1), jei heshų paskirstymas yra geras ir kolizijų mažai. Blogiausiu atveju (kai visi heshai patenka į vieną krepšį) efektyvumas gali sumažėti iki O(n), tačiau tai yra retas atvejis gerų hesh funkcijų ir pakankamo dydžio hesh lentynos atveju. Didėjant elementų skaičiui, žodynas gali atlikti perkrovimą (rehashing), padidindamas vidinės struktūros dydį, kad išlaikytų efektyvumą, kas gali būti santykinai brangi operacija.