3 ms·
To make a sorted hash list as space efficient as a bloomfilter you need compress it by taking advantage of the shared prefix of consecutive hashes.
by CodesInChaos 8y ago
To make a sorted hash list as space efficient as a bloomfilter you need compress it by taking advantage of the shared prefix of consecutive hashes.
- dwaite 8y agoWould that be a trie?
- bradleyjg 8y agoProbably some sort of radix tree (which is a kind of trie) would be best.
- bloomthrowaway 8y agoyou're right, although I don't think compression would save a ton of space since the hashes are random. Might save a bit or maybe 2 per entry