Hoe is een woordenboek in Swift opgebouwd?

De Swift Dictionary (Woordenboek) vertegenwoordigt een collectie van ongeordende sleutel-waardeparen.

Belangrijkste kenmerken:

• Ongordend: De volgorde van de elementen wordt niet gegarandeerd.
• Unieke sleutels: Elke sleutel in de dictionary moet uniek zijn.
• Hashbare sleutels: Het type sleutel moet hashbaar zijn (d.w.z. voldoen aan het Hashable protocol). Types zoals String, Int, Double, Bool en de meeste structuren zijn standaard hashbaar.
• Type-gebonden: De dictionary is strikt getypeerd, zowel voor sleutels als voor waarden.
• Opslag: Geïmplementeerd op basis van een hash-tabel, wat hoge efficiëntie biedt voor invoeg-, verwijder- en toegangsbewerkingen op basis van sleutel (gemiddeld O(1)).

Aanmaken van dictionaries:

// Lege dictionary
var emptyDictionary: [String: Int] = [:]

// Dictionary met beginwaarden
let cities: [String: String] = [
    "London": "UK",
    "Paris": "France",
    "Tokyo": "Japan"
]

Toegang en wijziging:

// Toegang via sleutel (retourneert een Optional)
let country = cities["Paris"] // Optional("France")

// Toevoegen of bijwerken van waarde
var scores: [String: Int] = ["Alice": 100, "Bob": 85]
scores["Charlie"] = 90 // Toevoegen
scores["Alice"] = 105 // Bijwerken

// Verwijderen van waarde
scores["Bob"] = nil // Verwijderen van element met sleutel "Bob"

Iteratie:

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

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

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

Interne structuur (algemeen):

Swift gebruikt een aangepaste implementatie van een hash-tabel. Bij het invoegen van een "sleutel-waarde" paar:

1. Wordt de hash-waarde van de sleutel berekend.
2. De hash-waarde wordt gebruikt om de "bak" (bucket) te bepalen waarin het element moet worden geplaatst.
3. Als er al elementen in de bak zijn, wordt een mechanisme voor het oplossen van botsingen gebruikt (bijvoorbeeld chaining of open addressing) om een geschikte plek te vinden.

De prestaties van de meeste operaties (invoegen, verwijderen, toegang) liggen dicht bij O(1) wanneer de hashes gelijkmatig verdeeld zijn en er weinig botsingen zijn. In het slechtste geval (alle hashes in één bak), kan de prestatie afnemen tot O(n), maar dit is zeldzaam bij goede hash-functies en voldoende grote hash-tabellen. Naarmate het aantal elementen toeneemt, kan de dictionary rehashing uitvoeren, waarbij de interne structuur wordt vergroot om de efficiëntie te behouden, wat een relatief dure operatie kan zijn.