Swift Dictionary and Set
Tags: swift, tutorial
Published: 2020-01-15 21:41:18

# 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.

```text
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:)`.
```text
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:
```text
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. 
```text
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.
```text
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.
```text
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
```text
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
``````