Introduction

Let’s take a closer look at a HashMap implementation by building it without using the built-in dictionary in Swift. The HashMap will use a fixed-size array underneath the hash function that will transform the key into an index. In this example, the hash function is based on taking the modulo of the sum of all key.unicodeScalars integer values with the size of the array.

Code Example

final class HashMap<Key: StringProtocol, Value> {

    private var hashMap: [(key: Key, value: Value)?]

    init(size: Int) {
        self.hashMap = Array(repeating: nil, count: size)        
    }

    private func hashFunction(key: Key) -> Int {
        var count = 0
        for element in key.unicodeScalars {
            count += Int(element.value)
        }
        return count % self.hashMap.count
    }

}

Insert

The insert operation uses the index provided by the hashFunction and sets the value at this index.

func insert(key: Key, value: Value) {
    let index = hashFunction(key: key)
    self.hashMap[index] = (key, value)
}

Get

The get operation uses the index provided by the hashFunction and retrieves the value at this index.

func getValue(by key: Key) -> Value? {
    let index = hashFunction(key: key)
    return self.hashMap[index]?.value
}

Complete Code Example

final class HashMap<Key: StringProtocol, Value> {

    private var hashMap: [(key: Key, value: Value)?]    

    init(size: Int) {
        self.hashMap = Array(repeating: nil, count: size)
    }

    func getValue(by key: Key) -> Value? {
        let index = hashFunction(key: key)
        return self.hashMap[index]?.value
    }

    func insert(key: Key, value: Value) {
        let index = hashFunction(key: key)
        self.hashMap[index] = (key, value)
    }

    private func hashFunction(key: Key) -> Int {
        var count = 0
        for element in key.unicodeScalars {
            count += Int(element.value)
        }
        return count % self.hashMap.count
    }

}

Time/Space Complexity

Time complexity in Big O notation:

Operation Average Worst Case
Insert Θ(1) O(n)

Space complexity: Θ(n)

Thank you for reading! 😊