How to Implement HashMap in Java from Scratch

What is a HashMap?

A HashMap is a data structure that allows you to store and retrieve data based on a unique key. It is made up of two main components: a hash function and an array. The hash function takes the key as input and returns a unique index for that key in the array. Once the index is determined, the value associated with the key can be stored or retrieved from that position in the array.

How does HashMap implementation work in Java

Let's say you have a giant box with tons of little compartments, and you want to move things in and out of it quickly. To make this possible, you have to label each compartment with a name or number so that you can find the right one easily. This is similar to how a HashMap works.

In a Java HashMap, each compartment holds a unique key-value pair, and the key serves as the label for that compartment. Whenever you add a new key-value pair to the HashMap, think of the hash code as a secret backstage pass for the key that makes the HashMap's job easier.

If the compartment is empty, it's like a vacant hotel room waiting for a new guest, and the HashMap happily welcomes the new key-value pair in. But if there's already a pair in the compartment, the HashMap is like a strict bouncer that kicks the old pair out and lets the new one takes its place - no ifs, and, or buts.

When you're ready to grab something from the HashMap, just give it the right key, and the HashMap will magically whisk you away to the right compartment like a high-speed elevator. It's like having your own personal magic genie in a box.

This method is highly efficient and speedy, as the HashMap only has to calculate the hash code and locate the specific compartment, rather than looking through all the compartments in the box. That's why it's an ideal way to store and access data in Java programs.

Now, let’s start by creating HashMap classes in Java.

Creating a HashMap class in Java

The first step in implementing a HashMap in Java is to create a HashMap class. This class will be responsible for handling all the operations that we can perform on the HashMap. The instance variables for the class will include the capacity, load factor, size, and an array of nodes.

public class MyHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;

private int capacity;
private float loadFactor;
private int size;
private Node&lt;K, V&gt;[] table;

public MyHashMap() {
    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}


public MyHashMap(int capacity, float loadFactor) {
    this.capacity = capacity;
    this.loadFactor = loadFactor;
    this.table = (Node&lt;K, V&gt;[]) new Node[capacity];
}

private static class Node&lt;K, V&gt; {
    final K key;
    V value;
    Node&lt;K, V&gt; next;

    Node(K key, V value, Node&lt;K, V&gt; next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

}

Defining a Hash Function in Java

The next step in implementing a HashMap in Java is to define a hash function. The hash function is responsible for taking a key and returning a unique index for that key in the array. The hash function should return the same index for the same key every time it is called. There are many different hash functions that can be used, but one simple example is to simply use the length of the key as the index.

private int hash(K key) {
    return key.hashCode() % capacity;
}

Handling hash collisions in Java

Hash collisions occur when two or more keys are hashed to the same index in the array. This can cause problems if we try to store multiple values at the same index. There are two main techniques for handling hash collisions: chaining and open addressing.

Chaining involves creating a linked list at each index in the array. When a collision occurs, a new node is added to the linked list. Open addressing involves searching for the next available index in the array until an empty index is found.

Here's an example of how to implement chaining in Java:

public void put(K key, V value) {
    int index = hash(key);
    Node<K, V> node = table[index];
    while (node != null) {
        if (node.key.equals(key)) {
            node.value = value;
            return;
        }
        node = node.next;
    }
    Node<K, V> newNode = new Node<>(key, value);
    newNode.next = table[index];
    table[index]

Putting it all together

Now that we have defined all the basic components of a HashMap, we can put them together to create a working implementation. Here's an example of a complete implementation of a HashMap in Java:

public class MyHashMap<K, V> {  
private static final int DEFAULT_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private int capacity;
private float loadFactor;
private int size;
private Node&lt;K, V&gt;[] table;

public MyHashMap() {
    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}


public MyHashMap(int capacity, float loadFactor) {
    this.capacity = capacity;
    this.loadFactor = loadFactor;
    this.table = (Node&lt;K, V&gt;[]) new Node[capacity];
}

private static class Node&lt;K, V&gt; {
    final K key;
    V value;
    Node&lt;K, V&gt; next;

    Node(K key, V value, Node&lt;K, V&gt; next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

private int hash(K key) {
return key.hashCode() % capacity;
}
public void put(K key, V value) {
int index = hash(key);
Node<K, V> node = table[index];
while (node != null) {
if (node.key.equals(key)) {
node.value = value;
return;
}
node = node.next;
}
Node<K, V> newNode = new Node<>(key, value);
newNode.next = table[index];
table[index] = newNode;
size++;
if (size > capacity * loadFactor) {
resize();
}
}
public V get(K key) {
    int index = hash(key);
    Node&lt;K, V&gt; node = table[index];
    while (node != null) {
        if (node.key.equals(key)) {
            return node.value;
        }
        node = node.next;
    }
    return null;
}

public void remove(K key) {
    int index = hash(key);
    Node&lt;K, V&gt; node = table[index];
    Node&lt;K, V&gt; prev = null;
    while (node != null) {
        if (node.key.equals(key)) {
            if (prev == null) {
                table[index] = node.next;
            } else {
                prev.next = node.next;
            }
            size--;
            return;
        }
        prev = node;
        node = node.next;
    }
}

private void resize() {
int newCapacity = capacity * 2;
Node<K, V>[] newTable = new Node[newCapacity];
for (int i = 0; i < capacity; i++) {
Node<K, V> node = table[i];
while (node != null) {
Node<K, V> next = node.next;
int index = hash(node.key);
node.next = newTable[index];
newTable[index] = node;
node = next;
}
}
table = newTable;
capacity = newCapacity;
}
}

Now to make this more interesting let's add some key-value pairs to the HashMap.

Handling resizing in Java

A HashMap has a fixed-size array. When the number of elements in the array exceeds a certain threshold, it is time to resize the array. Resizing is done by creating a new array with a larger capacity and rehashing all the keys and values into the new array. To avoid a costly resize operation, it is recommended to choose the initial capacity of the array carefully.

Here's an example of how to handle resizing in Java:

//codes
private void resize() {
int newCapacity = capacity * 2;
Node<K, V>[] newTable = new Node[newCapacity];
for (int i = 0; i < capacity; i++) {
Node<K, V> node = table[i];
while (node != null) {
Node<K, V> next = node.next;
int index = hash(node.key);
node.next = newTable[index];
newTable[index] = node;
node = next;
}
}
table = newTable;
capacity = newCapacity;
}

Adding key-value pairs to the HashMap

Now let's add some key-value pairs. To add a key-value pair to the HashMap, we first need to calculate the hash code of the key using the ‘hashCode() method,’ and then use this hash code to find the index in the array where the key-value pair should be stored. We can then store the key-value pair in that index.

Here is an example of how to add a key-value pair to the HashMap:

// create a new hash map
HashMap<String, Integer> map = new HashMap<>();
// add a key-value pair to the hash map
String key = "apple";
Integer value = 10;
int hashCode = key.hashCode();
int index = hashCode % map.getSize();
map.put(key, value, index);

In this example, we first create a new HashMap with a String key and an Integer value. We then add a key-value pair to the HashMap by defining the key and value, calculating the hash code of the key, finding the index in the array using the hash code, and then calling the put() method to store the key-value pair in the HashMap.

Retrieving values from the HashMap

To retrieve a value from the HashMap, we first need to calculate the hash code of the key using the hashCode() method, and then use this hash code to find the index in the array where the key-value pair is stored. We can then retrieve the value from that index.

Here is an example of how to retrieve a value from the HashMap using a key:

// get the value for a key from the hash map
String key = "apple";
int hashCode = key.hashCode();
int index = hashCode % map.getSize();
Integer value = map.get(key, index);

In this example, we define the key that we want to retrieve the value for and calculate the hash code of the key. We then find the index in the array where the key-value pair is stored and call the get() method to retrieve the value from the HashMap.

Removing key-value pairs from the HashMap

To remove a key-value pair from the HashMap, we first need to calculate the hash code of the key using the hashCode() method, and then use this hash code to find the index in the array where the key-value pair is stored. We can then remove the key-value pair from that index.

Here is an example of how to remove a key-value pair from the HashMap using a key:

// remove a key-value pair from the hash map
String key = "apple";
int hashCode = key.hashCode();
int index = hashCode % map.getSize();
map.remove(key, index);

In this example, we define the key that we want to remove and calculate the hash code of the key. We then find the index in the array where the key-value pair is stored and call the remove() method to remove the key-value pair from the HashMap.

Conclusion

Implementing a HashMap in Java from scratch is a useful exercise that can help deepen your understanding of the data structure. By following the steps outlined in this article, you can create a simple HashMap implementation using an array and linked lists. You can add key-value pairs to the HashMap using the put method, retrieve values using the get method, and remove key-value pairs using the remove method. There are also several other useful methods available in the Java HashMap class that you can explore on your own.

To extend the implementation, you can consider resizing the array to improve performance, implementing a rehashing function to redistribute keys evenly across the array, or using a more sophisticated collision resolution strategy like quadratic probing. By experimenting with these modifications, you can gain a deeper understanding of how HashMaps work and how to optimize their performance.