BTW, as you desire to decrease your error rate Cuckoo hashing starts to become an attractive alternative to Bloom filters: http://en.wikipedia.org/wiki/Cuckoo_

BTW, as you desire to decrease your error rate Cuckoo hashing starts to become an attractive alternative to Bloom filters: http://en.wikipedia.org/wiki/Cuckoo_hashing http://en.wikipedia.org/wiki/Cuckoo_hashing http://www.ru.is/faculty/ulfar/CuckooHash.pdf http://www.ru.is/faculty/ulfar/CuckooHash.pdf You can get your hash table utilization to almost 100%. If you're willing to accept a 64-bit hash function and you have 2 billion unique strings you'll need just over 16GB to do it all in one pass. A 64-bit hash is is just barely enough for 2 billion items. You might get a handful of collisions. Add more bits to reduce the probability. 128-bits would double the required size to 32GB but you're unlikely to ever see a collision in your life time. If 16GB or 32GB is too much you could do it in multiple passes. Make N passes through the text file and adjust the range of hash values you accept to test only 1/N each time. 8 passes through the original file with a generous 128-bit hash would take only 4GB of RAM. I have the feeling this is more work than you would want to put into the problem, though.