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.

# 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.