Module 17: Hashing

Learning Objectives

By the end of this module, you will be able to:

• Understand the concept of hashing.
• Learn how hash tables work.
• Understand hash functions and indexing.
• Handle collisions using chaining and open addressing.
• Implement frequency counters using hashing.
• Detect duplicate elements efficiently.
• Analyze the time complexity of hashing operations.

Introduction

Hashing is one of the fastest techniques for storing and retrieving data.

Instead of searching every element one by one, hashing uses a hash function to calculate the storage location directly.

Hashing is widely used in:

• Databases
• Password Storage
• Search Engines
• Caching
• Dictionaries
• Compilers
• Symbol Tables
• Blockchain
• Network Routing

What is Hashing?

Hashing is the process of converting a key into an index using a hash function.

Instead of storing data sequentially, data is stored at the calculated index.

Example

textCopy
1Key = 25
2
3Hash Function
4
5index = key % 10
6
725 % 10 = 5
8
9Store value at index 5

Visualization

textCopy
1Index   Value
2
30
4
51
6
72
8
93
10
114
12
135      25
14
156
16
177
18
198
20
219

Searching for 25 takes constant time because its location is known.

What is a Hash Table?

A Hash Table is a data structure that stores key-value pairs using a hash function.

Structure

textCopy
1Index
2
30
4
51
6
72
8
93
10
114
12
135 → 25
14
156
16
177
18
198
20
219

Hash Table Components

• Keys
• Values
• Hash Function
• Buckets

Hash Function

A Hash Function converts a key into an array index.

Simple Formula

textCopy
1index = key % tableSize

Example

Table Size = 10

textCopy
115 → 5
2
335 → 5
4
555 → 5

All three keys map to the same index.

This situation is called a collision.

Basic Hash Table Implementation

cCopy
1#include <stdio.h>
2
3#define SIZE 10
4
5int hashTable[SIZE];
6
7void initialize()
8{
9    for(int i = 0; i < SIZE; i++)
10        hashTable[i] = -1;
11}
12
13void insert(int key)
14{
15    int index = key % SIZE;
16
17    hashTable[index] = key;
18}
19
20void display()
21{
22    for(int i = 0; i < SIZE; i++)
23    {
24        printf("%d : %d\n", i, hashTable[i]);
25    }
26}
27
28int main()
29{
30    initialize();
31
32    insert(15);
33    insert(22);
34    insert(37);
35
36    display();
37
38    return 0;
39}

Output

textCopy
10 : -1
21 : -1
32 : 22
43 : -1
54 : -1
65 : -1
76 : -1
87 : 37
98 : -1
109 : -1

Time Complexity

Average-case performance is constant because a good hash function distributes keys evenly.

Collision Handling

A collision occurs when two or more keys produce the same hash index.

Example

textCopy
1Table Size = 10
2
315 % 10 = 5
4
525 % 10 = 5
6
735 % 10 = 5

All keys map to index 5.

There are two common techniques to resolve collisions:

1. Chaining
2. Open Addressing

Chaining

In chaining, each table index stores a linked list.

If multiple keys map to the same index, they are added to that list.

Example

textCopy
1Index
2
35
4
5↓
6
715 → 25 → 35 → NULL

Node Structure

cCopy
1struct Node
2{
3    int key;
4    struct Node *next;
5};

Insertion

cCopy
1#include <stdlib.h>
2
3struct Node* insert(struct Node *head, int key)
4{
5    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
6
7    newNode->key = key;
8    newNode->next = head;
9
10    return newNode;
11}

Advantages

• Easy to implement
• Unlimited number of collisions
• Dynamic memory allocation

Disadvantages

• Extra memory for pointers
• Performance decreases if chains become long

Average Complexity

textCopy
1Insert : O(1)
2
3Search : O(1)
4
5Worst Case : O(n)

Open Addressing

Instead of using linked lists, open addressing stores all elements inside the hash table.

When a collision occurs, another empty location is searched.

Methods

• Linear Probing
• Quadratic Probing
• Double Hashing

Linear Probing

Formula

textCopy
1index = (hash + i) % tableSize

Example

textCopy
1Insert 15
2
315 % 10 = 5
4
5Store at index 5

Insert 25

textCopy
125 % 10 = 5
2
3Collision
4
5Check index 6
6
7Store at index 6

Visualization

textCopy
1Index
2
35 → 15
4
56 → 25
6
77 → 35

Simple Program

cCopy
1#include <stdio.h>
2
3#define SIZE 10
4
5int hashTable[SIZE];
6
7void initialize()
8{
9    for(int i = 0; i < SIZE; i++)
10        hashTable[i] = -1;
11}
12
13void insert(int key)
14{
15    int index = key % SIZE;
16
17    while(hashTable[index] != -1)
18    {
19        index = (index + 1) % SIZE;
20    }
21
22    hashTable[index] = key;
23}

Advantages

• No extra memory
• Cache friendly

Disadvantages

• Clustering
• Performance decreases as the table fills

Chaining vs Open Addressing

Load Factor

The Load Factor indicates how full a hash table is.

Formula

textCopy
1Load Factor = Number of Elements / Table Size

Example

textCopy
1Elements = 8
2
3Table Size = 10
4
5Load Factor = 0.8

A high load factor increases collisions and reduces performance.

Practice Project 1: Frequency Counter

Problem

Count the frequency of each integer.

Input

textCopy
11 2 2 3 3 3 4

Output

textCopy
11 → 1
2
32 → 2
4
53 → 3
6
74 → 1

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[] = {1,2,2,3,3,3,4};
6    int frequency[100] = {0};
7
8    int size = sizeof(arr) / sizeof(arr[0]);
9
10    for(int i = 0; i < size; i++)
11    {
12        frequency[arr[i]]++;
13    }
14
15    for(int i = 0; i < 100; i++)
16    {
17        if(frequency[i] > 0)
18        {
19            printf("%d -> %d\n", i, frequency[i]);
20        }
21    }
22
23    return 0;
24}

Time Complexity

textCopy
1O(n)

Practice Project 2: Duplicate Detection

Problem

Find duplicate numbers in an array.

Input

textCopy
110 20 30 20 40 10

Output

textCopy
110
2
320

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int arr[] = {10,20,30,20,40,10};
6    int visited[100] = {0};
7
8    int size = sizeof(arr) / sizeof(arr[0]);
9
10    for(int i = 0; i < size; i++)
11    {
12        if(visited[arr[i]] == 0)
13        {
14            visited[arr[i]] = 1;
15        }
16        else
17        {
18            printf("%d\n", arr[i]);
19        }
20    }
21
22    return 0;
23}

Time Complexity

textCopy
1O(n)

Real-World Applications of Hashing

Password Storage

Passwords are stored as hashes instead of plain text.

Example

textCopy
1Password
2
3myPassword123
4
5↓
6
7Hash Function
8
9↓
10
118f4d0e7b9a...

Dictionary

Word lookup in a dictionary can be implemented using hash tables.

Example

textCopy
1apple
2
3↓
4
5Hash
6
7↓
8
9Index
10
11↓
12
13Meaning

Database Indexing

Databases use hashing for fast record retrieval.

Instead of scanning every row, records are accessed directly through hash indexes.

Caching

Web browsers and operating systems use hashing to quickly retrieve frequently accessed data.

Common Interview Questions

1. What is hashing?
2. What is a hash function?
3. What is a collision?
4. Explain chaining.
5. Explain open addressing.
6. Difference between chaining and linear probing.
7. What is load factor?
8. Design a hash table.
9. Count frequencies using hashing.
10. Find duplicates using hashing.

Common Mistakes to Avoid

• Choosing a poor hash function that causes excessive collisions.
• Ignoring collision handling strategies.
• Using a very small hash table, resulting in a high load factor.
• Forgetting to initialize the hash table before insertion.
• Not considering table resizing (rehashing) when the load factor becomes too high.
• Assuming hashing always provides O(1) performance, even with many collisions.

Best Practices

• Choose a hash function that distributes keys uniformly.
• Keep the load factor low (typically below 0.75) to maintain good performance.
• Use chaining when frequent insertions and deletions are expected.
• Use open addressing when memory efficiency and cache locality are priorities.
• Rehash the table when it becomes too full to reduce collisions.
• Analyze both average-case and worst-case time complexity for hash table operations.

Module Summary

In this module, you learned:

• What hashing is and how hash tables store data efficiently.
• How hash functions map keys to array indexes.
• Why collisions occur and how to resolve them using chaining and open addressing.
• The concept of the load factor and its impact on performance.
• How to build practical applications such as frequency counters and duplicate detectors using hashing.
• Real-world uses of hashing in databases, password storage, dictionaries, and caching.

After completing this module, you'll be ready to learn Trees, where you'll explore binary trees, binary search trees (BST), tree traversals, heaps, AVL trees, and efficient hierarchical data structures used in searching and optimization.