Hashing — Data Structure & Algrorithm

Imagine you have thousands of student records and you need to quickly find a particular student using their ID.

One simple approach would be to check the records one by one. But if there are thousands or millions of records, that can take a lot of time.

Hashing provides a way to store and retrieve data very quickly by using a special function called a hash function.

The basic idea is:

Key
 ↓
Hash Function
 ↓
Hash Value
 ↓
Storage Location

Instead of searching through every element, we use the key to calculate where the data should be stored.

What is Hashing?

Hashing is a technique of converting a key into a value that can be used to determine where the corresponding data should be stored.

For example, suppose we have student IDs:

We could use a simple hash function:

hash(key) = key % 10

For 101:

101 % 10 = 1

For 102:

102 % 10 = 2

So we could use these results as positions in a table.

Key → Hash Value

101 → 1
102 → 2
103 → 3
104 → 4

This is a very simplified example, but it demonstrates the basic idea behind hashing.

Hash Table

The data structure commonly used with hashing is called a hash table.

A hash table stores data using key-value pairs.

For example:

Key       Value
101       John
102       Jason
103       Alex
104       Michael

Instead of searching through every name, we can use the key to quickly determine where the value should be stored.

In Java, HashMap is a common implementation of a hash table.

import java.util.HashMap;

class Main {
    public static void main(String[] args) {

        HashMap<Integer, String> students = new HashMap<>();

        students.put(101, "John");
        students.put(102, "Jason");
        students.put(103, "Alex");

        System.out.println(students.get(102));
    }
}

Output:

Jason

We provide the key 102, and the HashMap finds the associated value.

Hash Function

A hash function takes a key and converts it into a hash value.

For example:

Key → Hash Function → Hash Value

Suppose our table has 10 positions and we use:

hash(key) = key % 10

Then:

101 % 10 = 1
102 % 10 = 2
103 % 10 = 3

The hash value helps determine where the data should be stored.

A real hash function can be much more sophisticated than this simple example.

Why Is Hashing Fast?

Suppose you have 1 million student records.

With a simple linear search, you may need to check many records before finding the one you're looking for.

With hashing, the key can be processed by a hash function to determine where the corresponding value should be located.

This means we can often perform insertion, deletion, and lookup in approximately:

O(1)

on average.

This is why hashing is extremely useful in DSA.

Collision

Here's an important problem with hashing.

Two different keys can sometimes produce the same hash value.

This is called a collision.

For example, using:

hash(key) = key % 10

we get:

101 % 10 = 1
111 % 10 = 1

Both keys produce the same hash value:

101 → 1
111 → 1

So both keys want to use the same location.

That's a collision.

Handling Collisions

Hash tables need techniques to handle collisions.

Two common approaches are:

Chaining
Open Addressing

Chaining

With chaining, multiple elements that produce the same hash value are stored together, commonly using a linked structure.

For example:

Index 1 → 101 → 111 → 121

Here, all three keys produced the same hash index.

The hash table stores them together at that location.

Open Addressing

With open addressing, if the calculated position is already occupied, the algorithm searches for another available position according to a defined probing strategy.

Common probing techniques include:

Linear Probing
Quadratic Probing
Double Hashing

We'll explore these techniques in more detail when studying hash tables.

Hashing in Java

Java provides several classes that use hashing internally.

The most important ones you'll encounter are:

HashMap
HashSet
Hashtable

HashMap stores key-value pairs.

HashMap<Integer, String> students = new HashMap<>();

HashSet stores unique values.

HashSet<Integer> numbers = new HashSet<>();

Both rely on hashing to provide efficient operations.

HashMap Example

Suppose John, Jason, and Alex have different student IDs.

import java.util.HashMap;

class Main {
    public static void main(String[] args) {

        HashMap<Integer, String> students = new HashMap<>();

        students.put(101, "John");
        students.put(102, "Jason");
        students.put(103, "Alex");

        System.out.println(students.get(101));
        System.out.println(students.get(103));
    }
}

Output:

John
Alex

We don't need to search through every student.

We simply provide the key.

Common HashMap Operations

Some important HashMap operations are:

put()
get()
remove()
containsKey()
containsValue()

For example:

students.put(104, "Michael");

adds a new key-value pair.

students.get(104);

retrieves the value.

students.remove(104);

removes the entry.

And:

students.containsKey(104);

checks whether the key exists.

HashSet and Hashing

Hashing isn't only used for key-value pairs.

A HashSet uses hashing to store unique elements.

For example:

import java.util.HashSet;

class Main {
    public static void main(String[] args) {

        HashSet<Integer> numbers = new HashSet<>();

        numbers.add(10);
        numbers.add(20);
        numbers.add(10);
        numbers.add(30);

        System.out.println(numbers);
    }
}

The value 10 was added twice, but a HashSet keeps only one copy.

So the set contains:

10
20
30

Hashing allows the set to efficiently determine whether an element already exists.

Hashing for Frequency Counting

One of the most common applications of hashing in DSA is counting frequencies.

Suppose we have:

apple, banana, apple, orange, banana, apple

We want to know how many times each word appears.

A HashMap is perfect for this.

import java.util.HashMap;

class Main {
    public static void main(String[] args) {

        String[] fruits = {
            "apple",
            "banana",
            "apple",
            "orange",
            "banana",
            "apple"
        };

        HashMap<String, Integer> frequency = new HashMap<>();

        for (String fruit : fruits) {
            frequency.put(
                fruit,
                frequency.getOrDefault(fruit, 0) + 1
            );
        }

        System.out.println(frequency);
    }
}

The result will represent:

apple  → 3
banana → 2
orange → 1

This technique is extremely common in DSA problems.

Finding Duplicates

Hashing can also help us find duplicate values.

Suppose:

10, 20, 30, 20, 40

We can use a HashSet:

import java.util.HashSet;

class Main {
    public static void main(String[] args) {

        int[] numbers = {10, 20, 30, 20, 40};

        HashSet<Integer> seen = new HashSet<>();

        for (int number : numbers) {

            if (seen.contains(number)) {
                System.out.println(
                    "Duplicate: " + number
                );
            }

            seen.add(number);
        }
    }
}

Output:

Duplicate: 20

The set allows us to quickly check whether we've already encountered a number.

Hashing and Strings

Hashing is also heavily used with strings.

For example, suppose we want to check whether two strings contain the same characters.

Hashing can help us count the frequency of each character.

For:

"listen"

we could create a frequency representation:

l → 1
i → 1
s → 1
t → 1
e → 1
n → 1

Then we can compare that with another string.

This type of technique is commonly used in anagram problems.

Average and Worst-Case Complexity

Hashing is generally very efficient.

For a well-designed hash table, common operations such as:

Search
Insert
Delete

are typically:

O(1)

on average.

However, collisions can cause multiple elements to end up in the same location.

In a poor or highly-collided situation, operations can become slower.

So the expected average complexity is generally:

Search → O(1)
Insert → O(1)
Delete → O(1)

while the worst-case behavior can be:

O(n)

depending on the implementation and collision behavior.

Real-Life Example

Imagine a hotel with 1,000 rooms.

Instead of checking every room to find John, the hotel gives each guest a room number.

If John's room number is 507, you can directly go to room 507.

The room number acts like a key, and the process of converting that key into a storage location is similar to what a hash function does.

Of course, real hash tables are more sophisticated, but the idea is similar:

Key
 ↓
Hash Function
 ↓
Location
 ↓
Data

Where Is Hashing Used?

Hashing appears throughout software development and DSA.

Some common applications include:

Fast searching
Duplicate detection
Frequency counting
Caching
Database indexing
Symbol tables
Password storage systems
Dictionaries
Sets
Lookup tables

Many DSA problems that seem difficult become much simpler once you realize that you can store previously seen information in a hash table.

The Main Idea

Hashing is a technique that uses a hash function to map a key to a storage location, allowing data to be inserted, searched, and removed efficiently.

The basic flow is:

Key
 ↓
Hash Function
 ↓
Hash Value
 ↓
Index / Bucket
 ↓
Stored Data

The most important concepts to remember are:

Hash Function
Hash Table
Collision
Chaining
Open Addressing

And in practical Java programming, you'll frequently work with:

HashMap → Key-value pairs
HashSet → Unique values

Hashing allows us to quickly find, insert, and remove data by using a key to determine where that data should be stored.

This makes hashing one of the most useful techniques in DSA, especially for problems involving fast lookups, duplicates, frequencies, and previously seen values.