A hash table is a key value lookup. It gives you a way of storing a value, against any given key, for very quick lookups.


The key and value can be basically any kind of data structure. Strings are popular. But so long as the key has a hash function, it could be anything.

How does hashing work

At a high-level, we want to store our objects in a array. But how do we jump from a string, to an actual index in the array? This is what a hash function does.

A hash function takes some string, converts it into an integer, and then that integer gets converted into an index for that array, and hence the object we are looking for.

So the hashcode isn’t the index in the array. We go from the key, to the hashcode, and then to the index.


And the reason for this is that the array storing the values might be much much smaller than all the possible combinations of hash’s out there.


One interesting things about hash codes is that it is possible for multiple different keys to have the same hashcode. There are in infinite number of strings, but only a finite number of hashcodes. Also, because we are further reducing the number of keys into a smaller array, the potential for key collisions when mapping can occur.


That’s why a lot of time and effort goes into finding hash algorithms that spread distributions of keys out. In an effort to avoid. But collisions do periodically occur. So we need to deal with them.

The most common way to deal with this collisions is to use chaining. Which basically stores all the collisions for a given key in a linked list. And then when a collisions occurs, walk each element of the linked list until you find the object with the perfect key match. That means the original keys are stored in these chains too.

And for those elements for where there is no collision, we have a one element linked list.


Usually we assume that we have a good hash function that gives a good distribution, so for the purposes of an interview you can assume this is constant time. But if you had a bad hash worst case it could be O(n).




public class HashTable {

    private int INITIAL_SIZE = 16;
    private HashEntry[] data; // LinkedList

    class HashEntry {
        String key;
        String value;
        HashEntry next;

        HashEntry(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;

    HashTable() {
        data = new HashEntry[INITIAL_SIZE];

    void put(String key, String value) {

        // Get the index
        int index = getIndex(key);

        // Create the linked list entry
        HashEntry entry = new HashEntry(key, value);

        // If no entry there - add it
        if (data[index] == null) {
            data[index] = entry;
        // Else handle collision by adding to end of linked list
        else {
            HashEntry temp = data[index];
            while(temp.next != null) {
                temp = temp.next;
            temp.next = entry;

        // the above while loop walks down the chain to the end
        // and then assigns the new entry as the last element

    String get(String key) {

        // Get the index
        int index = getIndex(key);

        // Get the value
        HashEntry temp = data[index];

        // if value
        if (temp != null) {
            // else walk chain until find match
            while (!temp.key.equals(key) && temp.next !=null) {
                temp = temp.next;

            return temp.value;

        // else return null
       return null;

    private int getIndex(String key) {
        // Get the hash code
        int hashCode = key.hashCode();

        // Convert to index
        int index = hashCode % INITIAL_SIZE;

        // Hack to force collision for testing
        if (key.equals("PeterCollision") || key.equals("PaulCollision")) {
            index = 4;

        return index;

    public String toString() {
        int bucket = 0;
        StringBuilder hashTableStr = new StringBuilder();
        for (HashEntry entry : data) {
            if(entry == null) {
            hashTableStr.append("\n bucket[")
                    .append("] = ")
            HashEntry temp = entry.next;
            while(temp != null) {
                hashTableStr.append(" -> ");
                temp = temp.next;
        return hashTableStr.toString();


import junit.framework.Assert;
import org.junit.Before;
import org.junit.Test;

public class HashTableTest {

    private HashTable hashTable;

    public void setUp() throws Exception {
        hashTable = new HashTable();

    public void PutAndGet() {
        hashTable.put("Peter", "PeterValue");
        Assert.assertEquals("PeterValue", hashTable.get("Peter"));

    public void Collision() {
        // these keys will collide (hacked in solution for testing)
        hashTable.put("PeterCollision", "PeterValue");
        hashTable.put("PaulCollision", "PaulValue");

        Assert.assertEquals("PeterValue", hashTable.get("PeterCollision"));
        Assert.assertEquals("PaulValue", hashTable.get("PaulCollision"));


Links that help