Bloom Filter
A bloom filter is a way to maintain a set of elements in a space-efficient way with a low probability of false positives (but no false negatives). By accepting a low probability of inaccuracy, you save quite a lot of space in memory!
Hashing has following uses:
1. In
Hash Tables
2. To build caches
3. In cryptography
4. In Rabin-Karp algorithm to search substrings
5. In computer graphics etc.
Examples
How Dropbox Knows When You’re Sharing Copyrighted Stuff (Without Actually Looking At Your Stuff)
With a properly implemented hash function, running the same exact file through the algorithm twice will return the same identifier both times — but changing a file even slightly completely changes the hash.
After a DMCA complaint is verified by Dropbox’s legal team, Dropbox adds that file’s hash to a big blacklist of hashes known to be those corresponding to files they can’t legally allow to be shared. When you share a link to a file, it checks that file’s hash against the blacklist.
A bloom filter is a way to maintain a set of elements in a space-efficient way with a low probability of false positives (but no false negatives). By accepting a low probability of inaccuracy, you save quite a lot of space in memory!
Hashing has following uses:
1. In
wikipedia.org
2. To build caches
3. In cryptography
4. In Rabin-Karp algorithm to search substrings
5. In computer graphics etc.
Examples
How Dropbox Knows When You’re Sharing Copyrighted Stuff (Without Actually Looking At Your Stuff)
With a properly implemented hash function, running the same exact file through the algorithm twice will return the same identifier both times — but changing a file even slightly completely changes the hash.
After a DMCA complaint is verified by Dropbox’s legal team, Dropbox adds that file’s hash to a big blacklist of hashes known to be those corresponding to files they can’t legally allow to be shared. When you share a link to a file, it checks that file’s hash against the blacklist.