Selected solutions for HW #3

#3.  The hash function that S. L. Ow has recommended is
a terrible hash function for the problem at hand.

The reason it is bad is because there are only
(44 + 45 + 46 + 47 + 48 + 49) - (1 + 2 + 3 + 4 + 5 + 6) + 1 =
259 different hash values that can be created.
If there are millions of distinct combinations of
numbers chosen by ticket buyers, then there will
be several thousand combinations stored in each
bucket corresponding to a hash value.

There are several hash functions that behave better.
One method is to treat the six-number combination
as a six digit number, where each digit can range in
value from 1 to 49.  For example, the following hash
value reduces the likelihood that two different combinations
of numbers will hash to the same hash value.

                                   5
h(x_1, x_2, x_3, x_4, x_5, x_6) = sum  (x_i * 53^i)   mod m
                                  i=0

where m is roughly the same size as the number of packets
expected to be bought.

Note that 53 is a prime number (to reduce the likelihood
of strange number-theoretic problems) greater than 49
(to reduce the possibility of obvious collisions).

To illustrate the last point, suppose instead of 53,
we chose 37.  Then it is easy to find two combinations
that hash to the same value.  For example,
  1, 2, 3, 4, 6, 7 and 1, 2, 3, 4, 5, 44  would hash
to the same value.