5 ms·
To me a cache is actually the inverse data structure of a bloom filter. A bloom filter will return whether something is in a set with potential false positives
by slededit 8y ago
To me a cache is actually the inverse data structure of a bloom filter.
A bloom filter will return whether something is in a set with potential false positives but never false negatives.
A cache will return whether something is in a set but with potential false negatives but never false positives (i.e. item is not currently in the cache but exists in the set).
- tpetry 8y agoIf the bloom filter says the password has been breached before you check it against haveibeenpwnd database ;) So kind of a caching layer caching every password that has definitely not been breached.
- chii 8y ago> So kind of a caching layer ... i'd name this sort of thing a filter, rather than a cache.
- JackCh 8y agoCalling a bloom filter a filter is a tautology and tautologies don't have much pedagogical value. Explaining what a bloom filter is (and/or is useful for) by imperfect analogy to caching is less precisely correct than a tautology but will help the uninformed a lot more.
- philwelch 8y agoWell, that’s the pseudo- bit :)