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

take U forward

6 chapters7 takeaways12 key terms5 questions

Overview

This video introduces the fundamental concepts of hashing, a technique used for efficient data retrieval. It begins by illustrating the inefficiency of brute-force searching for element frequencies in an array, which leads to a time complexity of O(N*Q). The solution presented is to use an array as a hash table for pre-computation, allowing for O(1) average time complexity for lookups. The video then extends this concept to character hashing using ASCII values and explores the limitations of array-based hashing for large numbers. Finally, it introduces `map` and `unordered_map` from C++ STL as more robust solutions for hashing, explaining their time complexities and the concept of collisions, particularly in the context of the division method.

How was this?

Save this permanently with flashcards, quizzes, and AI chat

Chapters

When asked to find the frequency of elements in an array, a naive approach involves iterating through the entire array for each query.
This brute-force method results in a time complexity of O(N*Q), where N is the size of the array and Q is the number of queries.
For large arrays and numerous queries, this O(N*Q) complexity becomes computationally expensive, potentially taking hundreds of seconds for 10^10 operations.

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

Given an array `[1, 2, 1, 3]` and asked how many times `1` appears, the brute-force method iterates through the array, comparing each element to `1` and counting matches, taking O(N) time for this single query.

Hashing involves pre-storing and then quickly fetching data.
An array can be used as a hash table (frequency array) if the range of input numbers is known and manageable.
Pre-computation involves iterating through the input array once to populate the hash array, where the index represents the number and the value at that index represents its frequency.
After pre-computation, fetching the frequency of any number takes O(1) time by directly accessing the hash array at the number's index.

This technique drastically reduces query time from O(N) to O(1) after an initial O(N) pre-computation, making it highly efficient for problems with many frequency queries.

For an array with numbers up to 12, create a hash array of size 13. Iterate through the input array: for each number `x`, increment `hashArray[x]`. To find the count of `3`, simply look up `hashArray[3]`.

Characters can also be hashed using their ASCII values.
For lowercase English letters, an array of size 26 can be used, mapping 'a' to index 0, 'b' to index 1, and so on, by using the formula `character - 'a'`.
If the character set is larger (e.g., including uppercase, numbers, symbols), an array of size 256 can be used, directly using the ASCII value as the index.
This approach allows for O(1) average time complexity for character frequency lookups after O(N) pre-computation, where N is the string length.

Extends the hashing concept to non-numeric data like characters, enabling efficient frequency counting for strings.

To count the frequency of 'c' in the string 'abcabc', create a hash array of size 26. For each character, calculate its index (e.g., 'a' -> 0, 'b' -> 1, 'c' -> 2) and increment the count at that index. The frequency of 'c' is found at `hashArray['c' - 'a']`.

Array-based hashing has limitations: memory constraints prevent creating arrays for very large number ranges (e.g., 10^9 or 10^12).
Declaring large arrays globally might extend the limit to around 10^7, but it's still insufficient for extremely large inputs.
When direct array indexing is not feasible due to large keys, data structures like `map` (ordered) and `unordered_map` (unordered) are used.
These map structures store key-value pairs, where the key is the data element and the value is its associated information (e.g., frequency).

Introduces more flexible and scalable hashing solutions that overcome the memory limitations of fixed-size arrays.

If given numbers up to 10^12, creating an array of that size is impossible. Instead, a `map` can store only the numbers present in the input, using the number as the key and its frequency as the value.

A `map` in C++ stores key-value pairs in sorted order of keys.
Insertion and retrieval in a `map` have a time complexity of O(log N), where N is the number of elements in the map.
An `unordered_map` stores key-value pairs without any specific order.
On average, `unordered_map` provides O(1) time complexity for insertion and retrieval, making it generally faster than `map`.
The worst-case time complexity for `unordered_map` is O(N), which occurs due to internal hash collisions.

Understanding the trade-offs between `map` and `unordered_map` allows choosing the most efficient data structure for a given problem, prioritizing speed when possible.

When using `map` to store frequencies of `[1, 2, 1, 3]`, it might internally store them as `(1, 2), (2, 1), (3, 1)`. `unordered_map` might store them in a different, arbitrary order, but lookups for `1` are typically faster on average.

A hash collision occurs when two different keys map to the same hash index.
The division method is a common technique where a key is divided by the size of the hash table (or a chosen number `M`), and the remainder is used as the hash index (key % M).
When collisions occur (e.g., multiple numbers have the same remainder when divided by `M`), techniques like separate chaining (using linked lists) are employed to store multiple values at the same index.
While `unordered_map` handles collisions internally, understanding them is crucial for analyzing worst-case scenarios and potential performance degradation.

Explains the underlying mechanism that can lead to performance issues in hash tables and why `unordered_map` isn't always O(1).

Using the division method with `M=10`, both `28` and `38` would hash to index `8` (since `28 % 10 = 8` and `38 % 10 = 8`). This is a collision, requiring a mechanism like chaining to store both values at index `8`.

Key takeaways

1Hashing is a technique to achieve fast data lookups, often reducing time complexity from O(N) or O(N*Q) to O(1) on average.
2Arrays can serve as efficient hash tables (frequency arrays) when the range of keys is small and known.
3Character frequencies can be efficiently calculated using ASCII values and array-based hashing.
4For large key ranges where array indexing is not feasible, `map` and `unordered_map` provide dynamic hashing solutions.
5`unordered_map` offers average O(1) performance for insertions and lookups, making it the preferred choice for speed, but it has a worst-case O(N) complexity due to collisions.
6Collisions are inevitable in hashing and occur when different keys map to the same hash index, impacting performance in the worst case.
7The division method (key % M) is a fundamental technique for calculating hash indices and understanding collision handling.

Key terms

HashingHash TableFrequency ArrayTime ComplexityBrute ForcePre-computationASCII ValueCollisionDivision MethodMapUnordered MapSeparate Chaining

Test your understanding

1Why is a brute-force approach to finding element frequencies in an array inefficient for large datasets?
2How does using an array as a frequency map improve the time complexity for lookups compared to brute-force searching?
3Explain how ASCII values can be used to implement hashing for characters.
4What are the primary limitations of using arrays for hashing, and when should `map` or `unordered_map` be preferred?
5What is a hash collision, and how does it affect the performance of hash-based data structures like `unordered_map`?