Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

hash table
data structures

What is a hash table?

Educative Answers Team

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.

Components of a 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.

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.

svg viewer

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.