This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 72

Static hashing challenge

Due: March 22
Points: 1-4

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\) 1
\(25\le s\le 39\) 2
\(21\le s \le 24\) 3
\(s = 20\) 4
\(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.