A HashMap is a tool that helps to store and find data quickly while writing computer programs...

This article explains how to implement a HashMap in Java. You will learn how to create a HashMap class, define a hash function, and handle collisions in Java.

How to Implement HashMap in Java from Scratch

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.

What is a HashMap?

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.

How does HashMap implementation work 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<K, V>[] table;

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

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

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

        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
}

Creating a HashMap class 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;
}

Defining a Hash Function 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]

Handling hash collisions in Java

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<K, V>[] table;

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

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

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

        Node(K key, V value, Node<K, V> 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<K, V> 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<K, V> node = table[index];
        Node<K, V> 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.

Putting it all together

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;
}

Handling resizing in Java

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.

Adding key-value pairs to 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.

Retrieving values 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.

Removing key-value pairs from the HashMap

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.

Conclusion

A HashMap is a tool that helps to store and find data quickly while writing computer programs. It is especially useful for organizing information, like a dictionary, where you have a word (key) and a definition (value). The HashMap works by using a special code (hash function) to save the information in an organized way, like putting things in labeled boxes. Sometimes, different words might end up in the same box, but the HashMap keeps them separate using a list, like a list of people with the same last name. This article will teach you Java HashMap implementation from scratch.

No, a HashMap cannot contain duplicate keys. If a duplicate key is added, the new value will replace the existing value associated with the key.

No, the size of a HashMap cannot be changed once it has been created. However, you can create a new HashMap with a different size and copy the contents of the old HashMap into the new one.

If a key's hash code changes, the key will no longer be associated with the value it was originally added with. It will be considered a new key, and you will not be able to retrieve the value associated with the old key.

Frequently Asked Questions

What’s up with Turing?
Get the latest news about us here.

Press

Know more about remote work.
Checkout our blog here.

Blog

Have any questions?
We’d love to hear from you.

FOR DEVELOPERS

How to Implement HashMap in Java from Scratch

Author

Elliot Brenya Sarfo

What Is Thread Safety in Java & How to Implement It?

Prototype vs Class in JavaScript

How to Create a Slider in JavaScript?

How to Implement Routing in Svelte Web App

How to Convert String to Date in JavaScript

Frequently Asked Questions

Press

Blog

Contact

Hire remote developers