Figure you need at least 12 bytes per entry to store the ID and hash. Then you can only handle 1/12 of your memory size in bytes (so 1 billion entries if you h

Figure you need at least 12 bytes per entry to store the ID and hash. Then you can only handle 1/12 of your memory size in bytes (so 1 billion entries if you have 12 billion bytes of RAM). Much more memory efficient to use a Bloom filter. Build n different ways of hashing the hash (this can be as simple as having some standard hash function H() making the ith different way H(h, i)). Then when you add an entry you write a bit at each of these locations. Instead of writing right away, you check to see if all the bits were already set. If they were, the entry being added is a candidate for a possible collision with some earlier entry, so stream it out to a file or something. Once you have the (much smaller) list of a few million collision candidates, you do another iteration over the whole data set, checking each one against only the collision candidates. The most memory-intensive part is the Bloom filter. You could probably get away with a Bloom filter size of 10 bits per entry or less. (If you want specific numbers, there are lots of online calculators to help you calibrate the size of a Bloom filter.) But given this is a one-off search, and you had a machine with enough RAM to find a collision, an ordinary hash-based set implementation is good enough and saves the most precious resource of all, developer time :)