Как реализуешь словарь?

Realizacija Slovarja v Swift

Slovari (Dictionaries) - jedno iz samyh vazhnyh kollekcij v Swift. Eto asociativnyj massiv, gde kazhdjyj element imeeт paru klyuch-znachenie. Pozvolyaet razobrat'sja v vnutrennej realizacii i kak ih ispol'zovat' optimalno.

Bazovoe ispol'zovanie

var slovar: [String: Int] = [:]
slovar["age"] = 30
slovar["count"] = 5

if let age = slovar["age"] {
    print("Age: \(age)")
}

Vnutrennjaja struktura - Hash Table

Swift slovari realizovany na osnove hash-tablicy:

// KONCEPTUALNAJA REALIZACIJA
struct SimpleDictionary<Key: Hashable, Value> {
    private var buckets: [[Pair<Key, Value>]]
    private var count = 0
    
    struct Pair<K, V> {
        var key: K
        var value: V
    }
    
    mutating func insert(_ value: Value, forKey key: Key) {
        let hash = key.hashValue
        let index = hash % buckets.count
        
        // Tselievyj poisk v baskete
        for i in buckets[index].indices {
            if buckets[index][i].key == key {
                buckets[index][i].value = value
                return
            }
        }
        
        // Esli kljucha net - dobavljaem novuju paru
        buckets[index].append(Pair(key: key, value: value))
        count += 1
        
        // Rehashing esli nuzhno
        if Double(count) / Double(buckets.count) > 0.75 {
            rehash()
        }
    }
    
    func value(forKey key: Key) -> Value? {
        let hash = key.hashValue
        let index = hash % buckets.count
        
        for pair in buckets[index] {
            if pair.key == key {
                return pair.value
            }
        }
        
        return nil
    }
    
    mutating func rehash() {
        let oldBuckets = buckets
        buckets = Array(repeating: [], count: buckets.count * 2)
        count = 0
        
        for bucket in oldBuckets {
            for pair in bucket {
                insert(pair.value, forKey: pair.key)
            }
        }
    }
}

Vremennaja slozhnost'

• Vstavka (insert) - O(1) v srednem, O(n) v khuzhem (mnogo kollidzij)
• Poisk (search) - O(1) v srednem
• Udalenie (delete) - O(1) v srednem
• Perebor (iteration) - O(n)

Prakticheskaja realizacija slovarja

class MutableDictionary<Key: Hashable, Value> {
    private var storage: [String: Any] = [:]
    
    subscript(key: Key) -> Value? {
        get {
            return storage[String(describing: key)] as? Value
        }
        set {
            if let value = newValue {
                storage[String(describing: key)] = value
            } else {
                storage.removeValue(forKey: String(describing: key))
            }
        }
    }
    
    func removeAll() {
        storage.removeAll()
    }
}

Kollidzii i hash function

Hash-tablica mogut imet' kollidzii, kogda dva raznyh kljucha imejut odnu i tu zhe hash-shummu:

struct CustomKey: Hashable {
    let value: Int
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(value)
    }
    
    static func == (lhs: CustomKey, rhs: CustomKey) -> Bool {
        lhs.value == rhs.value
    }
}

var dict: [CustomKey: String] = [:]
dict[CustomKey(value: 1)] = "One"
dict[CustomKey(value: 1)] = "Odin"  // Perezapisuetsja
dict[CustomKey(value: 2)] = "Two"

Optimizacija - vypolnenie rehashing

Kogda kolichestvo elementov priblizhaetsja k razmeru mass-iva, slovar' avtomaticheski uvelichivaet razmer i pereheshiruetsja:

var dict: [String: Int] = [:]
// Nachalno: 4 basketa

for i in 0..<10 {
    dict["key\(i)"] = i
    // Pri dostizheniii 3 elementov (0.75 * 4):
    // - Rehashing
    // - Novyj razmer: 8 basketov
}

Iteracija po slovarju

let dict = ["a": 1, "b": 2, "c": 3]

// Prostyj perebor
for (key, value) in dict {
    print("\(key): \(value)")
}

// Nur kljuchi
for key in dict.keys {
    print(key)
}

// Nur znachenija
for value in dict.values {
    print(value)
}

Swift slovari - osobennosti

// 1. Porjadok iteracii ne garantiruetsja
let dict: [String: Int] = ["a": 1, "b": 2]
for key in dict.keys {
    print(key)  // "a" i "b" v sluchajnom porjadke
}

// 2. Nil bezopasnost'
let dict: [String: Int?] = ["key": nil]
let value = dict["key"]  // Optional<Optional<Int>> - nested!

// 3. Default znachenie
let count = dict["missing", default: 0]  // 0

// 4. Updateonly
dict.updateValue(42, forKey: "new")  // Vozvrashshaet staroe znachenie

Kogda ispol'zovat' slovar'

• Fast lookups po kljuchu
• Kompleksnye mapirovki dannyh
• Keshirovanie (cache keys)
• Aggregacija dannyh

Kogda ispol'zovat' massiv vmesto slovarja

• Emsli porjadok vazhno
• Mало elementov
• Indeksnyj dostup vazhnee

Slovar' - fundamental'nyj instrument Swift, i ponimanie ego vnutrennoj realizacii - vazhno dlya opredelenija optimalnoj dlja vashej zadachi strukture dannyh.