@Carl Love I have nothing intelligent to say about this at the moment. I'll just give my parameters and mention another issue.

Set X, of size roughly 1.5 million, is a collection of hash values of 1.5 million larger objects. So let's call that X₀ and  write
h : X₀ -> X
Likewise, we have a set Y₀ of size 270 billion and h : Y₀ -> Y. The hash function seems fast and, after your note about integer word size, I modified the hashes to fit inside a 64-bit word as false positives are far from my biggest problem.

Your advice suggests that computing set intersection will be faster than an iterated membership test (and that seems natural in retrospect). This sort of "group testing" is used often in statistics. So I use a chunk of size 10,000 at the moment. It takes Maple 34 CPU seconds to generate 10,000 hashes and check that there are no collisions (so far). If I do find a collision, I will have to go back in, element by element, and find which member of Y₀ and which member of X₀ have the same hash.  This is not so hard if the chunk size is small: 10,000 individual lookups in a keyed table of size 1.5M. Then I have information for the algebra question that gave rise to this excursion. At the moment, with 2.5 million elements of Y₀ checked, I am 0.001% of the way through my search. I will next try larger chunks.

EDIT: To answer your question, elements of Y₀ are generated on the fly, using randcomb( . ) or nextcomb( . ) as collections of products of elements of a finite group. As I learn more about the group structure, I expect to cut the search down from 270 billion to less than a billion, but the need for these tools is likely to remain unless I suddenly become clever.

UPDATE:  I wonder whether it is memory consumption that makes the running time non-linear.
Chunks of size 10,000:  34 CPU seconds per chunk
Chunks of size 100,000: 2330 CPU seconds
Chunks of size 1,000,000: killed the process after 5 hours.
 

@Carl Love Great answer. Thanks.