1
$\begingroup$

The question is a true or false question:

Hash tables using probing for collisions run in constant time with respect to how many items are in the hash but are at least linearly dependent on how full the hash is.

I think it's true but I don't fully understand why and I don't understand the term linearly dependent.

Any help would be great, thanks.

$\endgroup$
0
$\begingroup$

The average number of positions addressed is $$ \frac{1}{2} \left(1 + \frac{1}{1-\alpha}\right) $$ for linear probing and $1 + \alpha/2$ for chained hashing. Here $\alpha$ is the load factor. For each constant $\alpha$, this average is constant, but it depends on $\alpha$. The expression $1/(1-\alpha)$ blows up as the table gets full ($\alpha \to 1$), which is probably what is meant by the dependence is at least linear. The dependence is on the load factor rather than on the absolute number of elements in the table, which is not the deciding factor.

Usually, a linear dependence (not to be confused with the same terminology from linear algebra!) would be $\Theta(\alpha)$, at least linear would be $\Omega(\alpha)$, and more than linear $\omega(\alpha)$; but here $\alpha \to 1$ rather than $\alpha \to \infty$ so terminology is not standard. Perhaps the correct variable, which does go to $\infty$, is $1/(1-\alpha)$. In this case, we do have linear dependence for linear probing.

$\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.