Another solution is to change the order things are checked in. With optimum k, each hash takes about 1/2 of the possibilities out. If he'd batch it so the memor

Another solution is to change the order things are checked in. With optimum k, each hash takes about 1/2 of the possibilities out. If he'd batch it so the memory accesses are roughly ordered, it would be much faster. EDIT: So, for instance, if k = 19, that means there are 19 hash functions. If he goes through all the inputs, and checks: are there any hashes here falling within the first 1/19 of the memory space? If not, keep it. If so, check whether any are unset. If not, keep it. If they are, zero the pointer to the input in the array. After this is done, he should be rid of roughly 32% (0.5 * (1-(18/19)^19)) of candidates. The second pass throws out 33% of candidates, and so on and so forth. He could even keep an absurdly large value for k and n: if it is 128G, then k = 19'053, meaning he can use an even finer increment. He'd have to spill the filter to disk, but the access patterns will be great.