Как е структуриран речникът в 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), увеличавайки размера на вътрешната структура, за да поддържа ефективност, което може да бъде относително скъпа операция.