The Hash table data structure stores elements in key-value pairs where

• Key– unique integer that is used for indexing the values
• Value – data that are associated with keys.

The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table.

1. Hash function

As we’ve already seen, the hash function determines the index of our key-value pair. Choosing an efficient hash function is a crucial part of creating a good hash table. You should always ensure that it’s a one-way function, i.e., the key cannot be retrieved from the hash. Another property of a good hash function is that it avoids producing the same hash for different keys.

2. Array

The array holds all the key-value entries in the table. The size of the array should be set according to the amount of data expected.

Collisions in hash tables & resolutions

A collision occurs when two keys get mapped to the same index. There are several ways of handling collisions.

1. Linear probing

If a pair is hashed to a slot which is already occupied, it searches linearly for the next free slot in the table.

2. Chaining

The hash table will be an array of linked lists. All keys mapping to the same index will be stored as linked list nodes at that index.

3. Resizing the hash table

The size of the hash table can be increased in order to spread the hash entries further apart. A threshold value signifies the percentage of the hash table that needs to be occupied before resizing. A hash table with a threshold of 0.6 would resize when 60% of the space is occupied. As a convention, the size of the hashtable is doubled. This can be memory intensive.

Time Complexity

Strengths:

• Fast lookups. Lookups take $O(1)$ time on average.
• Flexible keys. Most data types can be used for keys, as long as they’re  hashable .

Weaknesses:

• Slow worst-case lookups. Lookups take $O(n)$ time  in the worst case .
• Unordered. Keys aren’t stored in a special order. If you’re looking for the smallest key, the largest key, or all the keys in a range, you’ll need to look through every key to find it.
• Single-directional lookups. While you can look up the value for a given key in $O(1)$ time, looking up the keys for a given value requires looping through the whole dataset—$O(n)$ time.
• Not cache-friendly. Many hash table implementations use  linked lists , which don’t put data next to each other in memory.

public class MyHashMap<K, V> {

    private int             size  = 10;
    private MapNode<K, V>[] array = new MapNode[size];

    public void put(K key, V value) {
        int arrayIndex = hash(key);
        putVal(key, value, arrayIndex);
    }

    private int hash(K key) {
        int a = 20;
        int b = 30;
        int primeNumber = 101;
        int m = size;
        int h = key.hashCode();
        return ((a * h * b) % primeNumber) % m;
    }

    public V get(K key) {
        int arrayIndex = hash(key);
        MapNode<K, V> head = array[arrayIndex];

        if (head == null) {
            return null;
        }

        MapNode<K, V> currentNode = head;

        while (null != currentNode && !currentNode.getKey().equals(key)) {
            currentNode = currentNode.getNext();
        }

        if (currentNode == null) {
            return null;
        } else {
            return currentNode.getValue();
        }
    }

    public void putVal(K key, V val, int arrayIndex) {
        MapNode<K, V> head = array[arrayIndex];

        if (head == null) {
            array[arrayIndex] = head = new MapNode<>(key, val);
        } else {

            MapNode<K, V> currentNode = head;

            MapNode<K, V> prevNode = head;

            while (null != currentNode && !currentNode.getKey().equals(key)) {
                prevNode = currentNode;
                currentNode = currentNode.getNext();
            }

            if (currentNode == null) {
                currentNode = new MapNode<>(key, val);
                prevNode.setNext(currentNode);
            } else {
                currentNode.setValue(val);
            }

        }
    }
}

@AllArgsConstructor
@ToString
@Data
public class MapNode<K, V> {
    private K             key;
    private V             value;
    private MapNode<K, V> next;

    public MapNode(K key, V value) {
        this(key, value, null);
    }
}

Source code on Github