0
$\begingroup$

I am reading the book mining of massive data sets. (http://mmds.org/) In its chapter 1 http://infolab.stanford.edu/~ullman/mmds/ch1.pdf following section is there on page 9.

Example 1.4: Suppose hash-keys are positive integers. A common and simple hash function is to pick h(x) = x mod B, that is, the remainder when x is divided by B. That choice works fine if our population of hash-keys is all positive integers. 1/Bth of the integers will be assigned to each of the buckets. However, suppose our population is the even integers, and B = 10. Then only buckets 0, 2, 4, 6, and 8 can be the value of h(x), and the hash function is distinctly nonrandom in its behavior. On the other hand, if we picked B = 11, then we would find that 1/11th of the even integers get sent to each of the 11 buckets, so the hash function would work very well.

I could not understand this statement

hen only buckets 0, 2, 4, 6, and 8 can

be the value of h(x), and the hash function is distinctly nonrandom in its behavior.

What is the example in this trying to say? The hash in my understanding is made by h(x)= x mod B , so if B=10 then x mod 10 will have all values from 0,1,2,3,4,5,6,7,8,9.

$\endgroup$
0
$\begingroup$

This is a sentence a few lines above the particular example

To be precise, if hash-keys are drawn randomly from a reasonable population of possible hash-keys, then h will send approximately equal numbers of hash-keys to each of the $B$ buckets.

This property is not satisfied, in particular, odd-numbered bins would not have any entry if $B=10$.

However, if $B$ is $11$, then we have $h(2)=2, h(4)=4, h(6)=6, h(8)=8, h(10)=10, h(12)=1$ and so on. Note that even the odd-bins would be filled uniformly. This phenomenon is due to $2$ and $11$ are coprime.

$\endgroup$
  • $\begingroup$ I am not able to understand your explanation can you elaborate a little bit more.Why will odd number bins not have an entry if B=10. When B=11 then h(2)=2 and so that you mentioned how do you come to that conclusion? The hash in my understanding is made by h(x)= x mod B , so if B=10 then x mod 10 will have all values from 0,1,2,3,4,5,6,7,8,9. $\endgroup$ – political science Sep 15 at 17:14
  • $\begingroup$ all the inputs are even numbers. If you write an even number, $d$ as $d=10q+r$. Since $d$ is even and $10q$ is even, $r$ has to be even too. If you write $d=11q+w$, The parity of $11q$ can be odd or even, hence this makes a difference. $\endgroup$ – Siong Thye Goh Sep 15 at 17:25
  • $\begingroup$ Ok this comment makes some sense, now the line in your answer odd numbered bins would not have any entry if B=10 I am not able to get this line. Then you say B is 11 then we have h(2)=2 can you give an example of how this is possible. I am not able to visualize it. Say x=13 h(x)=13 mod 11 =2 is this what you mean to say, and similarly if x=14 ,h(x)=14 mod 11=3, if x=15 h(x)=15 mod 11 =4 is this what you are trying to say or the example or I have missed something. $\endgroup$ – political science Sep 15 at 17:28
  • $\begingroup$ Take an even number, divide it by $10$, will you get an odd remainder? $2$ divided by $11$ will give $2$ as the remainder. As for your example of $x=13$, please remember that your inputs are all even number, you won't get $x=13$ as your input. Similarly, you won't get $x=15$. Try to work out the possible outputs for a few more even numbers and observe that you can hit every bin when $B=11$. (remark: dozing off soon, might not response quickly) $\endgroup$ – Siong Thye Goh Sep 15 at 17:36
  • $\begingroup$ I re read the question and got it my brain has stopped working when I read things forward, the things or paragraph read 5 minutes ago I forget so I could not connect what I read. I had forgotten that there won't be any odd input as per example. $\endgroup$ – political science Sep 15 at 17:44

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.