Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search($x$) can be done in $O(1)$ time, where $x\in A$. Space used by data structure should be $O(n \log^{*}n)$ or $O(n)$ bits. Model of computation is RAM.
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
Bit vectors, as mentioned by Raphael, fulfill all the requirements and it is a very simple and fast option. But there is an alternative called Minimal Perfect Hashing, which could be represented succinctly requiring few bits in practice.
A bit vector $B$ can also be compressed in order to achieve $$O(nH_0(B)) \text{ bits}$$ of space. Depending on the distribution of 0's and 1's, this could be $o(n)$ bits.
