Java HashMap Implementation in a nutshell

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

So, lets 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.

hashmap-example

Source: Cracking the Coding Interview, 6th edition

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 modulo 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 below:

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

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

Testing

The custom hash map 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 a(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.

Memoization: Make Recursive Algorithms Efficient
Custom HashSet Implementation in Java