Come è strutturato un dizionario in Swift?

Il dizionario (Dictionary) in Swift rappresenta una collezione di coppie "chiave-valore" non ordinate.

Caratteristiche principali:

• Non ordinato: L'ordine degli elementi non è garantito.
• Chiavi uniche: Ogni chiave nel dizionario deve essere unica.
• Chiavi hashable: Il tipo di chiave deve essere hashable (cioè, conforme al protocollo Hashable). Tipi come String, Int, Double, Bool e la maggior parte delle strutture sono hashable di default.
• Tipizzazione: Il dizionario è strettamente tipizzato, sia per le chiavi che per i valori.
• Storage: Implementato su una tabella hash, che garantisce alta efficienza nelle operazioni di inserimento, rimozione e accesso tramite chiave (in media O(1)).

Creazione di dizionari:

// Dizionario vuoto
var emptyDictionary: [String: Int] = [:]

// Dizionario con valori iniziali
let cities: [String: String] = [
    "London": "UK",
    "Paris": "France",
    "Tokyo": "Japan"
]

Accesso e modifica:

// Accesso tramite chiave (ritorna un Optional)
let country = cities["Paris"] // Optional("France")

// Aggiunta o aggiornamento del valore
var scores: [String: Int] = ["Alice": 100, "Bob": 85]
scores["Charlie"] = 90 // Aggiunta
scores["Alice"] = 105 // Aggiornamento

// Rimozione del valore
scores["Bob"] = nil // Rimozione dell'elemento con chiave "Bob"

Iterazione:

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

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

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

Struttura interna (in generale):

Swift utilizza un'implementazione modificata di una tabella hash. Quando si inserisce una coppia "chiave-valore":

1. Viene calcolato il valore hash della chiave.
2. Il valore hash viene usato per determinare la "cestino" (bucket) in cui deve essere inserito l'elemento.
3. Se nella cesta ci sono già elementi, viene utilizzato un meccanismo di risoluzione delle collisioni (ad esempio, concatenamento o indirizzamento aperto) per trovare un posto adatto.

Le prestazioni della maggior parte delle operazioni (inserimento, rimozione, accesso) sono vicine a O(1) quando gli hash sono distribuiti uniformemente e ci sono poche collisioni. Nel caso peggiore (tutti gli hash cadono in un'unica cesta), le prestazioni possono degradare a O(n), ma ciò è raro con buone funzioni hash e dimensioni sufficienti della tabella hash. Quando il numero di elementi aumenta, il dizionario può eseguire un rehashing, aumentando la dimensione della struttura interna per mantenere l'efficienza, operazione che può essere relativamente costosa.