Sobes.tech
Junior — Middle

Can you explain how access to an object is implemented in a hash table within the system?

sobes.tech AI

Answer from AI

Access to an object in a hash table is implemented through computing a hash function from the key, which determines the index in the array where the value is stored.

Example of how it works:

  1. You take the key and apply a hash function to it, obtaining a number (hash).
  2. This number is converted into an array index (usually by taking the modulus with the array size).
  3. At this index in the array, a linked list or another container with elements that have the same hash is stored.
  4. The elements in this container are iterated over to find an exact match for the key.

Example in Swift:

struct HashTable<Key: Hashable, Value> {
    private var buckets: [[(key: Key, value: Value)]]

    init(size: Int) {
        buckets = Array(repeating: [], count: size)
    }

    func hash(_ key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }

    mutating func set(_ key: Key, value: Value) {
        let index = hash(key)
        for i in 0..<buckets[index].count {
            if buckets[index][i].key == key {
                buckets[index][i].value = value
                return
            }
        }
        buckets[index].append((key, value))
    }

    func get(_ key: Key) -> Value? {
        let index = hash(key)
        for pair in buckets[index] {
            if pair.key == key {
                return pair.value
            }
        }
        return nil
    }
}

Thus, access to an object is the calculation of the hash, moving to the required bucket, and searching for the key within it.