Hashing: You are to store objects identified by integers from [0..N − 1]. You expect never to have to store more than K objects. How would you design the hash function? Describe a general approach to design the hash function in terms of N and K. If N = 100000 and n = 50, give a concrete example of a hash function h. What is h(63455)?
Here is my attempt:
*note: $n$ is the "space of IDs" I believe.
Also $k$ = "k objects to store at the most" I also think..
$N = 100,000$, $n = 50$
I picked a prime number $k$ such that $n \le k \le 2n$.
I let $k = 61 \implies 50 \le 61 \le 100$
Now I choose 3 numbers in the bounds of $0 \le (n-1) \implies$ some 3 numbers between 0 and 50
I picked $23,14,5$
So: $h_{23,14,5} (63,455)$
So: 63,455/61 = 1040 so $d_0 = 15$
1040/61 = 17 so $d_1 = 3 \implies d_2 = 3$
so:
$[(23*15) + (14*3) + (5*3) ] \mod 61 = 402$?
So the answer is $402$?
Verified with my T.A. the correct solution. It seems I had some wrong values for some variables.
$63455/61 = 1040 \implies d_0 = 15$
$1040/61 = 17 \implies d_1 = 3$
$17$ is the last $q$ which $\implies d_2 = 17$
$\therefore h_{23,14,5} (63455) = (23*15) + (14*3) + [(5*17) \mod 61] = 411$
So the resulting hash is $411$