edited by
2,075 views

1 Answer

Best answer
15 votes
15 votes

A good hash function satisfies (approximately) the assumption of simple uniform hashing : each key is equally likely to hash to any of the $m$ slots, independently of where any other key has hashed to.

Coming to the Hash function, $h(k) = k \,\,mod(m)$, we usually avoid certain values of $m$. For example, $m$ should not be a power of $2$, since if $m$ = $2^p$, then $h(k)$ is just the $p$ lowest-order bits of $k$. Unless we know that all low-order $p-bit$ patterns are equally likely, we are better off designing the hash function to depend on all the bits of the key.
A prime not too close to an exact power of 2 is often a good choice for $m$.

We could choose $m = 701$ because it is a prime and not near any power of 2.

$81$ Not  a Prime. $61$ is near $2^6$

selected by

Related questions

0 votes
0 votes
1 answer
1
tishhaagrawal asked Dec 16, 2023
354 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
3 votes
3 votes
2 answers
4
ben10 asked Sep 15, 2018
1,313 views