Why do most Bloom Filters use MurmurHash over SHA or MD5? ⚡
All bloom filter operations (get, put) require the key to be passed through the hash function(s) to determine a position in the filter.
For each operation, the hash function will be invoked multiple times, typically thrice, and hence performance is essential. On the other hand, more popular hash functions like SHA and MD5 are cryptographic, which means they are designed to be
- highly secure
- well-distributed with a low collision rate
Ensuring these guarantees makes computing SHA and MD5 expensive.
MurmurHash, on the other side, is a non-cryptographic hash function that is optimized for speed and hence is often used in scenarios where speed is critical, such as bloom filters, hash tables, and caches.
Because Bloom Filters has no requirement of being secure, we can trade security for performance and hence MurmurHash becomes the default choice.
github repository: https://lnkd.in/gZZTsNsC live stream bloom filter implementation: youtu.be/UVFnabieyzc
⚡ I keep writing and sharing these engineering nuggets, so if you are keen on learning them, follow along.