Hash Table

Hash table - Wikiwand

Tip

The nice thing about hash tables is that most algorithms are $O(1)$ unless hash collisions occur.

Algorithm	Average	Worst case
Space	Θ(n)	O(n)
Search	Θ(1)	O(n)
Insert	Θ(1)	O(n)
Delete	Θ(1)	O(n)