What are Bloom Filters? - Hashing

Bloom Filters are data structures that efficiently answer queries when we do not have enough "search key" space to handle all possible questions. In this case, the "search key" is hashed, marked, and then used later to check if it was searched earlier.

Bloom Filters use hashing as an immutable function result, and marking the respective positions in the data structure guarantees that the subsequent search for the exact string will return true.

This data structure has an error rate when returning 'true', and we look into how the number of hash functions affects its performance. In practice, Bloom Filters can be used to check for membership and to avoid 'One Hit Wonders'.

We talk about what bloom filters are, how we use them, and where can these filters be applied.

An example would be TinyURL, which can check if a URL has been previously generated using a bloom filter and regenerate it if the answer is positive.

Bloom Filter: https://en.wikipedia.org/wiki/Bloom_f...
Code: https://github.com/gkcs/Competitive-P...

00:00 Usecase - Avoid one-hit wonders
06:07 Mechanism
10:20 Reset
11:00 Guarantees
12:35 Multi-Layer Bloom Filters
14:34 Problems
20:35 Probability

References:
Hashing: https://www.hackerearth.com/practice/...
FaceBook Talk:   / 432864835468  
One Hit Wonder: https://en.wikipedia.org/wiki/One-hit...
Cache: https://en.wikipedia.org/wiki/Cache_(...)
LRU: https://en.wikipedia.org/wiki/Cache_r...)