Hash tables are a type of data structure that provide efficient access to data via key-value pairs. The key is processed through a hash function to determine an index at which the value is stored.

Basic Structure

The basic structure of a hash table includes an array (table) and a hash function. The hash function maps keys to array indices, allowing for quick data retrieval.

Collision Handling

Collisions occur when two keys hash to the same index. Common strategies for handling collisions include chaining and open addressing.


import java.util.Hashtable;

class HashTableExample {
    public static void main(String args[]) {
        Hashtable numbers = new Hashtable<>();
        numbers.put("One", 1);
        numbers.put("Two", 2);
        numbers.put("Three", 3);
        System.out.println(numbers);
    }
}

Java HashTable Example

In this example, we create a simple hash table using Java's built-in Hashtable class. We store integer values with string keys and print the table.

Console Output:

{One=1, Two=2, Three=3}

Chaining in Hash Tables

Chaining Method

Chaining is a collision resolution method where each cell in the hash table points to a linked list of entries that hash to the same index.


import java.util.LinkedList;

class ChainingHashTable {
    private LinkedList[] table;
    private static class Entry {
        String key;
        int value;
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    @SuppressWarnings("unchecked")
    public ChainingHashTable(int size) {
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hash(String key) {
        return key.hashCode() % table.length;
    }

    public void put(String key, int value) {
        int index = hash(key);
        table[index].add(new Entry(key, value));
    }

    public LinkedList get(String key) {
        int index = hash(key);
        return table[index];
    }
}

Implementation of Chaining

This example demonstrates a hash table implementation using chaining. Each table index holds a linked list of entries to handle collisions.

Open Addressing

Open Addressing Method

Open addressing is a collision resolution method where all elements are stored within the hash table itself, and a probing sequence is used to find an empty slot.


class OpenAddressingHashTable {
    private Entry[] table;
    private static class Entry {
        String key;
        int value;
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public OpenAddressingHashTable(int size) {
        table = new Entry[size];
    }

    private int hash(String key) {
        return key.hashCode() % table.length;
    }

    public void put(String key, int value) {
        int index = hash(key);
        while (table[index] != null) {
            index = (index + 1) % table.length;
        }
        table[index] = new Entry(key, value);
    }

    public int get(String key) {
        int index = hash(key);
        while (table[index] != null && !table[index].key.equals(key)) {
            index = (index + 1) % table.length;
        }
        return table[index] != null ? table[index].value : -1;
    }
}

Linear Probing in Open Addressing

This implementation uses linear probing to resolve collisions. If a collision occurs, it checks the next slot in the sequence until an empty slot is found.

Double Hashing

Double Hashing Technique

Double hashing uses two hash functions to compute the index. If a collision occurs, the second hash function is used to calculate a new index.


class DoubleHashingHashTable {
    private Entry[] table;
    private static class Entry {
        String key;
        int value;
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public DoubleHashingHashTable(int size) {
        table = new Entry[size];
    }

    private int hash1(String key) {
        return key.hashCode() % table.length;
    }

    private int hash2(String key) {
        return 7 - (key.hashCode() % 7);
    }

    public void put(String key, int value) {
        int index = hash1(key);
        int stepSize = hash2(key);
        while (table[index] != null) {
            index = (index + stepSize) % table.length;
        }
        table[index] = new Entry(key, value);
    }

    public int get(String key) {
        int index = hash1(key);
        int stepSize = hash2(key);
        while (table[index] != null && !table[index].key.equals(key)) {
            index = (index + stepSize) % table.length;
        }
        return table[index] != null ? table[index].value : -1;
    }
}

Resolving Collisions with Double Hashing

Double hashing reduces clustering by using a second hash function, providing a more uniform distribution of keys across the hash table.

Rehashing

Rehashing Concept

Rehashing involves increasing the hash table size and re-inserting all existing keys into the new larger table. This is done to maintain a low load factor and improve performance.


import java.util.Arrays;

class RehashingHashTable {
    private Entry[] table;
    private int size;

    private static class Entry {
        String key;
        int value;
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public RehashingHashTable(int initialSize) {
        table = new Entry[initialSize];
        size = 0;
    }

    private int hash(String key) {
        return key.hashCode() % table.length;
    }

    public void put(String key, int value) {
        if (size >= table.length * 0.75) {
            rehash();
        }
        int index = hash(key);
        while (table[index] != null) {
            index = (index + 1) % table.length;
        }
        table[index] = new Entry(key, value);
        size++;
    }

    private void rehash() {
        Entry[] oldTable = table;
        table = new Entry[oldTable.length * 2];
        size = 0;
        for (Entry entry : oldTable) {
            if (entry != null) {
                put(entry.key, entry.value);
            }
        }
    }
}

Dynamic Resizing with Rehashing

This example illustrates dynamic resizing through rehashing, which helps maintain performance by keeping the load factor low as the number of entries grows.