Interview: Implement a HashMap-like data structure in Java

HashMap is one of the most used Map type in Java. A good experiment to implement our own one.

Not so long ago, I took a sit in an interview, and the interviewer asked me to implement a HashMap-like container which contains Integer types keys and Integer values. The trick was that I could not use any containers from the Collection API framework.

Steps we have to consider:

• Basic API for our map!
• Usage of equals and hashCode
• Our map has to be (not just) memory efficient

How to make it very flexible? If we used array we have to extend it continously and copy values when we remove one element. How to deal with buckets? Is that realy necessary? If so, how to implement that? Should it be a linked list as well?

One of the most important points was to make it extensible as much as possible. My approach was to implement buckets as a linked data structure and the key-value pairs inside buckets are linked data structures as well.

The Bucket class looks as follows:

private class Bucket<Key, Value> {
    private int hashCode;
    private Node<Key, Value> head;
    private Bucket<Key, Value> next;

    public Bucket(int hashCode, Bucket<Key, Value> next) {
        this.hashCode = hashCode;
        this.next = next;
    }
}

And the Node class is like:

private class Node<Key, Value> {
    private Key key;
    private Value value;
    private Node<Key, Value> next;

    public Node(Key key, Value value, Node<Key, Value> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // ...
}

Both LinkedMap and Bucket have a head field that points to the last inserted element or last created bucket.

Put

Once we want to put a new key-value pair into the map, first, we check whether the bucket exists. If so, we use put method of the bucket, otherwise we have to create a new one, chain that up to the head.

// LinkedMap#put
public Value put(Key key, Value value) {
    if (key == null) {
        throw new NullPointerException("Key cannot be null!");
    }
    Bucket<Key, Value> bucket = findBucketByHashCode(key.hashCode());
    if (null == bucket) {
        bucket = insertBucketByHashCode(key.hashCode());
    }
    return bucket.put(key, value);
}

// Bucket#put
public Value put(Key key, Value value) {
    if (key == null) {
        throw new NullPointerException("Key cannot be null!");
    }
    Node<Key, Value> currentNode = head;
    while (currentNode != null ) {
        if (currentNode.key.equals(key)) {
            currentNode.value = value;
            break;
        }
        currentNode = currentNode.next;
    }
    if (currentNode == null) {
        currentNode = new Node<Key, Value>(key, value, head);
        head = currentNode;
    }
    return currentNode.value;
}

get and remove methods are similar.

In this post we see how to implement a LinkedMap data structure.

Code can be found: https://gist.github.com/torokmark/06940b90482955fee18a6462350a2f09