1. Introduction

A HashMap is a part of Java’s collection since Java 1.2. It provides the basic implementation of the Map interface of Java. It stores the data in the form of key-value pairs, and its underlying principle is based on the hashing technique. In this post, we will implement a basic version of a HashMap from scratch.

2. Program Steps

1. Create a class Entry to store key-value pairs.

2. Initialize an array of Entry objects to represent the underlying data structure.

3. Implement methods put, get, and remove to interact with the map.

4. Handle potential collisions using linked lists.

3. Code Program

class CustomHashMap<K, V> {
    // The bucketArray is used to store array of chains
    private Entry<K, V>[] bucketArray;
    private int numBuckets;  // Current capacity of array list
    private int size;  // Current size of array list

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

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

    // Constructor
    public CustomHashMap() {
        bucketArray = new Entry[10];
        numBuckets = 10;
        size = 0;
    }

    private int getBucketIndex(K key) {
        int hashCode = key.hashCode();
        return hashCode % numBuckets;
    }

    public V get(K key) {
        int bucketIndex = getBucketIndex(key);
        Entry<K, V> head = bucketArray[bucketIndex];
        while (head != null) {
            if (head.key.equals(key))
                return head.value;
            head = head.next;
        }
        return null;
    }

    public void put(K key, V value) {
        int bucketIndex = getBucketIndex(key);
        Entry<K, V> head = bucketArray[bucketIndex];

        // If key is already present
        while (head != null) {
            if (head.key.equals(key)) {
                head.value = value;
                return;
            }
            head = head.next;
        }

        size++;
        head = bucketArray[bucketIndex];
        Entry<K, V> newNode = new Entry<K, V>(key, value);
        newNode.next = head;
        bucketArray[bucketIndex] = newNode;

        // If load factor goes beyond threshold, then double hash table size
        if ((1.0 * size) / numBuckets >= 0.7) {
            Entry<K, V>[] temp = bucketArray;
            bucketArray = new Entry[2 * numBuckets];
            size = 0;
            numBuckets = 2 * numBuckets;

            for (Entry<K, V> headNode : temp) {
                while (headNode != null) {
                    put(headNode.key, headNode.value);
                    headNode = headNode.next;
                }
            }
        }
    }

    public V remove(K key) {
        int bucketIndex = getBucketIndex(key);
        Entry<K, V> head = bucketArray[bucketIndex];
        Entry<K, V> prev = null;

        while (head != null) {
            if (head.key.equals(key))
                break;
            prev = head;
            head = head.next;
        }

        if (head == null)
            return null;
        size--;

        if (prev != null)
            prev.next = head.next;
        else
            bucketArray[bucketIndex] = head.next;

        return head.value;
    }

    public static void main(String[] args) {
        CustomHashMap<String, Integer> map = new CustomHashMap<>();
        map.put("John", 1);
        map.put("Doe", 2);
        map.put("Jane", 3);

        System.out.println("John&apos;s id: " + map.get("John"));
        System.out.println("Removed id: " + map.remove("Jane"));
        System.out.println("Jane&apos;s id after removal: " + map.get("Jane"));
    }
}

Output:

John's id: 1
Removed id: 3
Jane's id after removal: null

4. Step By Step Explanation

1. The CustomHashMap class is designed to handle key-value pairs using an array of linked lists (Entry objects).

2. The Entry class holds the key, value, and a next reference to form the linked list.

3. The getBucketIndex method calculates the bucket index for a given key based on its hashCode.

4. The get method retrieves the value associated with the provided key.

5. The put method adds a new key-value pair or updates an existing pair. It also handles resizing the bucketArray when the load factor exceeds 0.7.

6. The remove method removes the key-value pair associated with the given key and returns its value.

Note: This is a simplified implementation of a HashMap. Real-world implementations would have more optimizations and handle edge cases more comprehensively.