Efficient data structure for storing integers in a range?

Say I'm constantly given integers from the range $$[1,2^{32}]$$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $$2^{32}$$ values will have been treated.

What's the best way to store which integers have been treated so far so that we can search if the current integer is a duplicate?

• While I generally agree with the questions D.W. is suggesting, in this case, since you say you know all numbers in the range will show up eventually, a simple bitmap is almost certainly going to dominate on all axes. – Derek Elkins Mar 16 at 4:33
• @D.W. The reason I didn't specify time vs. space being my main criteria is because I assume if there were two options to those ends we could consider both. As for how many integers, that's mentioned already; how much memory, that's included in time vs. space; what architecture, I would have thought the assumed architecture would be your run of the mill desktop Intel/AMD x86_64 processor unless you meant what microarchitecture they were using but I don't think that's relevant. – Ozaner Hansha Mar 16 at 5:04

Since you know you're going to have to deal with all $$2^{32}$$ values eventually, you're going to need at least $$2^{32}$$ bits of memory, one for each value. The pigeonhole principle means that there's no possible way to store all the information you need with fewer bits than this.

So I recommend a straightforward bitmap. In other words, a simple array of bits. When a new value comes in, see if the corresponding bit is on or not; if it's off, flip it on. This takes the minimum possible amount of space, and is extremely fast (since all you have to do is index into an array).

P.S. You need $$2^{32}$$ bits specifically because the numbers could appear in any order. This means that there are $$2^{2^{32}}$$ possible states the program could be in, one for every possible combination of seen and not-seen values. Representing this many states will always take at least $$2^{32}$$ bits. If you knew the numbers would always come in increasing order, on the other hand, there'd only be $$2^{32}$$ states to distinguish between (since all you care about is the highest value seen so far), so you'd need a minimum of $$32$$ bits.

• If the values appeared in order, it would also be the case that we have to deal with all 2^32 values eventually, but somehow we only need 32 bits this time, so that argument doesn't work. It's passing through the halfway point with 2^32 uniformly random bits that is interesting – harold Mar 16 at 6:37
• @harold It has to do with how much information we need to save. In this case there are $2^{2^{32}}$ possible states we need to distinguish between. – Draconis Mar 16 at 14:58
• @Draconis There are $2^{2^{32}}$ possible states because the values can appear in any order. There are only $2^{32}$ states if the values appear in order. I was going to say almost exactly the same thing as harold but decided not to. Focusing on the pigeonhole principle without saying why or even that there are $2^{2^{32}}$ possible states is odd. It's like saying there is an infinitude of primes because of the pigeonhole principle. Your first paragraph is just weirdly and misleadingly written. – Derek Elkins Mar 16 at 19:54
• @DerekElkins Added an explanation of that – Draconis Mar 16 at 19:58
• That last point about how knowledge of the order of the integers would decrease the required bits is a nice addition. – Ozaner Hansha Mar 17 at 0:39

If the integers truly arrive in random order, then a bit array is a good (likely ideal) solution, and would require 512MB.

In the real world, information may be unpredictable, but not random, so a number of data structures optimized for sparse information (including sparse missing information) could be more appropriate if memory usage is a concern. For example, a binary tree of run-length encodings.

Assuming that the integers do not arrive in a truly random order, then the more you know about the pattern, the more potential optimizations will be available to you.