Hash tables, also known as dictionaries in Swift, are a fundamental data structure in computer science. They offer fast access, addition, and deletion of elements using keys, making them an indispensable tool for developing efficient algorithms. This blog post will explore the hash table pattern, demonstrating how to leverage it in Swift to solve common programming challenges effectively.

What is a Hash Table?

A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

In Swift, the Dictionary type implements a hash table, providing average-case constant time complexity (O(1)) for accesses, insertions, and deletions, assuming the hash function is good and collisions are minimal.

Why Use Hash Tables?

Hash tables are incredibly versatile and useful for several types of problems:

• Tracking item frequency: Easily count occurrences of elements.
• Unique item storage: Quickly check for the existence of items.
• Two-sum type problems: Solve problems that involve pairing elements to meet certain criteria.
• Caching results: Implement memoization to optimize performance in recursive calls.

Swift Examples Using Hash Tables

Example 1: Counting Frequencies

Suppose you want to count the frequency of elements in an array. Here’s how you can do it using a Dictionary:

func countFrequencies(of array: [Int]) -> [Int: Int] {
    var frequencyDict = [Int: Int]()

    for num in array {
        frequencyDict[num, default: 0] += 1
    }

    return frequencyDict
}

let numbers = [1, 2, 2, 3, 3, 3]
let frequencies = countFrequencies(of: numbers)
print(frequencies)  // Output: [3: 3, 2: 2, 1: 1]

Example 2: Checking for Duplicates

Here’s how you might use a hash table to check if there are any duplicates in an array:

func containsDuplicate(_ array: [Int]) -> Bool {
    var occurenceDict = [Int: Bool]()

    for num in array {
        if occurenceDict[num] == true {
            return true
        }
        occurenceDict[num] = true
    }

    return false
}

let values = [1, 2, 3, 4, 5, 1]
print(containsDuplicate(values))  // Output: true

let values2 = [1, 2, 3, 4, 5]
print(containsDuplicate(values2))  // Output: false

Example 3: Two-Sum Problem

The two-sum problem asks if there are two numbers in an array that add up to a specific target. Here’s a Swift solution using a hash table:

func twoSum(_ nums: [Int], _ target: Int) -> Bool {
    var numDict = [Int: Int]()

    for (index, num) in nums.enumerated() {
        let complement = target - num
        if let _ = numDict[complement] {
            return true
        }
        numDict[num] = index
    }

    return false
}

let numbers = [2, 7, 11, 15]
let result = twoSum(numbers, 9)
print(result)  // Output: true

Problems:

13. Roman to Integer

Leetcode: 13. Roman to Integer

func romanToInt(_ s: String) -> Int {
    let characters = Array(s) // Convert the string to array for easy iteration
    var result: Int = 0
    let map: [Character : Int] = [
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    ]

    // Iterate through the string, from left to right
    for index in 0..<characters.count-1 {
        // check if the current value is smaller than the next value -> Subtraction
        if (map[characters[index]]! < map[characters[index+1]]!) {
            result -= map[characters[index]]!
        // check if the current value is larger than or equal the next value -> Addition
        } else {
            result += map[characters[index]]!
        }
    }

    // Add the value of the last element
    result += map[characters.last!]!

    return result
}

print(romanToInt("III")) // 3
print(romanToInt("LVIII")) // 58
print(romanToInt("MCMXCIV")) // 1994

Conclusion

Hash tables are a powerful tool in the Swift programmer’s arsenal, perfect for tackling a wide range of problems with optimal efficiency. By understanding and utilizing hash tables effectively, you can significantly enhance the performance and scalability of your applications. Whether you’re counting frequencies, checking for duplicates, or solving complex computational problems, the hash table pattern is incredibly useful for achieving fast and readable solutions.

Further Readings:

• Leetcode - Hash Tables