How does std::unordered_set allocate bucket to provide O(1) lookup?

Question

The unordered_set should provide O(1) lookup time in case of a good hash function.
Each bucket contains items with the same hash value.
Let's assume that our hash function is ideal and gives no collisions at all.
Hash values can vary from 0 to max(std::size_t).
How to organize unordered_set without allocating continuous memory interval for buckets and to provide O(1) lookup?
We can not allocate continuous memory interval because if we allocate then we use a lot of memory for only to several hash values - 0 and 1000000 for example.
Values in the middle are not used at all, but we allocated memory for them.

Answer 1

Each bucket contains items with the same hash value.

Wrong. Each bucket "contains" items with the same value of:

       hash(key) % current number of buckets.

Let's assume that our hash function is ideal and gives no collisions at all.

Not having collisions in pre-mod space isn't necessarily ideal: what matters is collisions after modding (or masking if there's a power-of-2 bucket count, e.g. Visual C++) into the number of buckets.

And even then, having no collisions is not (normally) the design goal for a hash function used with a hash table. That's known as perfect hashing, and usually only practical when the keys are all known up front, pre-inserted, then fast lookup is wanted for the rest of the application's lifetime. In more common scenarios, the aim in the general case is to have - when inserting a new value - it be roughly as likely that you'll collide with already-inserted values as it would be if you picked a bucket a random. That's because a high-quality hash function effectively produces a random-but-repeatable value. Hash functions work well because it's acceptable to have a certain level of collisions, which is statistically related to the current load factor (and not the size() of the container).

Hash values can vary from 0 to max(std::size_t). How to organize unordered_set without allocating continuous memory interval for buckets and to provide O(1) lookup?

You typically have somewhere between 1 and ~2 buckets per value/element when the table had its largest size(). You can customise this somewhat by calling max_load_factor(float) to determine when the table resizes, but you can't customise by how much it resizes - that's left to the implementation. GCC will usually pick a prime a bit larger than twice the current size. Visual C++ will usually double the buckets.

We can not allocate continuous memory interval because if we allocate then we use a lot of memory for only to several hash values - 0 and 1000000 for example. Values in the middle are not used at all, but we allocated memory for them.

This ignores the modding of the hash value into the bucket count. (It also ignores the viability of sparse arrays, which can be practical because virtual address space can be massively larger than the physical RAM backing it, but that's not the point of hash tables.)