Ինչպես է կառուցված Swift-ի բառարանը?

Տառատեսակ (Dictionary) Swift-ում ներկայացնում է հավաքածու չսորտավորված զույգերի « բանալի-արժեք »։

Հիմնական հատկանիշներ՝

• Չսորտավորվածություն: Էլեմենտների կարգը չի երաշխավորվում։
• Անվերական բանալիներ: Յուրաքանչյուր բանալի պետք է լինի յուրահատուկ։
• Հաշվելի բանալիներ: Բանալիի տիպը պետք է լինի հաշվելի (այսինքն՝ համապատասխաներ Hashable պրոտոկոլին): Տիպեր, ինչպիսիք են String, Int, Double, Bool և մեծամասնությունը կառուցվածքների, ըստ նախնական կարգի, հաշվելի են։
• Տիպավորում: Տառատեսակը խիստ տիպավորված է՝ ինչպես բանալիների, այնպես էլ արժեքների։
• Պահոց: Իրականացվում է հեշ-թերթի հիման վրա, ինչը ապահովում է բարձր արդյունավետություն մուտքագրման, հեռացման և մուտք գործելու համար՝ ըստ բանալիի (միջինում՝ O(1))։

Ստեղծում՝

// Բաց տառատեսակ
var emptyDictionary: [String: Int] = [:]

// Բառարան սկզբնական արժեքներով
let cities: [String: String] = [
    "London": "UK",
    "Paris": "France",
    "Tokyo": "Japan"
]

Մուտք և փոփոխություն՝

// Մուտք ըստ բանալիի (վերադարձնում է Optional)
let country = cities["Paris"] // Optional("France")

// Ավելացում կամ թարմացում արժեքի
var scores: [String: Int] = ["Alice": 100, "Bob": 85]
scores["Charlie"] = 90 // Ավելացում
scores["Alice"] = 105 // Թարմացում

// Ապամպանում արժեք
scores["Bob"] = nil // Ապամպանում է տարր՝ բանալիով "Bob"

Իտերացիա՝

for (city, country) in cities {
    print("\(city) գտնվում է \(country)")
}

for city in cities.keys {
    print("Քաղաք: \(city)")
}

for country in cities.values {
    print("Երկիր: \(country)")
}

Ներքին կառուցվածք (ընդհանուր)

Swift-ը օգտագործում է փոփոխված հեշ-թերթի իրականացում։ Երբ ավելացվում է «բանալի-արժեք» զույգը՝

1. Հաշվարկվում է բանալիի հեշ-արժեքը։
2. Հեշ-արժեքը օգտագործվում է «խցիկի» (bucket) որոշման համար, որտեղ պետք է տեղադրվի տարրը։
3. Եթե խցիկում արդեն կան տարրեր, կիրառվում է հակասությունների լուծման մեխանիզմ (օրինակ՝ շղթայակապ կամ բաց հասցեագրման)՝ համապատասխան տեղ գտնելու համար։

Ամենամեծ մասշտաբով գործողությունների (մուտքագրում, հեռացում, մուտք գործում) արդյունավետությունը մոտ է O(1), եթե հեշերի հավասարաչափ բաշխում և փոքր հակասություններ։ Վատագույն դեպքում (երբ բոլոր հեշերը ընկնում են մեկ խցիկում) արդյունավետությունը կարող է նվազել մինչև O(n), բայց դա հազվադեպ է լավ հեշ-ֆունկցիաների և բավարար չափի հեշ-թերթի դեպքում։ Երբ ավելանում է տարրերի քանակը, բառարանը կարող է իրականացնել rehashing, մեծացնել ներքին կառուցվածքի չափը՝ պահպանելու արդյունավետությունը, ինչը կարող է լինել բավականին թանկ գործարք։