• edited by
2,563 views
2 2 votes

WHICH OF THE FOLLOWING IS THE BEST CHOICE AS $m$ IN THE HASH FUNCTION $h(k)=k \mod m$??

  1. $61$
  2. $701$
  3. $81$

answer is given as $701$ but how??

1 Answer

Best answer
15 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
Position:
Show:

Related questions

61 61 votes
4 answers 4 answers
25.3k
25.3k views
Arjun asked Feb 12, 2020
25,272 views
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Ass...
0 0 votes
2 2 answers
1.2k
1.2k views
1 1 vote
1 1 answer
1.8k
1.8k views
MiNiPanda asked Jan 1, 2019
1,827 views
Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in an unsuccessful search is 3, the expected number of probes in successful sear...
11 11 votes
1 1 answer
5.9k
5.9k views
Ayush Upadhyaya asked Sep 22, 2018
5,932 views
Consider an initially empty hash table of length 10. Following are the keys in hash table inserted using mod function h(k)=k mod 10.Slot NumberValue0 1912 333444523664777...