4 ms·
If you switch from linear probing to cuckoo hashing, then you end up with a cuckoo filter, which is more compact than a bloom filter for a given false-positive
by aidenn0 6y ago
If you switch from linear probing to cuckoo hashing, then you end up with a cuckoo filter, which is more compact than a bloom filter for a given false-positive rate. The compactness comes from the fact that Cuckoo hashing allows load factors of over 90% which are impractical for linear-probing.
- cb321 6y agoWell, sure. You can also switch to Robin-Hood linear probing to work well at high load factors and retain the almost never >1 DRAM hit. These are just various hash table options to claw back some load factor ratios of space usage.