1
$\begingroup$

In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:

$h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$

where $h'$ was h "prime". So, what I am supposed to conclude for $h'(k)$ to be? Is it any different from the value I get by computing $h(k)$

$\endgroup$
  • 1
    $\begingroup$ It has no particular significance. It could have been any other symbol instead of $h’$. It’s different from $h$, though. $\endgroup$ – Yuval Filmus Sep 5 at 5:03
2
$\begingroup$

$h'(k)$ is the value returned by the original unmodified hash function when applied to the element $k$. If the $h(k)$ slot is not free then $h(k,i)$ for $i=0,1,2,\dots$ gives a sequence of modified hash values which can be tried in turn until a free slot is found.

$\endgroup$
-1
$\begingroup$

h'(k) is mod(k,M) it is usually represented as h(k)

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