Frequency Counter Pattern Using Hash Map in DSA C

Mental Model

Count how many times each item appears by using a map that remembers counts.

Analogy: Imagine you have a basket of fruits and you write down how many apples, bananas, and oranges you have on a piece of paper.

Basket: [apple, banana, apple, orange, banana]
Hash Map:
apple -> 2
banana -> 2
orange -> 1

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3, 2]

Goal: Count how many times each number appears in the array.

Step 1: Add 2 to map with count 1

{2:1}

Why: First time seeing 2, start count at 1

Step 2: Add 3 to map with count 1

{2:1, 3:1}

Why: First time seeing 3, start count at 1

Step 3: Increase count of 2 to 2

{2:2, 3:1}

Why: 2 appeared again, increase count

Step 4: Add 4 to map with count 1

{2:2, 3:1, 4:1}

Why: First time seeing 4, start count at 1

Step 5: Increase count of 3 to 2

{2:2, 3:2, 4:1}

Why: 3 appeared again, increase count

Step 6: Increase count of 2 to 3

{2:3, 3:2, 4:1}

Why: 2 appeared again, increase count

Result:

Final map: {2:3, 3:2, 4:1}

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node for linked list in each bucket
typedef struct Node {
    int key;
    int count;
    struct Node* next;
} Node;

// Simple hash map with chaining
#define SIZE 10

Node* hashMap[SIZE] = {NULL};

// Hash function for integers
int hash(int key) {
    return (key % SIZE + SIZE) % SIZE;
}

// Find node with key in bucket
Node* find(Node* head, int key) {
    while (head != NULL) {
        if (head->key == key) {
            return head;
        }
        head = head->next;
    }
    return NULL;
}

// Insert or update count for key
void insert(int key) {
    int index = hash(key);
    Node* node = find(hashMap[index], key);
    if (node != NULL) {
        node->count++;
    } else {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->key = key;
        newNode->count = 1;
        newNode->next = hashMap[index];
        hashMap[index] = newNode;
    }
}

// Print all keys and counts
void printFrequency() {
    for (int i = 0; i < SIZE; i++) {
        Node* curr = hashMap[i];
        while (curr != NULL) {
            printf("%d: %d\n", curr->key, curr->count);
            curr = curr->next;
        }
    }
}

int main() {
    int arr[] = {2, 3, 2, 4, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < n; i++) {
        insert(arr[i]);
    }

    printFrequency();
    return 0;
}

Node* node = find(hashMap[index], key);

Check if key already exists in the map

if (node != NULL) { node->count++; } else {

If found, increase count; else create new node with count 1

newNode->next = hashMap[index]; hashMap[index] = newNode;

Insert new node at head of bucket list

for (int i = 0; i < n; i++) { insert(arr[i]); }

Process each array element to build frequency map

Output

2: 3

3: 2

4: 1

Complexity Analysis

Time: O(n) because we process each element once and hash map operations are average O(1)

Space: O(n) because in worst case all elements are unique and stored in map

vs Alternative: Compared to nested loops counting frequencies (O(n^2)), hash map is much faster

Edge Cases

empty array

No insertions happen, map stays empty, no output

DSA C

for (int i = 0; i < n; i++) {
        insert(arr[i]);
    }

all elements same

One key with count equal to array length

DSA C

if (node != NULL) {
        node->count++;
    } else {

elements with negative numbers

Hash function handles negative keys correctly using modulo adjustment for positive indices

DSA C

int hash(int key) {
    return (key % SIZE + SIZE) % SIZE;
}

When to Use This Pattern

When you need to count how many times items appear quickly, use a frequency counter with a hash map to store counts efficiently.

Common Mistakes

Mistake: Not checking if key already exists before inserting, causing duplicates.
Fix: Always search for key first; if found, increase count instead of inserting new node.

Mistake: Using a poor hash function causing many collisions.
Fix: Use a simple modulo hash for integers and handle collisions with chaining.

Summary

Counts how many times each item appears using a hash map.

Use when you need fast frequency counts of items in a collection.

The key is to check if the item exists and update count or add new entry.