Implement a hash map from scratch (get, set, remove), then extend it: what do you test and how does resizing work?

Predict first

What does the chained hash table report?

struct HashTable<Key: Hashable, Value> {
    private var buckets: [[(key: Key, value: Value)]]
    private(set) var count = 0
    private(set) var resizes = 0

    init(capacity: Int = 4) { buckets = Array(repeating: [], count: capacity) }

    private func slot(_ key: Key, in n: Int) -> Int { Int(UInt(bitPattern: key.hashValue) % UInt(n)) }

    subscript(key: Key) -> Value? {
        get { buckets[slot(key, in: buckets.count)].first { $0.key == key }?.value }
        set {
            let s = slot(key, in: buckets.count)
            if let i = buckets[s].firstIndex(where: { $0.key == key }) {
                if let v = newValue { buckets[s][i].value = v }
                else { buckets[s].remove(at: i); count -= 1 }
            } else if let v = newValue {
                buckets[s].append((key, v)); count += 1
                if count * 4 > buckets.count * 3 { grow() }            // load factor above 0.75
            }
        }
    }
    private mutating func grow() {
        let bigger = buckets.count * 2
        var next = [[(key: Key, value: Value)]](repeating: [], count: bigger)
        for bucket in buckets { for e in bucket { next[slot(e.key, in: bigger)].append(e) } }
        buckets = next; resizes += 1
    }
}
struct BadKey: Hashable {                          // every key hashes alike: still correct, just slow
    let id: Int
    func hash(into h: inout Hasher) { h.combine(0) }
}
var t = HashTable<Int, String>()
for i in 1...20 { t[i] = "v\(i)" }
print("count", t.count, "resizes", t.resizes)
t[5] = "five"                                       // overwrite: count must not change
print("t[5]", t[5] ?? "nil", "count", t.count)
t[7] = nil
print("t[7]", t[7] ?? "nil", "count", t.count)
print("t[99]", t[99] ?? "nil")
var bad = HashTable<BadKey, Int>()
for i in 0..<10 { bad[BadKey(id: i)] = i * i }
print("bad[9]", bad[BadKey(id: 9)] ?? -1, "count", bad.count)

• count 20 resizes 3 / t[5] five count 20 / t[7] nil count 19 / t[99] nil / bad[9] 81 count 10
• count 20 resizes 4 / t[5] five count 21 / t[7] nil count 19 / t[99] nil / bad[9] 81 count 10
• count 20 resizes 3 / t[5] five count 20 / t[7] 7 count 19 / t[99] nil / bad[9] -1 count 10