Dictionary.swift

struct Placeholder<Key, Value> where Key: Equatable, Key: Hashable {
    var values: [(Key, Value)] = []
    
    func firstValue(matchingKey key: Key) -> Value? {
        return values.lazy.filter({ $0.0 == key }).first?.1
    }
    
    mutating func removeValue(key: Key) {
        values = values.filter({ $0.0 != key })
    }
}

struct Dictionary<Key, Value> where Key: Equatable, Key: Hashable {
    fileprivate var storage = Array<Placeholder<Key, Value>>(repeating: Placeholder<Key, Value>(), count: 2)
    
    private let maxLoadFactor = 0.7
    
    private var size: Int {
        return storage.count
    }
    
    var count: Int {
        return storage.flatMap({ $0.values }).count
    }
    
    var currentLoadFactor: Double {
        return Double(count) / Double(size)
    }
    
    mutating func set(key: Key, value: Value) {
        remove(key: key)
        let position = abs(key.hashValue) % size
        storage[position].values.append((key, value))
        resizeIfNeeded()
    }
    
    mutating func resizeIfNeeded() {
        if currentLoadFactor > maxLoadFactor {
            let oldDictionary = self
            storage = Array<Placeholder<Key, Value>>(repeating: Placeholder<Key, Value>(), count: size*2)
            for (key, value) in oldDictionary {
                self[key] = value
            }
        }
    }
    
    mutating func remove(key: Key) {
        let position = abs(key.hashValue) % size
        storage[position].removeValue(key: key)
    }
    
    func get(key: Key) -> Value? {
        let position = abs(key.hashValue) % size
        return storage[position].firstValue(matchingKey: key)
    }
    
    subscript(key: Key) -> Value? {
        get {
            return get(key: key)
        }
        set {
            if let value = newValue {
                set(key: key, value: value)
            } else {
                remove(key: key)
            }
        }
    }
}

extension Dictionary: Sequence {
    typealias Iterator = AnyIterator<(Key, Value)>
    func makeIterator() -> Dictionary.Iterator {
        var storageIterator = storage.makeIterator()
        var currentIterator: AnyIterator<(Key, Value)>?
        return AnyIterator({
            if let next = currentIterator?.next() {
                return next
            }
            if let nextPlaceholder = storageIterator.next() {
                currentIterator = AnyIterator(nextPlaceholder.values.makeIterator())
            }
            return currentIterator?.next()
        })
    }
}

var dictionary = Dictionary<String, String>()
dictionary["there"] = "asdf"
dictionary["1232"] = "asd2f"

for pair in dictionary {
    print(pair)
}

dictionary.count

dictionary["1232"]
dictionary["1232"] = nil
dictionary["1232"]
dictionary["there"]