3 ms·
I always thought the explanation of bloom filters was way overcomplicated. They are simply chaining hash tables, without the chain. Chaining hash tables first h
by hn_throwaway_99 6y ago
I always thought the explanation of bloom filters was way overcomplicated. They are simply chaining hash tables, without the chain. Chaining hash tables first hash a value to an entry in an array, then walk down the chain at that entry to see if the value is actually there and disambiguate when different values hash to the same array entry. Bloom filters just get rid of that second step and leave it up to you to determine if the thing you are looking for is "really" there.
Of course, that assumes familiarity with chaining hash tables, but I feel like every CS program goes over hash table implementations, but bloom filters weren't something I learned about until I left college.