Hash Maps: Introduction

Let’s understand the Hash Maps pattern, its real-world applications, and some problems we can solve with it.

Overview

The hash map pattern is a method to store data. It aims to reduce the time taken to find and access values.

Hash maps store data in the form of key-value pairs. They are similar to arrays because array values are stored against numeric keys. These keys are known as indexes. We don’t get to pick the value of these keys as they are always sequential integers starting from 00. Therefore, if we want to find an element within an array and don’t know it’s index, we’ll have to search the entire array which, in the worst case, will take O(N)O(N) time.

On the contrary, hash maps allow us to have flexible keys. Each key is unique and is mapped against a value. Therefore, we can look up its value in O(1)O(1) time.

A practical application of using hash maps over arrays would be to lookup the marks of students. Had we used arrays, we would have to create the following two arrays:

  • names: This stores the names of the students.

  • marks: This stores the marks of the students.

We would have to make sure that the names and marks arrays store their values in the same order. This means if “John” is at index 4 in the names array, his marks should also be present at the same index in the marks array. This process is very tedious since we first have to make a lookup in the names array in O(N)O(N) time and then, using the corresponding index, perform another lookup in the marks array in O(1)O(1) time.

Using a hash map makes our life much easier. We can use the names of the students as keys, and their marks are the corresponding values. Now we only have to perform one lookup for the marks of a student in O(1)O(1) time.

The following illustration shows how values are inserted and accessed from a hash map in the above example:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.