teach-ict.com logo

THE education site for computer science and ICT

1. Introduction to Hash table

Before you read this section you should be familiar with hashing itself - we have a section on it HERE

Hash table is a type of data structure. It allows data of any size to be mapped with a related but fixed size form. For example a certain hashing function might map its input data into a fixed 32 bit number. This allows searching and comparing to be faster and more efficient.

For example, imagine a group of data items, where each item is a copy of the text of the novel 'War and Peace', but with a single random word in the text changed.

You can store the copies in a list or an array. But if you later want to run a search looking for a particular copy, the search will be very, very slow as it crawls through the entire text of each copy.

Now imagine that the data set includes hundreds or thousands of copies of the novel, each with their own single change. Searching through this data in a list or array structure becomes far too inefficient and slow.

This is where hash tables comes in. Made correctly, hash tables reduce the search time of even massive data sets to something manageable. Some of the practical uses of hash tables include:

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