I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored.

One way this can be seen:

  • we have a range of integers $S = \{1, \dots{}, N\}$ with $N$ big (say $2^{40}$)
  • we have a function $f : S \to S$ with, supposedly, many collisions (the images are uniformly distributed in $S$)
  • we then need to store $f[S]$, that is $\{f(x) | x \in S\}$

I have a quite accurate (probabilistic) estimation of what $|f[S]|$ is, and can therefore allocate data structures in advance (say $|f[S]| \approx 2^{30}$).

I have had a few ideas, but I am not sure what would be the best approach:

  • a bitset is out of the question because the input set does not fit into memory.
  • a hash table, but (1) it requires some memory overhead, say 150% of $|f[S]|$ and (2) the table has to be explored when built which requires additional time because of the memory overhead.
  • an "on the fly" sort, preferably with $O(N)$ complexity (non-comparison sort). Regarding that, I am not sure what is the major difference between bucket sort and flashsort.
  • a simple array with a binary search tree, but this requires $O(N \log |f[S]|)$ time.
  • maybe using Bloom filters or a similar data structure could be useful in a relaxation (with false positives) of the problem.

Some questions on stackoverflow seem to tackle with this sort of things (https://stackoverflow.com/questions/12240997/sorting-array-in-on-run-time, https://stackoverflow.com/questions/3951547/java-array-finding-duplicates), but none seems to match my requirements.

  • 2
    $\begingroup$ Do you need to enumerate f[S] (whatever it is), or to be able to tell quickly whether some x is in it? $\endgroup$ Commented Sep 3, 2012 at 20:13
  • $\begingroup$ @Gilles: I believe that, since no obvious structure can be found in f[S], the two solutions are equivalent. $\endgroup$
    – doc
    Commented Sep 3, 2012 at 21:23
  • $\begingroup$ Your numbers don't add up. The expected image of a random function on a domain of size $N$ is roughly $(1-1/e)N$. Another issue is that going through $2^{56}$ is going to take too long unless you have a supercomputer or a large cluster at your disposal. $\endgroup$ Commented Sep 4, 2012 at 15:20
  • 1
    $\begingroup$ The time for the binary search tree would be $O(N \log |f[S]|)$, which may or may not be close to $O(N\log N)$ in practice but still is more accurate. $\endgroup$
    – jmad
    Commented Sep 15, 2012 at 8:25
  • 1
    $\begingroup$ With $N \sim 2^{56}$, won't a linear time algorithm be prohibitive too? (From my calculations, even if you consider one element of $S$ in 1 nano-second, it would take you a good 2 years!). $\endgroup$
    – Aryabhata
    Commented Sep 26, 2012 at 18:55

1 Answer 1


Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A[y]$, $y \ge 0$, represents the range $[2^m y, 2^m(y+1)-1]$. For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits. Try to store $z$ (not $x$!) at location $y$:

  • When $A[y]=z$ already, do nothing: $x$ is a duplicate.

  • When $A[y]$ is uninitialized, store $z$ at $A[y]$.

  • Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists. You will have to search linearly through the list headed by $A[y]$ and, depending on what the search uncovers, potentially insert $z$ into the list.

At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short. When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing. If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$). This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it is a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.

  • 1
    $\begingroup$ I think the second-to-last paragraph is the central one here, and should probably be at the top (as idea). I don't know the term "bin and chain" (although it makes sense after reading the post). This idea can be extended to tries. $\endgroup$
    – Raphael
    Commented Nov 22, 2012 at 10:26
  • $\begingroup$ So, this is $\Theta(n^2)$ on poorly-distributed inputs. I don't see how this is efficient. $\endgroup$
    – einpoklum
    Commented Nov 30, 2018 at 23:27
  • $\begingroup$ @einpoklum This answer explicitly describes the conditions in which the solution is efficient. $\endgroup$
    – whuber
    Commented Dec 1, 2018 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.