Design a Hash Table in Java – Interview Question

Introduction

A hash table is a popular data structure used to store key-value pairs, making it easy and quick to find, insert, and delete data. Hash tables are widely used in software development because they provide an efficient way to manage large datasets with constant time complexity for these operations.

In this guide, we will design a hash table in Java from scratch. We'll cover how a hash table works and how to handle collisions (when two keys map to the same index). We will also demonstrate a fully working hash table that supports basic operations like inserting, retrieving, and deleting key-value pairs.

Why Hash Tables?

Hash tables are essential for developers because they are used in many applications, such as database indexing, caching, and implementing associative arrays (also known as dictionaries). Understanding how they work and how to build them from scratch is a valuable skill for technical interviews.

Key Features of Our Java Hash Table:

Insert key-value pairs.
Retrieve values by key.
Remove key-value pairs.
Handle collisions using separate chaining (linked lists).
Support dynamic resizing and efficient lookups.

How Hash Tables Work

A hash table uses a hash function to convert a key into an index for storing the value in an array. When inserting a key-value pair, the key is hashed to an index, and the value is stored at that index. To retrieve the value, the same hash function is used to find the correct index. If two keys map to the same index, a collision occurs, which we will handle using separate chaining.

Java Hash Table Implementation

Components:

Node Class: Represents a single entry (key-value pair) in the hash table.
HashTable Class: Manages key-value pairs, handles collisions and implements hash table operations.

1. Node Class

public class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;  // For handling collisions

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

The Node class represents an entry in the hash table with a key, value, and a reference to the next node for collision handling.

2. HashTable Class

import java.util.*;

public class HashTable<K, V> {
    private Node<K, V>[] buckets;  // Array of linked lists
    private int capacity;          // Number of buckets
    private int size;              // Number of key-value pairs

    // Constructor to initialize hash table
    public HashTable(int capacity) {
        this.capacity = capacity;
        this.buckets = new Node[capacity];
        this.size = 0;
    }

    // Hash function to compute the index for a key
    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    // Insert a key-value pair
    public void put(K key, V value) {
        int index = hash(key);
        Node<K, V> newNode = new Node<>(key, value);
        Node<K, V> current = buckets[index];

        // If no node exists at the index, add the new node
        if (current == null) {
            buckets[index] = newNode;
            size++;
        } else {
            // Collision handling: Check for key, or add new node to the chain
            Node<K, V> prev = null;
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value;  // Update value if key exists
                    return;
                }
                prev = current;
                current = current.next;
            }
            prev.next = newNode;  // Add new node at the end of the chain
            size++;
        }
    }

    // Get value for a key
    public V get(K key) {
        int index = hash(key);
        Node<K, V> current = buckets[index];

        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;  // Key not found
    }

    // Remove a key-value pair
    public void remove(K key) {
        int index = hash(key);
        Node<K, V> current = buckets[index];
        Node<K, V> prev = null;

        while (current != null) {
            if (current.key.equals(key)) {
                if (prev == null) {
                    buckets[index] = current.next;  // Remove head node
                } else {
                    prev.next = current.next;  // Bypass the current node
                }
                size--;
                return;
            }
            prev = current;
            current = current.next;
        }
    }

    // Return the size of the hash table
    public int size() {
        return size;
    }

    // Check if the hash table is empty
    public boolean isEmpty() {
        return size == 0;
    }
}

Explanation:

Insert (put): Computes the index for a key and stores the key-value pair. If the index already has a key, it adds the new key-value pair to the chain (linked list).
Retrieve (get): Computes the index for the key and traverses the chain to find the key. If found, it returns the value.
Remove (remove): Computes the index and traverses the chain to find and remove the key-value pair.

3. Main Class

public class Main {
    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable<>(10);

        // Insert key-value pairs
        hashTable.put("apple", 1);
        hashTable.put("banana", 2);
        hashTable.put("grape", 3);
        hashTable.put("apple", 4);  // Update value

        // Get values
        System.out.println("Value for 'apple': " + hashTable.get("apple"));  // Output: 4
        System.out.println("Value for 'banana': " + hashTable.get("banana"));  // Output: 2

        // Remove a key-value pair
        hashTable.remove("banana");
        System.out.println("Value for 'banana' after removal: " + hashTable.get("banana"));  // Output: null

        // Check size of the hash table
        System.out.println("Size of the hash table: " + hashTable.size());  // Output: 2
    }
}

Output Example:

Value for 'apple': 4
Value for 'banana': 2
Value for 'banana' after removal: null
Size of the hash table: 2

Conclusion

In this post, we designed a fully functional hash table in Java. The hash table supports basic operations like inserting, retrieving, and deleting key-value pairs. We handled collisions using separate chaining with linked lists. The hash table is efficient and demonstrates how to manage data using hashing.

Key Takeaways:

Hash tables use a hash function to map keys to indexes for fast lookups.
Collisions are handled using chaining, where multiple entries can be stored at the same index in a linked list.
This design can be expanded to support resizing and load factor management for better performance.

Understanding how a hash table works will equip you to use this data structure in real-world applications and technical interviews.

Java Guides

Search This Blog