# How do I design a hash function for this given case?

My professor gave me the following problem.

You are to store objects identified by integers from the interval $[0..10^9 − 1]$. You expect never to have to store more than 1400 objects. Design the hash function h of the type discussed in class (universal hashing). That is, select a prime number on which the hash function will be based, the ”dimensionality” of your hash funciton, say k, and k parameters $\{ a_0, . . . , a_{k−1}\}$. Given your selections, what is $h(350620501)$? Explain all choices you made.

I've developed the following answer.

Generate a prime number p that is greater than the range of keys that the objects in the table will be identified by $[0…(10^9-1)]$. The first prime greater than $10^9$ will do for this example, so let $p = 1000000007$. Because the data type to be hashed are integers, two randomly generated integers modulo p are chosen to add randomness to the hash function, so let $a = 63873076$ and $b = 87191394$. The number of slots in the table will be the maximum number of objects we will be expecting to store, so let $m = 1400$. The universal hash function will be defined as:

$h(x) = ((ax + b) \mod p) \mod m$

$h(350 620 501) = 7$

This is my first time generating a hash function, so I wanted to ensure that my solution and understanding was correct--specifically, my thinking behind choosing the value for m and the reason that values a and b are added to the function.

• Use $10^9$ to get "$10^9$" and in general google for StackExchange LaTeX guide to see how to write all math expressions. Your reasoning is fine. – user21820 Oct 18 '15 at 1:54
• First time using LaTeX. Thanks for the pointer to the guide. – Jared Oct 18 '15 at 2:01
• I should mention that it depends on what kind of hashing you are using. It's fine if you use a linked list for each hash value, which is always what you should use anyway. – user21820 Oct 18 '15 at 3:36