In Python, lookups in a set stay constant time on average O(1), even with hundreds of millions of elements, as long as there's enough RAM and no serious hash collisions. So, I think, that the maximum size of a set for fast lookup is mostly limited by available memory, not by the algorithm itself.