Hash Table Implementation in Swift

1. Introduction

A Hash Table is a data structure that stores key-value pairs and supports nearly instantaneous lookups, insertions, and deletions. It uses an array and a hashing function to determine where to store and retrieve the values. In case of collisions (when two different keys have the same hash value), one common resolution method is called chaining, where each cell in the array contains a linked list of key-value pairs.

2. Implementation Steps

1. Define a structure KeyValuePair that will store the key and value.

2. Define the HashTable class with an array of linked lists of KeyValuePair items.

3. Implement a basic hashing function to determine an index for each key.

4. Implement insert, retrieve, and remove methods.

5. Handle collisions using chaining.

3. Implementation in Swift

struct KeyValuePair<Key: Hashable, Value> {
    let key: Key
    var value: Value
}
class HashTable<Key: Hashable, Value> {
    // The main storage array
    private var storage: [LinkedList<KeyValuePair<Key, Value>>]
    private let capacity: Int
    init(capacity: Int) {
        self.capacity = capacity
        self.storage = Array(repeating: LinkedList<KeyValuePair<Key, Value>>(), count: capacity)
    }
    // 3. Basic hashing function
    private func hash(forKey key: Key) -> Int {
        return abs(key.hashValue) % capacity
    }
    // 4. Implement methods
    func insert(_ value: Value, forKey key: Key) {
        let keyValuePair = KeyValuePair(key: key, value: value)
        let index = hash(forKey: key)
        storage[index].append(keyValuePair)
    }
    func value(forKey key: Key) -> Value? {
        let index = hash(forKey: key)
        for case let pair in storage[index] where pair.key == key {
            return pair.value
        }
        return nil
    }
    func removeValue(forKey key: Key) {
        let index = hash(forKey: key)
        for (i, pair) in storage[index].enumerated() where pair.key == key {
            storage[index].remove(at: i)
            return
        }
    }
}
// Usage:
let hashTable = HashTable<String, Int>(capacity: 5)
hashTable.insert(123, forKey: "abc")
hashTable.insert(456, forKey: "def")
print(hashTable.value(forKey: "abc") ?? "Not Found") // Outputs: 123
hashTable.removeValue(forKey: "abc")
print(hashTable.value(forKey: "abc") ?? "Not Found") // Outputs: Not Found

Output:

123
Not Found

Explanation:

1. KeyValuePair struct is a simple container for the key-value pairs we want to store in the hash table.

2. HashTable is our main class that uses an array as the underlying storage mechanism.

3. The hash function takes the hash value of a key and returns an index for storage. The % capacity ensures we don't go out of bounds of our storage array.

4. Insert, value, and removeValue methods provide the main functionality for the hash table. The value method iterates over the linked list in the relevant storage cell to find the value for a given key.

5. Chaining is implicitly handled as each cell in the storage array is a linked list. When multiple items hash to the same index, they're just appended to the end of the linked list.