Swift Dictionary and Set

Swift Dictionaries

No less than important data structure that contains unique keys with corresponding values.
Retrieving a value by its key takes constant time, whereas searching an array for a particular element grows linearly to arrays size. Dictionaries are not ordered, key-value pairs are not enumerated, meaning for in is undefined.

enum Setting {
    case text(String)
    case int(Int)
    case bool(Bool)
}
let defaultSettings: [String: Setting] = [
    "darkMode": .bool(false),
    "Name": .text("Mark"),
]

defaultSettings["Name"]

To get the optional of underlying value subscription [] is used.

Mutating Dictionaries

Just like arrays, dictionaries defined using let are immutable.

To remove a value from a mutable dictionary, it may either be set to nil or call removeValue(forKey:).

defaultSettings["Name"]

var userSettings = defaultSettings
userSettings["Name"] = .text("Dave")
userSettings["active-mode"] = .bool(true)

Here, value of defaultSettings didn't change.

Update is done with updateValue(_:forKey:) method:

let oldName = userSettings.updateValue(.text("Tim"), forKey: "Name")
userSettings["Name"]
oldName

Useful methods

Merge

To combine default settings dictionary with any custom settings overriding defaults yet still including default values for any keys that aren't customized is called: merging

Dictionary has a merge(_:uniquingKeysWith:) method, which takes the key-value pairs to be merged in and a function that specifies how to combine two values with the same key.

var settings = defaultSettings
let overriddenSettings: [String:Setting] = ["Name": .text("Timothy")]
settings.merge(overriddenSettings, uniquingKeysWith: { $1})
settings

{ $1 } is used as the policy for combining two values: If a key exists in both settings and overriddenSettings, value from the latter is used.

A new dictionary can be constructed out of a sequence of (Key, Value) pairs. If we can guarantee that the keys are unique, Dictionary(uniqueKeysWithValues:) may be utilized. However, if key may exist multiple times, a function to combine the two values with same key must be provided. For example, computation of rate of appearance in a sequence may be done with a map over each element, combining it with a 1, then, creating a dictionary out of the resulting element-frequency pairs. If two values for the same key are met, the frequencies are simply added up using + operator.

extension Sequence where Element: Hashable {
    var frequencies: [Element:Int] {
        let frequencyPairs = self.map{ ($0, 1) }
        return Dictionary(frequencyPairs, uniquingKeysWith: +)
    }
}
let frequencies = "hello".frequencies // ["e": 1, "h": 1, "o": 1, "l": 2]
let filtered = frequencies.filter{ $0.value > 1 }
filtered // ["l": 2]

Map over dictionary values

Because Dictionary is a subclass of Sequence, it already has a map method that produces an array. However, to keep the dictionary structure intact and only transform its values mapValues is utilized.

let settingsAsStrings = settings.mapValues {
    setting -> String in
    switch setting {
        case .text(let text): return text
        case .int(let number): return String(number)
        case .bool(let value): return String(value)
    }
} // ["darkMode": "false", "Name": "Timothy"]

Hashable requirement detail

Dictionaries are hash tables, where each key is assigned with position in memory based on the key's hashValue. Dictionary therefore requires it's Key type to conform to the Hashable protocol. All the basic data types of standard library (strings, integers, booleans) already do. Moreover, if array's elements are hashable, the array itself conforms as well.

In order to maintain the performance, has table require the types stored in them to provide a fast and far-fetching hash deriving function. The compiler generates Hashable conformance by use of standard library's hash function that custom types can hook into.

For structs and enumerations, compiler will synthesize Hashable conformance for as long as elements are Hashable.

If for some reason a custom type has 1 or more stored properties that must be ignored for hashing, Equatable conformance must be met first, then, hash(into:) requirement of the Hashable protocol. This method receives a Hasher, which wraps a universal hash function and captures the state of the hash function on the go. The hasher has a combine method that accepts any hashable value. Hence, all the components, except of transient (lazy) ones, of a custom type must be fed to the hasher with combine.

Equality checking must also be performed on these essential components excluding transience, because there is an invariant to be held:
"Two instances that are equal (as defined by == implementation) must have the same hash value", while reverse is incorrect:
"Two instances with the same hash value don't necessarily compare equally". This makes sense, since there's only so much of hash values, while infinite number of strings.

Swift Sets

Set is an unordered collection of elements, with each element appearing only once. Think of set as a dictionary that only stores keys and no values. Like Dictionary, Set is implemented with a hash table and is as performant and demanding.

Test for a membership operation has a constant cost while arrays has a linear cost.

Set conforms to the ExpressibleByArrayLiteral protocol, which means it can be initialized with a literal

let naturals: Set = [1,2,3,2]
naturals // {2, 3, 1}
naturals.contains(0) // false

Note that '2' appears only once in the set, duplicate never gets inserted.

Set is closely related to mathematical concept of a set; common operations like subtraction are supported