Best way we know search for an integer Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?"

My question is about the best way we know in terms of time/space to answer this query. Ultimately, the time should be guaranteed (not randomized) and the space must be polynomial of $n$.

Firstly, one can use let's say 2-3 Trees or another type of search trees to do this in $O(log n)$ time and $O(n)$ space.

Secondly, one might say that it can be done in $O(1)$ with hashing, however I should note that this time is random and we are looking only for deterministic algorithms. Universal hashing requires a lot of space.

So, one way to approach the main question is to answer if there is a perfect hashing constructable in poly-time and poly-space?

Another approaches are also appreciated. Thanks.
A very simple solution if your integers are not too big, let's say biggest integer is $U-1$ and there are $U$ different integers (between 0 and $U-1$), is to build a table T (bit matrix) of size $U$ with all bits set to $0$. Upon occurrence of item $k$ set $T(k)\leftarrow 1$.

If you want to search for an item $k$ you simply check if $T(k)$ is $1$ or $0$.
This solution takes $\Theta(U)$ space and $\Theta(1)$ time per inserted item, or per search.
If $U$ is much less than $n$ and you don't make deletions then I think
this solution is ideal in your case. If you make deletions of $U &gt; n$ then more sophisticated solutions are needed