What is a hash table, and how does it work?

A hash table is a data structure that is used to store and retrieve key-value pairs. It is also known as a hash map, dictionary, or associative array. A hash table works by using a hash function to map each key to a corresponding index in an array.

The hash function takes the key as input and produces a hash code, which is an integer value that represents the key. The hash code is then used to calculate an index in the array, where the corresponding value is stored. In most cases, the hash function should produce the same hash code for the same key every time it is called.

To handle collisions, where two or more keys map to the same index, the hash table uses a collision resolution strategy. The most common strategies are chaining and open addressing.

In chaining, each index in the array stores a linked list of key-value pairs that have the same hash code. When a new key-value pair is inserted, it is added to the linked list at the corresponding index. If a collision occurs when inserting a key-value pair, it is added to the end of the linked list.

In open addressing, each index in the array stores a single key-value pair. When a new key-value pair is inserted, the hash table checks whether the corresponding index is already occupied. If it is, the hash table looks for the next available index in the array using a probing sequence. A probing sequence is a sequence of indices that the hash table checks until an empty index is found. When a collision occurs, the hash table uses a variation of the probing sequence to determine the next index to check.

Here is an example of how to implement a hash table in Java using chaining:

class HashTable {
    private int capacity;
    private LinkedList<Entry>[] table;
    
    public HashTable(int capacity) {
        this.capacity = capacity;
        table = new LinkedList[capacity];
    }
    
    public void put(int key, int value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }
        for (Entry entry : table[index]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        table[index].add(new Entry(key, value));
    }
    
    public int get(int key) {
        int index = hash(key);
        if (table[index] == null) {
            return -1;
        }
        for (Entry entry : table[index]) {
            if (entry.key == key) {
                return entry.value;
            }
        }
        return -1;
    }
    
    private int hash(int key) {
        return key % capacity;
    }
    
    private static class Entry {
        int key;
        int value;
        
        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

In this example, the HashTable class implements a hash table using chaining. The class has a capacity field that determines the size of the array, and a table field that is an array of linked lists. The put() method takes a key-value pair as input and inserts it into the hash table. The get() method takes a key as input and returns the corresponding value from the hash table. The hash() method takes a key as input and returns the corresponding index in the array using the modulo operator. The Entry class represents a key-value pair that is stored in the hash table.

In summary, a hash table is a data structure that is used to store and retrieve key-value pairs. It works by using a hash function to map each key to a corresponding index in an array. To handle collisions, it uses a collision resolution strategy such as chaining.