Constant time function to map set on range

Question

So I have a set of positive integers S (like {1, 5, 9, 29, 12}).
With this set, I want to construct an algorithm that can, later on, tell me, given any element, its position on the set in constant time (always the same regardless of how big the set was).
Kind of like a hashmap, but those are O(1) in average, not always. There's always a chance for collisions.
One could build an array with size max(S) and store, in each element's index, its position. But this would take as much space as the biggest element in S (not ideal; the size should be linear to the size of S).