Hashing | Maps | Time Complexity | Collisions | Division Rule of Hashing | Strivers A2Z DSA Course

take U forward

5 chapters7 takeaways11 key terms5 questions

Overview

This video introduces hashing as a technique to efficiently store and retrieve data, significantly improving upon brute-force methods. It covers basic hashing concepts, including frequency counting for numbers and characters using arrays. The limitations of array-based hashing for large numbers are discussed, leading to an introduction of `map` and `unordered_map` data structures in C++ STL. The video also touches upon the division method for hashing and the concept of collisions, explaining why `unordered_map` offers better average-case performance.

How was this?

Save this permanently with flashcards, quizzes, and AI chat

Chapters

Many interview problems require efficient data retrieval, and brute-force methods (like linear search) can be too slow.
A common problem is counting the frequency of elements in an array.
The brute-force approach involves iterating through the array for each query, resulting in O(N) time complexity per query.
For Q queries and an array of size N, the total time complexity becomes O(Q*N), which is inefficient for large datasets.

Understanding the inefficiency of brute-force methods highlights the need for more optimized data structures and algorithms like hashing.

Counting how many times the number '1' appears in an array by iterating through each element and incrementing a counter if a match is found.

Hashing allows pre-storing and fast fetching of data.
For numbers within a known, limited range, an auxiliary array (hash array or frequency array) can be used.
The value of the number itself serves as the index in the hash array.
Pre-computation involves iterating through the input array and incrementing the count at the corresponding index in the hash array.
Fetching the frequency of a number then becomes an O(1) operation by directly accessing the hash array.

This method drastically reduces query time from O(N) to O(1) for frequency counting within a manageable range, making it highly efficient.

Given an array with numbers up to 12, create a hash array of size 13. For each number in the input array, increment the count at that number's index in the hash array (e.g., if '3' appears, increment `hash_array[3]`).

Array-based hashing is impractical when numbers are very large (e.g., 10^9 or 10^12) due to memory constraints (max array size is around 10^6 to 10^7).
Character hashing is feasible using arrays because the number of possible characters (ASCII) is limited (256).
Lowercase characters can be mapped to indices 0-25 using the formula `character - 'a'`.
For any character, its ASCII value can be used directly as an index in a 256-sized array.

This section shows how hashing adapts to different data types, but also reveals its limitations with large numerical ranges, necessitating other approaches.

To count character frequencies in a string, create an array of size 26. For each character `c`, increment `hash_array[c - 'a']`.

When array indices become too large or keys are not simple integers/characters, `map` and `unordered_map` (hash maps) are used.
A `map` stores key-value pairs and keeps keys sorted, offering O(log N) time complexity for insertion and retrieval.
An `unordered_map` also stores key-value pairs but does not maintain order, providing an average time complexity of O(1) for insertion and retrieval.
The worst-case time complexity for `unordered_map` is O(N), which occurs due to internal collisions.

These data structures overcome the limitations of array-based hashing, allowing efficient handling of large or complex keys, with `unordered_map` being preferred for its average O(1) performance.

Using `std::map<int, int> frequency_map;` to store the frequency of numbers, where the number is the key and its count is the value. `frequency_map[number]++;` increments the count.

Hashing aims to map keys to array indices, but multiple keys can sometimes map to the same index, causing a collision.
The division method is a common technique where a key is modulated by the hash table size (e.g., `key % table_size`) to determine its index.
Collisions are handled using techniques like separate chaining (using linked lists at each index) or open addressing.
The worst-case scenario for hash maps occurs when all keys hash to the same index, degrading performance to O(N).

Understanding collisions is crucial for comprehending why hash map performance can degrade in specific scenarios and why `unordered_map`'s average O(1) is so valuable.

Using the division method with a table size of 10, both the number 28 and 38 would hash to index 8 (28 % 10 = 8, 38 % 10 = 8), resulting in a collision at that index.

Key takeaways

1Hashing is a technique that maps keys to values for efficient data lookup, often achieving O(1) average time complexity.
2Array-based hashing is efficient for data within a known, limited range but fails for very large numbers due to memory limits.
3Character hashing is effectively done using arrays by mapping characters to their ASCII values or relative positions (e.g., `char - 'a'`).
4`std::map` (or Java's `TreeMap`) provides ordered key-value storage with O(log N) complexity, suitable when order matters or for complex keys.
5`std::unordered_map` (or Java's `HashMap`) offers average O(1) complexity for key-value operations by using hashing internally, making it ideal for most frequency counting and lookup tasks.
6Collisions are inevitable in hashing and can degrade `unordered_map` performance to O(N) in the worst case, though this is rare.
7The choice between `map` and `unordered_map` depends on whether sorted order is required or if average O(1) performance is prioritized.

Key terms

HashingFrequency CountingTime ComplexityBig O NotationHash ArrayASCII ValueMapUnordered MapCollisionDivision MethodSeparate Chaining

Test your understanding

1What is the primary advantage of using hashing over a brute-force approach for frequency counting?
2Why is array-based hashing not suitable for numbers as large as 10^9?
3How can you efficiently hash characters using an array, and what is the formula for lowercase English letters?
4What is the difference in time complexity and ordering between `std::map` and `std::unordered_map`?
5Explain what a hash collision is and how it can impact the performance of an `unordered_map`.