You've spent plenty of time using Swift's built-in Dictionary, but under the hood, that's just a highly optimized hash table. If you're prepping for a technical interview or just want to understand why lookups are O(1), you need to know how to build one from scratch. I find the best way to wrap your head around this is by building a simple inventory system for a vintage record store.

How do I actually turn a key into an array index?

The core of a hash table is the hash function. In Swift, we don't have to write the math for the hash itself because the Hashable protocol does the heavy lifting for us. Any type that conforms to Hashable has a hashValue property.

The trick is that the hashValue is a massive integer, but your underlying storage is just a fixed-size array (the "buckets"). To map that huge number to a valid index, we use the modulo operator. Here is the basic setup for our record store:

struct Record: Hashable {
    let artist: String
    let album: String
}

class RecordStoreHashTable<Key: Hashable, Value> {
    private var buckets: [[(Key, Value)]]
    private var count = 0
    private let capacity = 10

    init() {
        // Initialize an array of 10 empty arrays (buckets)
        self.buckets = Array(repeating: [], count: capacity)
    }

    private func index(for key: Key) -> Int {
        // Use abs() because hashValue can be negative
        return abs(key.hashValue) % capacity
    }
}

What's the best way to deal with collisions?

Eventually, two different keys will hash to the same index. It's mathematically inevitable. I usually recommend "Separate Chaining" for custom implementations because it's the most intuitive. Instead of storing a single value at each index, we store an array of tuples—essentially a little list of all items that collided at that spot.

When you put a value, you find the bucket, check if the key already exists to update it, or just append a new tuple if it doesn't. When you get a value, you jump to the bucket and do a linear search through that small list.

func put(key: Key, value: Value) {
    let idx = index(for: key)
    
    // Check if the key already exists in the bucket to update it
    for i in 0.. Value? {
    let idx = index(for: key)
    // Search the specific bucket for our key
    return buckets[idx].first(where: { $0.0 == key })?.1
}

How do I keep the performance fast as the table fills up?

If you have 1,000 records but only 10 buckets, your "O(1)" lookup quickly turns into O(n) because your buckets become long lists. To fix this, we use a "Load Factor"—usually around 0.75. Once the number of elements divided by the capacity exceeds this threshold, we need to resize.

You can't just copy the array to a bigger one; you have to re-hash every single element. Because the capacity changed, the result of hashValue % capacity changes, meaning every item might move to a completely different bucket.

I'll be honest: implementing a dynamic resize is where most people get tripped up. You essentially create a brand new, larger RecordStoreHashTable and migrate all the existing tuples into it. If you don't resize, your hash table is basically just a collection of slow arrays.

📋 Practical Task

Build a Movie Metadata Cache

Implement a custom hash table to act as a cache for movie metadata. Your implementation must meet the following requirements:

• Create a Movie struct that conforms to Hashable (use title and releaseYear as the properties).
• Implement a MovieCache class with a fixed capacity of 15 buckets.
• Implement a set(movie:value:) method that handles collisions using separate chaining.
• Implement a getValue(for movie:) method that returns the cached metadata (a String) or nil if not found.
• Implement a remove(movie:) method that deletes the entry from the bucket if it exists.

Test your cache by adding three different movies that you suspect might collide (or just add a variety of movies) and ensure you can retrieve and delete them correctly.