# perfect hashing when not knowing the keys

knowing only the number of keys, n, how can you create a data structure of some sort that satisfies the following:

1. initialization takes O(n) time
2. after being initialized, you can insert and search keys and the probability that these actions take O(1) time is higher than 0.5.

how can you extend the algorithm so that the probability for (2) is higher than 0.75?

and in general, how can you extend it so that the probability is higher than $$1-0.5^c$$ for some natural c, and the time complexity is $$O(n^2)$$?

thank you!

• What precisely do you mean by "the probability that these actions take $O(1)$ time"? – Robert Israel Jun 4 at 12:00