Реализация набора с постоянным поиском

Question

Мне нужно хранить набор из n чисел от 1 до 10 ^ 9, так что

1. Инициализация занимает O(n) времени - это математическое ожидание
2. Поиск занимает O(1) времени - это худший случай
3. Структура занимает O (N) памяти

Не могли бы вы помочь мне понять, возможно ли это реализовать и как?

Я думаю, что можно использовать хеш-функции или искать деревья для этого.