Jak jest zbudowany słownik w Swift?

Słownik (Dictionary) w Swift reprezentuje kolekcję nieuporządkowanych par "klucz-wartość".

Główne cechy:

• Nieuporządkowany: Kolejność elementów nie jest gwarantowana.
• Unikalne klucze: Każdy klucz w słowniku musi być unikalny.
• Hashowalne klucze: Typ klucza musi być hashowalny (czyli spełniać protokół Hashable). Typy takie jak String, Int, Double, Bool i większość struktur są domyślnie hashowalne.
• Typowanie: Słownik jest ściśle typowany, zarówno pod względem kluczy, jak i wartości.
• Przechowywanie: Zaimplementowany na bazie tablicy haszującej, co zapewnia wysoką wydajność operacji wstawiania, usuwania i dostępu po kluczu (średnio O(1)).

Tworzenie słowników:

// Pusty słownik
var emptyDictionary: [String: Int] = [:]

// Słownik z wartościami początkowymi
let cities: [String: String] = [
    "London": "UK",
    "Paris": "France",
    "Tokyo": "Japan"
]

Dostęp i modyfikacja:

// Dostęp po kluczu (zwraca Optional)
let country = cities["Paris"] // Optional("France")

// Dodanie lub aktualizacja wartości
var scores: [String: Int] = ["Alice": 100, "Bob": 85]
scores["Charlie"] = 90 // Dodanie
scores["Alice"] = 105 // Aktualizacja

// Usunięcie wartości
scores["Bob"] = nil // Usunięcie elementu z kluczem "Bob"

Iteracja:

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

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

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

Struktura wewnętrzna (ogólnie):

Swift używa zmodyfikowanej implementacji tablicy haszującej. Przy wstawianiu pary "klucz-wartość":

1. Obliczana jest wartość hash klucza.
2. Wartość hash jest używana do określenia "wiadra" (bucket), do którego ma być dodany element.
3. Jeśli w wiadrze są już elementy, używany jest mechanizm rozwiązywania kolizji (np. łańcuchowanie lub otwarte adresowanie), aby znaleźć odpowiednie miejsce.

Wydajność większości operacji (wstawianie, usuwanie, dostęp) jest bliska O(1), gdy hasze są równomiernie rozłożone i jest niewiele kolizji. W najgorszym przypadku (wszystkie hasze trafiają do jednego wiadra), wydajność może spaść do O(n), ale jest to rzadkie przy dobrych funkcjach hash i odpowiednim rozmiarze tablicy haszującej. Wraz ze wzrostem liczby elementów słownik może przeprowadzić rehash, zwiększając rozmiar struktury wewnętrznej, aby utrzymać wydajność, co może być operacją stosunkowo kosztowną.