Solves
membership
Articles
DS
Data structure
Cuckoo hashing
Two nests per key, a lookup in at most two probes; insertion evicts tenants. Works up to a load of 1/2, with buckets up to 98 %.
lookup at most d probes in the worst case; insertion O(1) on average below the threshold
1 problem
DS
Data structure
Bloom filter
Says “surely not” or “maybe yes” about set membership, at about 10 bits per item.
O(k)
2 problems
Problems
Often together
hashing 2 graph 1 randomized 1 classic 1 probabilistic 1 bitset 1 sketch 1 databases 1 security 1 in production 1 interviews 1