Hash Tables: Fast Key-Value Storage

Hash Tables: Fast Key-Value Storage

Imagine you want to store pairs of information that belong together — like a person's name and their phone number. The name is the key (what you search with), and the phone number is the value (what you want to find). One way to do this is to keep two separate arrays: one for names and one for numbers. But that approach is clumsy and slow. To find someone's number, you often have to check the names one by one until you find a match. We need a smarter data structure built exactly for this job.

That smarter structure is called a hash table.

A real-life example: the phone book

Think about a printed phone book directory for a whole city. It lists everyone's name in alphabetical order. If you want Ram's phone number, you don't read every single page from the start. Instead, you use the index at the front. The index tells you something like "names starting with R are on page 5." You jump straight to page 5 and read Ram's number.

Notice what just happened. You started with a name (Ram), and through the index you turned it into a page number (an intermediate value). The page number then led you directly to the data you wanted. This is the key idea: instead of scanning everything, we translate the key into a location and go there directly.

What a hash table is

A hash table is a data structure that stores a mapping between a key and a value, and lets you search, insert, and delete data very fast — in most cases in constant O(1) time. Constant time means the work stays the same no matter how much data you store. Whether the table holds 10 names or 10 million names, looking one up takes roughly the same tiny amount of time.

How does it pull this off? It uses the same trick as the phone book index. A hash table has a special tool called a hash function.

• You give the key (for example, Ram) to the hash function.
• The hash function turns that key into an intermediate value, called the hash value.
• That hash value is used as an array index — a position number in an array.
• The actual data is stored in that array slot, so the table jumps straight to it.

Because reading an array at a known index is instant, this gives the fast O(1) access. The hash function is playing the same role as the phone book's index: it translates a name into a "where to look" number.

The logical view: a simple table

While the data is really stored inside an array behind the scenes, it is much easier to *picture* a hash table as a plain two-column table. Each row holds one mapping — a key on the left and its value on the right:

| Key | Value |

| --- | --- |

| Ram | 14551 |

| Neha | 14555 |

| Prakhar | 14567 |

| Shikhar | 14564 |

This simple picture is easy to read and reason about. When you look up Neha, you go to her row and read 14555. We will use this clean table picture throughout the course whenever we talk about hash tables, because it makes problems easier to think through — even though, under the hood, a hash function and an array are doing the fast work.

Why this matters

The phone book index, the hash function, and the array index are all the same idea wearing different clothes: take the thing you know (the key), convert it into a direct location, and go straight there. That one move is what makes a hash table so fast and so useful.