Bloom filter:
A quick way to do a probabilistic check of if an element is in a set.
Setup: Take the hash of each element in the set, bitwise-or them together.
Lookup: Take the hash of the element you wish to lookup. If any of the bits that are on in this hash are off in the Bloom filter, you know that the element is not in the set. Otherwise, the element is probably in the set, but could be a false positive.
By choosing the length of the hash and the hash function, you end up with ~10 bits/element for a 95% success rate.
As most of the password hashes will be misses, this is an ideal situation. The only time you actually need to do the slow lookup is when a password is a hit.
