Introduction to Hashing

Say you have a class of students and you want to find one person’s marks. If they are sitting in a long row with no order, you start at the first chair and check each one until you reach the right person. That checking one by one is slow. Hashing is the trick that lets you jump straight to the right spot without checking everyone. Let us see how.

😖 The Pain First

Imagine you store names and phone numbers in a plain list. You want Riya’s number. The computer does not know where Riya is. So it starts at the top and reads each entry until it finds her.

If Riya is the last one, you checked every single entry. With a list of one million people, that is one million checks in the worst case. We call this O(n) time, which means the work grows with the number of items n.

That is the pain. Searching a plain list is slow because you may have to look at everything.

Now the question is simple. What if the computer could go straight to Riya’s spot in one move, without reading anyone else? That is exactly what hashing gives you.

📚 What Is Hashing?

Hashing is a way to turn a key into a position in an array. A key is the thing you search by, like a name or an ID. The position is just an array index, like box number 7.

There is a small helper that does this turning. We call it a hash function. A hash function takes a key and gives back a number, and that number tells you which box to use.

So the flow is short:

• You have a key, say "Riya".
• The hash function reads the key and produces an index. Let us say it gives back box 4 for now.
• You go to box 4 and store or read Riya’s value there.

Next time you want Riya, you run the same hash function. It gives back the same box 4 again, so you go straight there. That is just one move, and you never scan the whole list.

🔑 A Real-World Analogy

Think about lockers in a school. Each student gets a locker number. Arjun does not search every locker to find his bag. He remembers his number, walks to that locker, and opens it.

The locker number is like the index. The rule that says “Arjun gets locker 12” is like the hash function. Because Arjun knows the rule, he reaches his locker in one move.

A book index works the same way. You do not read every page to find the word “loops”. You look up “loops” in the index, it tells you page 84, and you turn straight to page 84.

🧭 Key to Index, Step by Step

Here is the whole idea in one picture. The key goes into the hash function, and an index comes out. The number 4 below is just a sample to show the shape of the flow.

Let us make the hash function real with a tiny example. Say our array has 5 boxes, numbered 0 to 4. One simple rule is this:

• Add up the character codes of the letters in the key.
• Divide by the array size and keep the remainder.
• That remainder is the index.

The remainder trick uses the modulo operation, written as %. It always gives a number from 0 up to size minus 1, so the index always lands inside the array.

When you run this rule on a key, the work is the same small amount no matter how big the array is. That is why a lookup is about O(1) time, meaning the time stays nearly constant and does not grow with n.

⚙️ A Tiny Hashing Demo

Let us see this in real code. Most languages already give you a built-in map or dictionary that uses hashing inside. You put in a key and a value, then read it back by key. You never write the hash function yourself, because the language does it for you.

Below we store three students with their marks, then look up one student by name. Notice that we never scan a list. We just ask for the key directly.

#include <stdio.h>
#include <string.h>

#define SIZE 5

// Turn a key (name) into an index from 0 to SIZE-1
int hashKey(const char *key) {
    int sum = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        sum += key[i];      // add character codes
    }
    return sum % SIZE;      // modulo keeps it inside the array
}

int main(void) {
    int marks[SIZE] = {0};

    // Store Riya's marks at her hashed index
    int index = hashKey("Riya");
    marks[index] = 92;

    // Look up Riya again: same key gives the same index
    printf("Index for Riya: %d\n", hashKey("Riya"));
    printf("Riya's marks: %d\n", marks[hashKey("Riya")]);
    return 0;
}

Index for Riya: 0
Riya's marks: 92

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    // The map uses hashing inside to find each key fast
    unordered_map<string, int> marks;

    marks["Riya"] = 92;
    marks["Arjun"] = 85;
    marks["Alex"] = 78;

    // Look up by key in about one step
    cout << "Riya's marks: " << marks["Riya"] << endl;
    cout << "Arjun's marks: " << marks["Arjun"] << endl;
    return 0;
}

Riya's marks: 92
Arjun's marks: 85

import java.util.HashMap;

public class HashingDemo {
    public static void main(String[] args) {
        // HashMap uses hashing inside to reach each key fast
        HashMap<String, Integer> marks = new HashMap<>();

        marks.put("Riya", 92);
        marks.put("Arjun", 85);
        marks.put("Alex", 78);

        // Look up by key, with no scanning of the whole list
        System.out.println("Riya's marks: " + marks.get("Riya"));
        System.out.println("Arjun's marks: " + marks.get("Arjun"));
    }
}

Riya's marks: 92
Arjun's marks: 85

# A Python dict uses hashing inside to find each key fast
marks = {}

marks["Riya"] = 92
marks["Arjun"] = 85
marks["Alex"] = 78

# Look up by key directly, with no scanning of the whole list
print("Riya's marks:", marks["Riya"])
print("Arjun's marks:", marks["Arjun"])

Riya's marks: 92
Arjun's marks: 85

// A JavaScript Map uses hashing inside to reach each key fast
const marks = new Map();

marks.set("Riya", 92);
marks.set("Arjun", 85);
marks.set("Alex", 78);

// Look up by key directly, with no scanning of the whole list
console.log("Riya's marks:", marks.get("Riya"));
console.log("Arjun's marks:", marks.get("Arjun"));

Riya's marks: 92
Arjun's marks: 85

🪣 Two Keys, One Box: Collisions

There is one thing you should know now. Sometimes two different keys hash to the same index. Riya might land on box 2, and so might Arjun. That clash is called a collision.

A collision is not a bug. It happens because the array has fewer boxes than there are possible keys. Good hashing systems plan for it and have a way to keep both values in that spot.

You do not need to solve collisions today. Just remember they exist, and that the hash table handles them. We cover the actual methods in the hash table tutorial.

⏱️ Why It Is Fast

Let us compare the plain list with hashing side by side, so the speed difference is clear.

We say O(1) average and not always. In the rare case where many keys collide into one box, a lookup can slow down. With a good hash function that stays rare, so in real use hashing feels like one quick step.

⚠️ Common Mistakes To Avoid

A few things trip up beginners when they first meet hashing:

• Thinking the index comes from the order you inserted keys. It does not. The index comes only from the key through the hash function.
• Expecting keys to stay sorted. A hash map does not keep order. If you need sorted keys, that is a different structure.
• Believing lookups are always O(1). They are O(1) on average. Heavy collisions can slow it down.
• Trying to write your own hash function for real projects. Use the built-in map or dictionary, because it is already tuned.

🧩 What You’ve Learned

✅ Searching a plain list is O(n) because you may check every item.

✅ Hashing turns a key into an array index using a hash function, so you reach the spot in about O(1) time.

✅ The same key always gives the same index, so storing and looking up both go straight to one box.

✅ Built-in maps and dictionaries already use hashing inside, so you rarely write the hash function yourself.

✅ Collisions happen when two keys land on the same box, and the hash table handles them for you.

🚀 What’s Next?

• Hash Functions
• Hash Table