2 ms·
The fact that Bloom filters are so far from the information theoretical limit for the problem they address offers some hope. I think it’s reasonable to expect
by hinkley 5y ago
The fact that Bloom filters are so far from the information theoretical limit for the problem they address offers some hope.
I think it’s reasonable to expect that there are many structures out there that can achieve the same API in less space (time?) and that at least a few of those can achieve a better API in the same space, even if it means giving up some gains to store extra metadata.
Example: linked list hashmaps, which store two extra pointers to remember insertion order.