Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
A hash table is a type of data structure that stores key-value pairs. 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.
A basic hash table consists of two parts:
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.
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.
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.