Hacker News new | ask | show | jobs
by desertrider12 1348 days ago
Nope, there will just be 2^8 tables (constant overhead per table) each with 2^24 24-bit keys.

If you start with an array of any N keys, they have 32N bits of information. But once you insert them all into an unordered set like this, you throw away information by losing the order. There are only (2^32 choose N) unique sets of N keys, which is less than N*2^32 for N>1. This checks out in your example - there is only one unique set of all the 32-bit integers, so that should take log2(2^32 choose 2^32) = 0 bits to store sets of this size.