# 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
Commented Jul 17, 2011 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. Commented Jul 17, 2011 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
Commented Jul 17, 2011 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)$… Commented Jul 17, 2011 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. Commented Jul 17, 2011 at 15:19

## 2 Answers

I think Raman and Rao's "Succinct Dynamic Dictionaries and Trees" meets the bounds you specify. From the abstract:

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$.

• This looks fantastic. (You'll understand if I read the paper before accepting, though, right?) Commented Jul 18, 2011 at 13:42

If your application can tolerate some false positives, then you should look into using a Bloom filter.

Paraphrase of Wikipedia: A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed. The more elements that are added to the set, the larger the probability of false positives.

• Mine can't, but +1 for a great data structure. Commented Jul 18, 2011 at 13:36