Explain how hash tables work.?

Hash tables are a type of data structure that allow for fast data retrieval and storage. They allow a program to access a data value given a key, in constant time O(1), on average.

Here’s how they work:

**1. Hash Function:**

A hash table utilizes a hash function that takes an input (or ’key’) and returns an index into an array where the corresponding value is stored. The hash function is used to convert the key into a unique index (hash code), which is used to find the desired value.

Suppose our hash function is ‘h(k) = k mod 10‘, where ‘k mod 10‘ is the remainder when ‘k‘ is divided by 10.

If we want to store a value with the key 23, our hash function would compute ‘h(23) = 23 mod 10 = 3‘. So, we store the corresponding value at the index 3 in our hash table.

**2. Handling Collisions:**

Collisions occur when the hash function returns the same index for two different keys. There two main methods to handle collisions: separate chaining and open addressing.

- Separate Chaining: Each index in the array points to a linked list. When a collision occurs, the new key-value pair is added to the end of the linked list at the relevant index.

- Open Addressing: When a collision occurs, we find the next available slot in the array and use that to store our new key-value pair.

**3. Load Factor and Resizing:**

The load factor is a measure that determines when to increase the size of the hash table. It is calculated as the ratio of the number of elements to the size of the array.

If we have a hash table of size 10 and 8 elements stored in it, then ‘load factor = 8/10 = 0.8‘. When the load factor surpasses a certain threshold (typically 0.7), the hash table is resized.

The following pseudocode illustrates a simple hash table using an array:

class HashTable
    initialize(size):
        data = new Array(size)

    __hash(key):
        hash = 0
        for(let i = 0; i < key.length; i++):
            hash = (hash + key.charCodeAt(i) * i) % data.length
        return hash

    insert(key, value):
        address = this.__hash(key)
        if(!data[address]):
            data[address] = []
        data[address].push([key, value])
        return address

    lookup(key):
        address = this.__hash(key)
        if(data[address]):
            for(let i = 0; i < data[address].length; i++)
                if(data[address][i][0] == key)
                    return data[address][i][1]
        return null

In this code, ‘__hash()‘ is a simple hash function that converts the key to an index in the data array. The ‘insert()‘ method hashes the key and push a new array containing the key and value to the hashed address. The ‘lookup()‘ function also hashes the key but then tries to find it in the data array. If it finds it, it returns the value, else it returns null.