5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Have you checked the original paper? It's cited at the end of the lecture notes. $\endgroup$ – Yuval Filmus Jul 5 '16 at 16:40
  • $\begingroup$ @YuvalFilmus in the original paper I didn't find the space needed to store the table $G[1..n]$ (there, the random value is called $k$; page 541 "The choices for k (or k') are selected at random until suitable values are found.") $\endgroup$ – Thomas Mueller Jul 5 '16 at 19:22
  • $\begingroup$ The abstract states that the data structure uses "space $n + o(n)$" (though I'm not sure if that's in bits or in words). $\endgroup$ – Yuval Filmus Jul 6 '16 at 6:41
  • $\begingroup$ @YuvalFilmus yes that's true. For example in Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions (which is the basis for Hash, displace, and compress), space is described as "An FKS hash function description occupies $O(n)$ machine words". Sure, you could say $n$ needs to fit in a machine word. But Hash, displace, and compress doesn't talk about $O(n)$ machine words any more, but $O(n)$ bits. That's why I ask. $\endgroup$ – Thomas Mueller Jul 6 '16 at 6:57
  • $\begingroup$ Whether the unit of measure is bits or words should be determined from context or, better, mentioned explicitly in the paper. If you have qualms about the paper, you can contact the authors. $\endgroup$ – Yuval Filmus Jul 6 '16 at 6:59
2
$\begingroup$

Space is counted in machine words rather than in bits. A machine word is allowed to contain a member of the universe $U$, and so is $O(\log |U|)$ bits wide. The array $G$ stores hash functions, via their index inside some collection of universal hash functions. The lecture notes don't mention this, but there are collections of universal hash functions of size $O(|U|^2)$. If you use one of these collections, each entry of $G$ takes $O(\log (|U|^2)) = O(\log |U|)$ bits to store, and so $O(1)$ machine words.

Why is it meaningful to count space in machine words? First of all, even if you store your set as an array (with logarithmic access time, using binary search), the number of bits is $O(n \log |U|)$ rather than $O(n)$. If we want such an array to be considered taking up linear space, we need to "divide" by $\log |U|$, and the simplest way to accomplish this is to allow each memory cell to contain $O(\log |U|)$ bits (the exact constant doesn't matter).

Another reason we would like to allow cells to contain an unbounded number of bits is so that they can store indices. When you implement binary search, or any other algorithm, you have variables which store indices in the array. These variables take $O(\log n)$ bits to store. When discussing algorithms, however, we often think of an index as taking $O(1)$ space. Again, the way to accomplish this is to allow each memory cell to contain at least $\log n$ bits.

On the other hand, if we allow memory cells to be of arbitrary size, then the space measure becomes trivial, since anything can be done in $O(1)$ space (though depending on the exact computation model, you might have to pay in terms of running time). The usual convention in algorithms is to allow each memory cell to contain $O(\log n)$ bits, where $n$ is the input size (in bits). In this particular case, it is more meaningful to allow a machine word to contain $O(\max(\log n, \log |U|))$ bits, and this is the way we measure the space consumption of the algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.