Hashing | Notion

Introduction to Hashing

Hashing is a fundamental technique in data structures and algorithms (DSA) that optimizes data storage and retrieval. It involves pre-storing data (e.g., frequencies of elements) and fetching it efficiently to answer queries. This lecture, part of Striver’s A to Z DSA Course, introduces hashing through the problem of counting element frequencies in an array, using both brute force and optimized approaches. The solutions are implemented in Java, as requested.

Why Hashing is Important

Purpose: Hashing enables fast data access, reducing time complexity for operations like searching and counting.
Relevance: Essential for coding interviews, competitive programming, and applications like database indexing, caching, and frequency analysis.
Common Pitfall: Without hashing, problems requiring frequent queries (e.g., element counts) become computationally expensive due to repeated linear searches.

Problem Statement: Frequency Counting

Given an array of integers (e.g., [1, 2, 1, 3, 2]) and a set of queries (e.g., how many times does 1 appear? How many times does 3 appear?), determine the frequency of each queried number.

Brute Force Approach

The naive approach iterates through the array for each query to count occurrences.

Java Code for Brute Force

public class FrequencyCounter {
    public static int countFrequency(int number, int[] arr) {
        int counter = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == number) {
                counter++;
            }
        }
        return counter;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 2};
        int[] queries = {1, 4, 2, 3, 12};
        for (int query : queries) {
            System.out.println(countFrequency(query, arr));
        }
    }
}

How it Works: For each query, the function scans the entire array, incrementing a counter when the queried number is found.
Time Complexity: O(n) per query, so O(Q * n) for Q queries, where n is the array size.
Space Complexity: O(1), using only a counter variable.
Drawback: For large Q and n (e.g., both 10^5), the total operations could reach 10^10, taking ~100 seconds, which is impractical for real-time applications.
Example Output for array [1, 2, 1, 3, 2] and queries [1, 4, 2, 3, 12]:
```
2
0
2
1
0
```

Array Hashing