5
$\begingroup$

I need some help understanding the problem statement in CLRS 11.3-4 pg 269. It says:

Consider a hash table of size $m = 1000$ and a corresponding hash function $ h(k) =\left \lfloor m(kA \bmod 1) \right \rfloor $ for $A = (\sqrt5 - 1)/2$. Compute the locations to which the keys 61, 62, 63, 64, and 65 are mapped.

Is $\mod 1$ a misprint in my copy? Also $A$ is a real number. Is modulus defined for non-integer numbers?

$\endgroup$
6
$\begingroup$

That's not a misprint. $kA \bmod 1$ makes sense. For instance, $37.239 \bmod 1 = 0.239$.

$\endgroup$
  • $\begingroup$ ok thanks this was the first time I came across mod for non integer.So What is the final mapping. $\endgroup$ – p.j Nov 18 '13 at 21:27
  • 2
    $\begingroup$ @p.j Note that the common definition for modulo does not need that any of the numbers is integer: $a \mod b = c \iff \exists k \in \mathbb{Z}.\ a - bk = c$. (Typically, one requires $c < b$ to get a well-defined operation, but in mathematics modulo is used as a relation.) $\endgroup$ – Raphael Nov 18 '13 at 21:42
  • $\begingroup$ What I think he used this hash function because after solving decimal part is changing even for small change in number , I am still not sure but it seems it will give less number of collision. $\endgroup$ – p.j Nov 19 '13 at 5:57
1
$\begingroup$

Thanks to for clarifying mod 1 concept , for constant $\mathcal{A}$ I got the proper explanation in CLRS itself it says : Although this method works with any value of the constant $\mathcal{A}$, it works better with some values than with others. The optimal choice depends on the characteristics of the data being hashed. Knuth suggests that $$ \mathcal{A} \approx (\sqrt(5) - 1)/div 2 = 0.6180339887 ... $$ is likely to work reasonably well. As an example, suppose we have $ \mathcal{k} = 123456, \mathcal{p} = 14, \mathcal{m} = 2^{14} = 16384,$ and $ \mathcal{w} = 32.$ Adapting Knuth’s suggestion, we choose $\mathcal{A}$ to be the fraction of the form $$\mathcal{s}/2^{32}$$ that is closest to $$(\sqrt(5) - 1)/ 2,$$ so that $$ \mathcal{A} = 2654435769/2^{32}.$$ Then $$\mathcal{k} . \mathcal{s} = 327706022297664 =(76300 . 2^{32} )+ 17612864,$$ and so $\mathcal{r_{1}} = 76300$ and $\mathcal{r_{0}} = 17612864.$ The 14 most significant bits of $ \mathcal{r_{0}} $ yield the value $\mathcal{h}(k) = 67$.

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