8
$\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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ ok thanks this was the first time I came across mod for non integer.So What is the final mapping. $\endgroup$
    – Parag
    Commented Nov 18, 2013 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
    Commented Nov 18, 2013 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$
    – Parag
    Commented Nov 19, 2013 at 5:57
2
$\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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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