Hash tables and bit buckets

So I was working on homework for my database II class this morning (very early this morning, I might add) when I came across the final problem asking what a hashing table with the following hashing formula with various values of B plugged into it would be useful for:

H = n2 mod B

Now, using the value of 10 for B doesn’t really help all that much, as you leave four of the buckets empty at all times and four of the other buckets will get double filled, assuming an equal distribution of values for n (0,1,2…) But there is a reason to use this! What happens if you set B=2, and start plugging in negative values in for n? Well….

  • 102 mod 2 = 0
  • 112 mod 2 = 1
  • 122 mod 2 = 0
  • etc.

We get alternating values of 0 and 1. But we could do this without going the extra step of squaring the value and get the same result, right? Well, yes and no… what happens if we input a negative number for n?

  • (-10) mod 2 = 0
  • (-11) mod 2 = -1

Uh-oh! Now we have a situation where we are getting a value that does not fall into a bit bucket that exists! What to do, what to do? Well, if we square the value of n in this case, all of the even values of n, whether they are positive or negative, will fall into the 0 bucket, and all of the odd values of n, positive or negative, will fall into the 1 bucket:

  • ( -10)2 mod 2 = 0
  • (-11)2 mod 2 = 1

Thus, problem solved! Now I just hope that I got this right and I get the nice extra credit that I so richly deserve for being a fucking genius. 🙂