This tutorial walks you through creating a custom HashMap in Java. You’ll learn how to implement:

• A hash function
• Basic operations like put, get, and remove
• Collision handling using a custom singly linked list (not java.util.LinkedList)

We’ll use:

• A fixed-size array of 16 buckets
• Our own Entry class to create a linked list structure for each bucket

This version does not include initial capacity, load factor, or resizing to keep it simple and focused.

Step 1: Define the MyHashMap Class and Entry Nodes

public class MyHashMap<K, V> {

    private static class Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private Entry<K, V>[] table;

    public MyHashMap() {
        table = new Entry[16];
    }
}

Detailed Explanation:

• The array table[16] is the base structure where entries are stored by hash index.
• Each element in the array points to the head of a linked list.
• The Entry<K, V> class stores a key, value, and next reference.
• The next reference connects multiple entries in the same bucket, forming a singly linked list.
• This is a custom list using nodes; we do not use Java’s LinkedList.

Step 2: Compute Hash (Array Index)

private int hash(K key) {
    return key == null ? 0 : Math.abs(key.hashCode() % table.length);
}

Explanation:

• Converts a key into an index within the array.
• We use hashCode() and modulo by array length to stay within bounds.
• Math.abs() ensures a non-negative index.
• If the key is null, we assign it to index 0.

Step 3: Insert Key-Value Pair (put method)

public void put(K key, V value) {
    int index = hash(key);
    Entry<K, V> head = table[index];

    while (head != null) {
        if ((key == null && head.key == null) || (key != null && key.equals(head.key))) {
            head.value = value;
            return;
        }
        head = head.next;
    }

    Entry<K, V> newEntry = new Entry<>(key, value);
    newEntry.next = table[index];
    table[index] = newEntry;
}

Explanation:

• Computes the index using the hash function.
• Checks for existing key in the bucket’s linked list.
• If found, updates the value.
• If not, inserts a new node at the beginning of the linked list.
• The next pointer handles chaining: newEntry.next = table[index].

Step 4: Retrieve Value by Key (get method)

public V get(K key) {
    int index = hash(key);
    Entry<K, V> head = table[index];

    while (head != null) {
        if ((key == null && head.key == null) || (key != null && key.equals(head.key))) {
            return head.value;
        }
        head = head.next;
    }

    return null;
}

Explanation:

• Finds the correct bucket using the hash function.
• Walks through the linked list at that index.
• If the key is found, returns its value.
• If the key is not found, returns null.

Step 5: Remove Key-Value Pair (remove method)

public V remove(K key) {
    int index = hash(key);
    Entry<K, V> current = table[index];
    Entry<K, V> previous = null;

    while (current != null) {
        if ((key == null && current.key == null) || (key != null && key.equals(current.key))) {
            if (previous == null) {
                table[index] = current.next;
            } else {
                previous.next = current.next;
            }
            return current.value;
        }
        previous = current;
        current = current.next;
    }

    return null;
}

Explanation:

• Uses the hash to locate the correct bucket.
• Walks through the linked list to find the matching key.
• If the key is found, removes the corresponding node.
• Adjusts the next pointer to maintain the linked structure.
• Returns the removed value, or null if not found.

Step 6: Test the HashMap

public class Main {
    public static void main(String[] args) {
        MyHashMap<String, String> map = new MyHashMap<>();

        map.put("name", "Alice");
        map.put("city", "Mumbai");
        map.put("language", "Java");

        System.out.println("name -> " + map.get("name"));
        System.out.println("city -> " + map.get("city"));
        System.out.println("language -> " + map.get("language"));

        map.remove("city");
        System.out.println("city -> " + map.get("city"));
    }
}

How Buckets Work Internally

If multiple keys hash to the same index (for example, index 3), the internal structure looks like this:

table[3] → [A, valueA] → [B, valueB] → [C, valueC] → null

• Each element in the array is a pointer to the head of a linked list.
• Each [key, value] pair is an Entry object.
• The next field links the entries in the same bucket.