In FKS hashing, I wonder if the size of the table $G[1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability of a hash function $g_i$ is higher than 0.5, I can see that it will mostly hold small values (assuming we start with $g_0$, and if that doesn't work, try $g_1$ and so on). But I think for $n$ to $\infty$ there will be larger values as well, so that the number of bits for each entry is $log^*(n)$ and not fixed. Right?The reason I ask is that many minimal perfect hash functions, such as the CHD algorithm, rely on a similar mechanism, and those algorithms claim to be strict $O(n)$ space.
Is FKS hashing really linear space?
data structures;hash tables;hashing;space analysis