Ugenz Academy/Tutorial

Hashing

12 min read2,210 words

Reading progress

Keep learning

Hashing

Hashing is a technique used to store and retrieve data very quickly using a special function called a hash function.

The main idea is:

Convert a key into an index, then use that index to store or find the data.

Hashing is extremely important in DSA because it can often make searching from O(n) to approximately O(1).

1. Why Do We Need Hashing?

Suppose we have:

[10, 25, 35, 42, 56, 78]

If we want to find 56 using a normal array, we may need to check:

10 → 25 → 35 → 42 → 56

This is linear search.

Complexity

O(n)

But what if we could directly calculate where 56 should be?

That's the idea behind hashing.

Key ↓ Hash Function ↓ Index ↓ Data

Then we can potentially find the value in:

O(1)

2. Real-Life Example

Imagine a college has student IDs:

101 102 103 104 ...

Instead of searching through every student's record, we could use the ID to determine where their information is stored.

For example:

Student ID → Hash Function → Storage Location

So:

101 → 1 102 → 2 103 → 3

Then finding student 103 is very fast.

3. Hash Function

A hash function converts a key into an index.

A simple example:

hash(key) = key % table_size

Suppose table size is 10.

For:

key = 27

we calculate:

27 % 10 = 7

So:

27 → index 7

Another:

43 % 10 = 3

Therefore:

43 → index 3

4. Hash Table

A hash table is a data structure that stores data using hash values.

Suppose:

Table size = 10

We insert:

27 43 15

Using:

hash(key) = key % 10

we get:

27 % 10 = 7 43 % 10 = 3 15 % 10 = 5

The table looks conceptually like:

Index Value ---------------- 0 - 1 - 2 - 3 43 4 - 5 15 6 - 7 27 8 - 9 -

So to find 43:

43 % 10 = 3

Go directly to index 3.

5. Hashing vs Array Search

Suppose:

[15, 27, 43, 51, 72]

Array

To search for 72:

15 → 27 → 43 → 51 → 72

Worst case:

O(n)

Hash Table

Calculate:

72 % table_size

Then go to the calculated location.

Average case:

O(1)

That's the major advantage of hashing.

6. Collision

There's an important problem.

What if two keys produce the same index?

This is called a:

Collision

For example, table size = 10.

27 % 10 = 7 37 % 10 = 7 47 % 10 = 7

All three want index 7.

27 ─┐ 37 ─┼──→ index 7 47 ─┘

We need a method to handle this.

7. Collision Handling

Two major methods are:

1. Separate Chaining

2. Open Addressing

Let's understand both.

8. Separate Chaining

In separate chaining, each hash table position stores multiple values, usually using a linked list or another container.

For:

27 37 47

all hash to index 7.

We can store:

Index 7: 7 → [27] → [37] → [47]

Conceptually:

0 1 2 3 4 5 6 7 → 27 → 37 → 47 8 9

This is called chaining because values are chained together.

9. Open Addressing

Another approach is open addressing.

Instead of storing multiple values at the same index, we search for another empty position.

For example:

27 → index 7 37 → index 7 ❌

Index 7 is occupied.

Try another position:

index 8

So:

7 → 27 8 → 37

Then perhaps:

47 → 7 ❌ → 8 ❌ → 9 ✅

Result:

7 → 27 8 → 37 9 → 47

10. Linear Probing

One common open-addressing technique is linear probing.

If the desired index is occupied:

index index + 1 index + 2 index + 3 ...

are checked.

Example:

27 → 7 37 → 7 occupied ↓ 8

So:

7 → 27 8 → 37

11. Quadratic Probing

Instead of checking:

+1 +2 +3 +4

we use squares:

+1² +2² +3² +4²

So:

h(k) h(k) + 1² h(k) + 2² h(k) + 3² ...

This helps reduce some clustering problems found in linear probing.

12. Double Hashing

Another method is double hashing.

We use two hash functions.

index = h1(key) + i × h2(key)

The second hash function determines the jump size.

This can reduce clustering further.

13. Hash Table in C++

In modern C++, we usually don't implement hashing from scratch.

The STL provides:

unordered_map unordered_set

These are hash-based containers.

14. unordered_set

unordered_set stores unique values.

Example:

#include <iostream> #include <unordered_set> using namespace std; int main() { unordered_set<int> s; s.insert(10); s.insert(20); s.insert(30); if (s.find(20) != s.end()) { cout << "Found"; } return 0; }

Output:

Found

15. Important unordered_set Operations

unordered_set<int> s;

Insert

s.insert(10);

Search

s.find(10);

Check existence

if (s.count(10)) { cout << "Found"; }

Delete

s.erase(10);

Size

s.size();

Empty

s.empty();

16. unordered_map

unordered_map stores:

Key → Value

For example:

Student ID → Student Name
101 → Uday 102 → Ram 103 → Sita

C++:

#include <iostream> #include <unordered_map> using namespace std; int main() { unordered_map<int, string> students; students[101] = "Uday"; students[102] = "Ram"; students[103] = "Sita"; cout << students[101]; return 0; }

Output:

Uday

17. unordered_map Operations

Insert

students[101] = "Uday";

Access

cout << students[101];

Search

if (students.find(101) != students.end()) { cout << "Found"; }

Delete

students.erase(101);

Size

students.size();

18. Frequency Counting

This is one of the most important applications of hashing.

Suppose:

[1, 2, 2, 3, 1, 2, 4]

We want to count how many times each number appears.

Use:

unordered_map<int, int> freq;

Then:

for (int x : arr) { freq[x]++; }

Complete example:

#include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { vector<int> arr = {1, 2, 2, 3, 1, 2, 4}; unordered_map<int, int> freq; for (int x : arr) { freq[x]++; } for (auto p : freq) { cout << p.first << " -> " << p.second << endl; } return 0; }

Conceptually:

1 → 2 2 → 3 3 → 1 4 → 1

19. Character Frequency

Hashing is also useful with strings.

Suppose:

"banana"

We want:

b → 1 a → 3 n → 2

C++:

unordered_map<char, int> freq; for (char ch : s) { freq[ch]++; }

This is extremely common in DSA problems.

20. Find Duplicate Elements

Suppose:

[1, 2, 3, 2, 4, 1]

We can use a hash set.

unordered_set<int> seen; for (int x : arr) { if (seen.count(x)) { cout << "Duplicate: " << x << endl; } seen.insert(x); }

The set remembers which values we've already seen.

21. Two Sum Problem

This is one of the most famous hashing problems.

Given:

[2, 7, 11, 15]

and:

target = 9

We need two numbers whose sum is 9.

Instead of checking every pair, use a hash map.

For each number:

needed = target - current

For 2:

needed = 9 - 2 = 7

Is 7 already seen?

No.

Store 2.

Then encounter 7:

needed = 9 - 7 = 2

2 is already in the hash table.

Therefore:

2 + 7 = 9

C++ example

#include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { vector<int> arr = {2, 7, 11, 15}; int target = 9; unordered_map<int, int> mp; for (int i = 0; i < arr.size(); i++) { int needed = target - arr[i]; if (mp.find(needed) != mp.end()) { cout << mp[needed] << " " << i; return 0; } mp[arr[i]] = i; } return 0; }

The important idea is:

Current value ↓ Calculate what is needed ↓ Search hash table ↓ Found? ↓ Yes → Answer No → Store current value

Average complexity:

Time = O(n) Space = O(n)

A brute-force solution would usually be:

O(n²)

22. Hashing with Strings

Hashing isn't limited to integers.

We can hash:

int string char pair custom objects

For example:

unordered_set<string> names; names.insert("Uday"); names.insert("Ram"); names.insert("Sita");

Search:

if (names.count("Uday")) { cout << "Found"; }

23. map vs unordered_map

This is very important in C++.

map

Usually implemented using a balanced tree.

map<int, string> mp;

Complexity:

Search → O(log n) Insert → O(log n) Delete → O(log n)

Keys are maintained in sorted order.

unordered_map

Hash table.

unordered_map<int, string> mp;

Average:

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

But elements are not stored in sorted order.

24. set vs unordered_set

Similarly:

ContainerStructureAverage SearchSorted?
setTreeO(log n)Yes
unordered_setHash tableO(1)No

And:

ContainerStores
setUnique values
unordered_setUnique values
mapKey → Value
unordered_mapKey → Value

25. Hashing Complexity

For unordered_map and unordered_set:

OperationAverageWorst Case
SearchO(1)O(n)
InsertO(1)O(n)
DeleteO(1)O(n)

Why can the worst case become O(n)?

Because many keys can collide and end up in the same bucket.

Good hash distribution keeps operations close to O(1) on average.

26. Load Factor

A hash table has a concept called load factor.

Roughly:

Load Factor = Number of stored elements / Number of buckets

For example:

Elements = 7 Buckets = 10

Then:

Load Factor = 7 / 10 = 0.7

If a hash table becomes too full, collisions can increase.

Hash tables can therefore rehash, meaning they create more buckets and redistribute the elements.

You generally don't need to implement this manually when using unordered_map or unordered_set.

27. Hashing vs Hash Table

Don't confuse these terms.

Hashing

The technique of converting data into a hash value/index.

Hash Function

The function that performs the conversion.

key → hash function → hash/index

Hash Table

The data structure that uses hashing to store data.

Hashing ↓ Hash Function ↓ Hash Table

28. Common DSA Problems Using Hashing

Hashing appears everywhere.

Basic

  • Frequency counting
  • Find duplicates
  • Remove duplicates
  • Check existence
  • Count distinct elements

Intermediate

  • Two Sum
  • First non-repeating character
  • Anagram checking
  • Longest consecutive sequence
  • Subarray with given sum
  • Count subarrays with sum K

Advanced

  • Longest substring without repeating characters
  • Group anagrams
  • Frequency-based problems
  • Prefix sum + hashing
  • Sliding window + hashing

🧠 The Core Hashing Pattern

When you see a problem asking:

"Have I seen this before?"

Think:

unordered_set

When you see:

"How many times does this occur?"

Think:

unordered_map

When you see:

"I need to quickly find a corresponding value."

Think:

unordered_map

For example:

Have I seen 10? ↓ unordered_set How many times did 10 occur? ↓ unordered_map Where did I see 10? ↓ unordered_map<value, index>

🔥 Final Summary

HASHING | ┌────────┴────────┐ ↓ ↓ Hash Function Hash Table | | Key → Index Store / Search | ┌───────────┴───────────┐ ↓ ↓ unordered_set unordered_map ↓ ↓ Unique values Key → Value

Most important points:

  1. Hashing provides fast data lookup.
  2. A hash function converts a key into a hash/index.
  3. Two keys can produce the same index → collision.
  4. Collision can be handled using chaining or open addressing.
  5. C++ provides unordered_set and unordered_map.
  6. Average search/insert/delete is O(1).
  7. Hashing is extremely useful for frequency counting, duplicates, Two Sum, anagrams, and lookup problems.
  8. map/set are generally O(log n) and sorted.
  9. unordered_map/unordered_set are generally O(1) average and not sorted.

Your DSA roadmap now:

Introduction ↓ Complexity Analysis ↓ Arrays ↓ Strings ↓ Linked List ↓ Stack ↓ Queue ↓ Deque ↓ Recursion ↓ Backtracking ↓ ⭐ Hashing ← YOU ARE HERE ↓ Trees ↓ Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie ↓ Graphs ↓ ...

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy