HashMap.swift

import Foundation

// Build a HashMap like data structure with next methods
//   put(key: K, value: V) 
//   get(key: K) -> V? 
//   getRandom() -> (K, V)?
//   all of them with average O(1) time complexity.

class HashMap<K, V> where K: Hashable {
    private var store = Dictionary<K, V>()
    private(set) var keys = Array<K>()
    
    func put(key: K, value: V) {
        if store[key] == nil { // O(1)
            keys.append(key) // O(1)
        }
        store[key] = value // O(1)
    }
    
    func get(key: K) -> V? {
        return store[key] // O(1)
    }
    
    func getRandom() -> (K, V)? {
        guard let key = keys.randomElement() else { return nil } // O(1)
        guard let value = store[key] else { return nil } // O(1)
        return (key, value) 
    }
}

let dict = MyDictionary<Int, String>()

dict.put(key: 1, value: "A")
dict.put(key: 2, value: "B")
dict.put(key: 3, value: "C")
dict.put(key: 4, value: "D")
dict.put(key: 5, value: "E")
dict.put(key: 6, value: "F")

// Overiding element
dict.put(key: 10, value: "R")
dict.put(key: 10, value: "Y")
dict.put(key: 10, value: "U")



print(String(describing: dict.get(key: 1))) // Optional("A")
print(String(describing: dict.get(key: 3))) // Optional("B")
print(String(describing: dict.get(key: 6))) // Optional("F")
print(String(describing: dict.get(key: 10))) // Optional("U")
print(dict.keys) // [1, 2, 3, 4, 5, 6, 10]

for i in 0..<20 {
    print(String(describing: dict.getRandom()))
}