Implementation of set with contant search

Question

I need to store a set of n numbers from 1 to 10^9, such that

1. Initialization takes O(n) time - it is mathematical expectation
2. Search takes O(1) time - it is the worst case
3. Structure takes O(n) memory

Could you help me to understand whether it is possible to implement it and how?

I think one can use hash functions or search trees for it.