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.

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.

Operation |
Average |
Worst |
---|---|---|

Search | O(1) |
O(n) |

Insertion | O(1) |
O(n) |

Deletion | O(1) |
O(n) |

Space | O(n) |
O(n) |

**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 .

**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); } }