# Set data structure for efficient repeated insertions

I'm looking for a space-efficient data structure that holds sets (no repetition) of wordsize elements and supports fast insertion (amortized O(1)). By "space-efficient" I mean, ideally, $n + o(n)$ words to store $n$ elements.

Being a set is an important part of the question: if each element is added $\log n$ times the space used can't be $n\log n$.

The structure should also support listing its elements (reasonable efficiently); any sane structure should have no trouble here. (Fast membership queries are a plus.)

• Is there a reason that a hash table wouldn't do the trick? – Dave Jul 17 '11 at 5:28
• @Dave: I don't think of that as meeting the space requirement, but I suppose a sufficiently strict dynamic resizing schedule could make it work. But generally I'd like to see what's out there before actually writing code. – Charles Jul 17 '11 at 6:01
• To get amortized $O(1)$ with dynamic resizing, you have to increase the size by a constant fraction, which I don't think meets the space requirement if you want to strictly meet $n+o(n)$. – Dave Jul 17 '11 at 7:22
• OK, this is a bit silly—but given that your universe is of constant size (wordsize elements), even a full bit vector would have a size of $O(1)$… – Magnus Lie Hetland Jul 17 '11 at 12:47
• @Magnus: I guess that it is meant that the actual functions behind the O- and o-notations in the question do not depend on the word size. – Tsuyoshi Ito Jul 17 '11 at 15:19

We first give a representation of a set $S \subseteq U = \{0, \dots , m − 1\}, |S| = n$ that supports membership queries in $O(1)$ worst case time and insertions into/deletions from $S$ in $O(1)$ expected amortised time. The representation uses $B + o(B)$ bits, where $B = \lceil lg \binom{m}{n} \rceil$ is the information-theoretic minimum space to represent $S$.