More in The Data Structures series.

In our data structure series, we have already looked at a couple of ways in which we can implement a stack, and also Single Linked Lists (SLL) and Double Linked Lists (DLL). In this post, we’ll see how we can implement our own HashMap and see a couple of examples of how we can use that HashMap. Let’s get started.

The HashMap

Before we can start with the implementation of the HashMap, we need to understand how the stuff actually works. This is a combination of an array and a LinkedList. So it’s a bit interesting. When we add an item to a HashMap, we provide a key and a value. The key will be used as a reference to the value we are storing. When we want to fetch that value from the HashMap, we’ll use the key to fetch it. So let’s see how we can do this.

The first thing to do is to create an array internally in our HashMap class. This is an array of nodes (we’ll create the Node class later). This array is of a fixed length, a length of 16 is the most common. When we put an item into the HashMap, we need to find a place for the Node is the array. Note that we can store hundreds of items in a HashMap, but we only have an array of length 16. So how and where do we fit them all? Well, that’s where the interesting part comes:

1. Take the key and get the hash code of the key.
2. Take the modulus of this hash code and the length of the array (16 in this example) – index = hashCode % arrayLength
3. The result is the index of the array where the Node has to be saved.
4. If there’s no node at that index, save this Node.
5. If there’s already a Node at that index, which is variation of Linked List, traverse to the end of the Linked List and add the new node as the new tail.

That’s how you save key-value pairs in a HashMap. So in this post, we’ll see how we can do just that.

The Node

We’ll be using a modified version of the Node class we have been using in our linked lists. Because we have a key and a value to store in a HashMap, we’ll need two variables in the class. So we’ll change that. Also, because the Node is a variation of the Linked List, we’ll need a reference to the next node. So we’ll have that as well. And, because the hash code of the key is an important value here, we’ll just store that as well in the Node, just in case. Our new Node class for a HashMap looks like this:

public class Node<K, V> {

    private K key;
    private V value;
    private Node<K, V> next;
    private long hashCode;

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Node<K, V> getNext() {
        return next;
    }

    public void setNext(Node<K, V> next) {
        this.next = next;
    }

    public long getHashCode() {
        return hashCode;
    }

    public void setHashCode(long hashCode) {
        this.hashCode = hashCode;
    }
}

The K and the V classes

If you observe the Node class, we have two new classes, K and V. You might be wondering what these are. If you have read any of my previous data structure posts, you’ll know that we have been using the generic T class for defining our Node classes, so that at run time we can decide what type of data we want to store in the lists. These two K and V classes are no different than that T class, they’re just generic classes, something like placeholder classes. You’ll understand that when we look at some examples. For now, let’s just assume that the K class is the key class and the V class is the value class. That should make things easier to understand.

The HashMap class

Now let’s look at the HashMap class itself. First, we declare an integer constant to hold the array length, then we declare the Node array itself, of that length:

public class HashMap<K, V> {

    private static final int ARRAY_SIZE = 16;

    private Node<K, V>[] nodeList = new Node[ARRAY_SIZE];
    
}

Now, we have to start adding key-value pairs to the HashMap, we have a method for that:

public void put(K key, V value) throws InvalidIndexException {

    long hashCode = this.getHashCode(key);
    int index = this.getIndex(hashCode);

    if (index > ARRAY_SIZE) {
        throw new InvalidIndexException("Invalid key, please check again!");
    }

	// Checking if there is already a Node at the given index.
    if (this.nodeList[index] != null) {

		// We're getting the node at the given index, so that we can traverse to the end
		// and add the new node.
        Node<K, V> exitingNode = this.nodeList[index];

        while (exitingNode.getNext() != null) {
            exitingNode = exitingNode.getNext();
        }

		// We're creating the new node.
        Node<K, V> newNode = new Node<>();
        newNode.setKey(key);
        newNode.setValue(value);
        newNode.setHashCode(hashCode);

        exitingNode.setNext(newNode);

    } else {
		// If there's no node at the given index, we'll just create a new node and add to the array
		// at the given index.
        Node<K, V> newNode = new Node<>();
        newNode.setKey(key);
        newNode.setValue(value);
        newNode.setHashCode(hashCode);

        this.nodeList[index] = newNode;
    }
}

private long getHashCode(K key) {

    String keyString = key.toString();
    return keyString.hashCode();
}

private int getIndex(long hashCode) {

    return Math.toIntExact(hashCode % ARRAY_SIZE);
}

I have added comments in the code above wherever it is required. The comments should make the code clear enough to understand.

One more method we could write is to print the whole HashMap just to test if we have all the data that we put into the HashMap. So for that, we’ll use the following method:

public void printHashMap() {

    System.out.println("==============================================");
    System.out.println("Printing map:");

    int index = 0;

    while (index < ARRAY_SIZE) {

        Node<K, V> node = this.nodeList[index];

        if (node != null) {

            int listIndex = 0;

            while (node != null) {

                if (listIndex > 0) {
                    System.out.print(" || ");
                }

                System.out.print(node.getKey().toString() + " -> ");
                System.out.print(node.getValue().toString());

                node = node.getNext();
                listIndex++;

            }

            System.out.println("");
        }

        index++;
    }

    System.out.println("==============================================");
}

The Testing

The next thing we’ll do, is testing the HashMap class we just wrote. I have a code snippet for that. First, we’ll try to create a HashMap with the config HashMap<Integer, String>. This way, we’ll have an integer key and a string value. For that, I’ll use the following code snippet:

HashMap<Integer, String> hashMap = new HashMap<>();

try {
    hashMap.put(1, "One");
    hashMap.put(2, "Two");
    hashMap.put(21, "Twenty One");
    hashMap.put(22, "Twenty Two");
    hashMap.put(23, "Twenty Three");
    hashMap.put(256, "Two Hundred And Fifty Six");

    hashMap.printHashMap();
} catch (InvalidIndexException e) {
    e.printStackTrace();
}

If you run this, you should get the following output:

==============================================
Printing map:
22 -> Twenty Two
1 -> One || 23 -> Twenty Three
2 -> Two
256 -> Two Hundred And Fifty Six
21 -> Twenty One
==============================================

That’s pretty much what we expected. Next, we’ll try one more config with HashMap<String, String>. This time, we have a string key and string value. We’ll use a similar set of key-value pair for this as we used for the previous test:

HashMap<String, String> stringHashMap = new HashMap<>();

try {
    stringHashMap.put("One", "One");
    stringHashMap.put("Two", "Two");
    stringHashMap.put("Three", "Twenty One");
    stringHashMap.put("Four", "Twenty Two");
    stringHashMap.put("Five", "Twenty Three");
    stringHashMap.put("Six", "Two Hundred And Fifty Six");

    stringHashMap.printHashMap();
} catch (InvalidIndexException e) {
    e.printStackTrace();
}

For this code snippet, we see the following output:

==============================================
Printing map:
Five -> Twenty Three || Six -> Two Hundred And Fifty Six
One -> One || Four -> Twenty Two
Two -> Two
Three -> Twenty One
==============================================

That’s perfect. As you could see from the outputs of both the examples, we have more than one node at certain indexes appearing in the HashMaps. This is where the Linked List in the Node class comes into play.

If you want to play with the complete project of this HashMap implementation, you can fork it from my Github repo. Also, let me know in the comments below if you have any queries or want to suggest improvements in the code.