THE education site for computer science and ICT

# 1. Introduction to Hash tables

Hash tables allows very fast, efficient searching to take place over a data set. Consider the small list of items:

                            Cat,Dog,Fox,Bird,Ox,Cow,Tiger

We could place these items in a list or array. They are not in any order, alphabetic or otherwise and so to find the last item 'Tiger', the entire list needs to be searched. This means as the list grows larger, searching time increases. In 'Big O' notation, search time 'O' increases by $O(n)$ where n is the length of the list. For a collection of millions of items, this becomes significant.

It would be good if we could use a technique that can potentially find an item in time $O(1)$ i.e. it is found in 1 step.

This is where hashing and a hash table comes in.

A perfect hash table would find an item in one go.

Uses of hash tables include:

• Caches
• Database indexing
• Dynamic languages such as Python use it to create objects