Java HashMap Implementation in a Nutshell

A HashMap (or hash table) is a data structure that maps keys to values for highly efficient lookup. There are a number of ways to implement this data structure. This post is about the simple implementation of HashMaps in Java using an array of a linked list.

So, let's first define a class representing a node of a linked list as:

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

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

    // getters, equals, hashCode and toString
}

Inserting Element

To insert an element, a key and value, we do the following:

1. First, compute the key's hash code, which will usually be an int. The two different objects could have the same hash code, as there may be an infinite number of elements and a finite number of ints.
2. Then, calculate the index in the array using hash code using modulo as  hashCode (key) % array_length. Here, two different hash codes could map to the same index.
3. Get the linked list at this index calculated above. Store the element in this index. The use of a linked list is important because of collisions: you could have two different keys with the same hash code or two different hash codes that map to the same index.

The picture below shows explains this.

This can be implemented as:

public class MyMap<K, V> {
    private Entry<K, V>[] buckets;
    private static final int INITIAL_CAPACITY = 1 << 4; // 16

    private int size = 0;

    public MyMap() {
        this(INITIAL_CAPACITY);
    }

    public MyMap(int capacity) {
        this.buckets = new Entry[capacity];
    }

    public void put(K key, V value) {
        Entry<K, V> entry = new Entry<>(key, value, null);

        int bucket = getHash(key) % getBucketSize();

        Entry<K, V> existing = buckets[bucket];
        if (existing == null) {
            buckets[bucket] = entry;
            size++;
        } else {
            // compare the keys see if key already exists
            while (existing.next != null) {
                if (existing.key.equals(key)) {
                    existing.value = value;
                    return;
                }
                existing = existing.next;
            }

            if (existing.key.equals(key)) {
                existing.value = value;
            } else {
                existing.next = entry;
                size++;
            }
        }
    } 
    // . . .
}

Retrieving Element

The retrieval of the element from HashMap can be done with the following steps:

1. Compute the hash code from the key, and then compute the index from the hash code with module operation.
2. Then, get the linked list at index computed above and search through the linked list for the value with this value.

The implementation can be as simple as the following:

public V get(K key) {
    Entry<K, V> bucket = buckets[getHash(key) % getBucketSize()];

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

Testing

The custom HashMap implemented above can be tested easily as:

@Test
public void testMyMap() {
    MyMap<String, String> myMap = new MyMap<>();
    myMap.put("USA", "Washington DC");
    myMap.put("Nepal", "Kathmandu");
    myMap.put("India", "New Delhi");
    myMap.put("Australia", "Sydney");

    assertNotNull(myMap);
    assertEquals(4, myMap.size());
    assertEquals("Kathmandu", myMap.get("Nepal"));
    assertEquals("Sydney", myMap.get("Australia"));
}

Time Complexity

Since different keys can be mapped to the same index, there is a chance of collision. If the number of collisions is very high, the worst case runtime is O(n), where n is the number of keys.
However, we generally assume a good implementation that keeps collisions to a minimum, in which case the lookup time is O(1).

Conclusion

This post illustrated how HashMap (or HashTable) can be implemented with an array-based linked list. You can take a look more examples on Cracking the Coding Interview by Gayle Laakmann McDowell.

The source code for all example presented above is available on GitHub.

If you enjoyed this article and want to learn more about Java Collections, check out this collection of tutorials and articles on all things Java Collections.