Hash table explained like I’m 5

A library is an excellent reference point for this structure

Photo by Janko Ferlic from Pexels

I felt compelled to attempt an improvement on the existing resources on this topic because It took me a lot of time and frustration to find a resource that I felt explained it to a satisfactory and digestible degree.

Motivation

A hash table is worth our time because it provides some alternatives to the humble array. In many cases, A hash table requires less time complexity than an array does.

In a typical scenario, adding a new item to a hash table is done in constant time relative to the data structure, but in polynomial time (or less) relative to the size of the key of the data. Considering the key of the data is usually short, we can comfortably call this constant time.

For those unfamiliar with Big O, I’ll provide a brief description right now since it is important for the motivation of this data structure.

Big O:

Constant time or Big O([some number]) is an operation that takes a constant amount of time irrespective of the size of the data.

For example, if we had a pickup truck that could hold 2721.55 kilograms (or 3 tons), it would always take a fixed amount of time to transport anything less than 3 tons to the barn, because the size of the thing we are transporting is irrelevant to the time it takes to drive our truck to the barn. Driving to the barn always takes 3 minutes.

Polynomial-time, or Big O([n, where n is the size of the input]) is an operation that requires some time equivalent to some constant time multiplied by the size of the input.

For example, let’s say we have 100 watermelons, and we let our granddad borrow the truck for the day. We need to move the 100 watermelons to the shed, which is a 20-second walk. In order to complete this task, we will have to pick up a watermelon and walk to the shed 100 times. Therefore, the time to move out watermelons is in Polynomial-time or Big O(n * (20 seconds)) where n is the size of the input, which would be 100 in our watermelon scenario. This task would take 2000 seconds, or approximately 33 minutes assuming we don’t stop for refreshments.