1) Don't access randomly. That means either that the hash function you use is more like a reducing/mapping function (i.e. order preserving), or you iterate in t

1) Don't access randomly. That means either that the hash function you use is more like a reducing/mapping function (i.e. order preserving), or you iterate in the hashed order of your data. Obviously, this only works for scans and batch processes, not random user queries unless you can batch them. 2) Have a leakier bloom that fits in your L1/L2 cache size. You may have to have 2 layers of bloom filters, and this will be highly dependent on the relative expenses of the various operations.