Hash Table Implementation in Java

1. Introduction

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. The primary operation it supports efficiently is a lookup. In essence, it works by transforming the key using a hash function into an index of an array where the corresponding value is stored.

2. Implementation Steps

1. Define a HashTable class.

2. Each entry in the hash table will be a KeyValuePair to store both key and value.

3. Implement methods like put(), get(), and remove().

4. Handle collisions using chaining - each cell of the hash table will contain a list of key-value pairs.

3. Implementation in Java

import java.util.LinkedList;
class KeyValuePair<K, V> {
    K key;
    V value;
    KeyValuePair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    K getKey() {
        return key;
    }
    V getValue() {
        return value;
    }
    void setValue(V value) {
        this.value = value;
    }
}
class HashTable<K, V> {
    private LinkedList<KeyValuePair<K, V>>[] table;
    private static final int INITIAL_CAPACITY = 16;
    private int size = 0;
    @SuppressWarnings("unchecked")
    public HashTable() {
        table = new LinkedList[INITIAL_CAPACITY];
    }
    private int hash(K key) {
        return key.hashCode() % table.length;
    }
    public V get(K key) {
        int index = hash(key);
        LinkedList<KeyValuePair<K, V>> bucket = table[index];
        if (bucket == null) {
            return null;
        }
        for (KeyValuePair<K, V> pair : bucket) {
            if (pair.getKey().equals(key)) {
                return pair.getValue();
            }
        }
        return null;
    }
    public void put(K key, V value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }
        LinkedList<KeyValuePair<K, V>> bucket = table[index];
        for (KeyValuePair<K, V> pair : bucket) {
            if (pair.getKey().equals(key)) {
                pair.setValue(value);
                return;
            }
        }
        bucket.add(new KeyValuePair<>(key, value));
        size++;
    }
    public V remove(K key) {
        int index = hash(key);
        LinkedList<KeyValuePair<K, V>> bucket = table[index];
        if (bucket == null) {
            return null;
        }
        for (KeyValuePair<K, V> pair : bucket) {
            if (pair.getKey().equals(key)) {
                bucket.remove(pair);
                size--;
                return pair.getValue();
            }
        }
        return null;
    }
    public int size() {
        return size;
    }
    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable<>();
        hashTable.put("one", 1);
        hashTable.put("two", 2);
        hashTable.put("three", 3);
        System.out.println("Value for 'one': " + hashTable.get("one"));
        System.out.println("Size of hash table: " + hashTable.size());
        hashTable.remove("one");
        System.out.println("Value after removing 'one': " + hashTable.get("one"));
    }
}

Output:

Value for 'one': 1
Size of hash table: 3
Value after removing 'one': null

Explanation:

1. The KeyValuePair class is a simple container to hold both a key and its corresponding value.

2. The HashTable class is our main class implementing the hash table. It contains a table of LinkedList to handle collisions using chaining.

3. The hash() function determines the index in the table for a given key.

4. The get() method retrieves the value for a given key.

5. The put() method inserts a new key-value pair or updates the value if the key already exists.

6. The remove() method removes the key-value pair from the hash table and returns the value of the removed key.

7. The size() method returns the number of key-value pairs in the hash table.

8. The main() function demonstrates the basic operations (put, get, and remove) of the hash table.