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

- Your hash function. Remember that it should be very simple.
- The value of \(s\)
- A promise that you have checked that all 20 integers hash into different buckets
- 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.