Problem 81

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Static hashing challenge

Due: April 19
Points: 2-6

Consider the following list of 20 integers in the range of 0 up to 999,999:

[319591, 806701, 204176, 805272, 679810, 268615, 410622, 
 598278, 212593, 892307, 201299, 32620, 104299, 148144, 
 829010, 493111, 103713, 572558, 854484, 348654]

Find a simple (one-liner, constant-time cost) hash function that maps each integer into separate buckets in a very small hash table. The smaller your hash table, the more points you will earn, according to the following table:

Table size Points earned
\(s \ge 100\) 0
\(40\le s\le 99\) 2
\(30\le s\le 39\) 3
\(25\le s\le 29\) 4
\(21\le s \le 24\) 5
\(s = 20\) 6
\(s \lt 20\) 1000

For example, using the following hash function results in a size \(s=100\) hash table, with each of the 20 integers going into separate buckets:

\[h(x) = \left(\left(510964x + 122200\right) \bmod 1000003\right) \bmod 100\]

(Hence the reason why you get no points for \(s\ge 100\); I've already done that much for you.)

Here's what you need to turn in:

  1. Your hash function. Remember that it should be very simple.
  2. The value of \(s\)
  3. A promise that you have checked that all 20 integers hash into different buckets
  4. Tell me briefly how you got \(h(x)\). Of course you should cite any sources. Feel free to attach a code printout if you wrote some code.