For pure speed, nothing will beat Perl's hashes. You can do it faster in C, but the penalty of calling in and out from Perl will alway slow you down whatever you try.

The real problem is that you'll rapidly run out of space at which point you'll compromise from fastest, to get fastest with less space.

At that point you'll be looking at some form of sparse bitmap of which there are many algorithms but none that cannot be undone by uncooperative data, so you need to get to know the distribution of your data and tailor your algorithms accordingly. If your data is truly random, then you may be out of luck.

A supersearch for my name and judy arrays will turn up a compact, single file version of the Judy array code that compiled clean and worked very well for that application. Still slower than hashes, but far more compact. Just hope you don't find any bugs, because the Judy code is horribly complex.