Hash with Chaining Problems

Question

I ran into an example in Computer Science Course.

suppose we use Hashing with chanining and use table of size m. the hash function map record with key k into k mod m slot. if we know the record keys is subset of {$i^2 | 1 \leq i \leq 100 $}, for which value of m cost of search is lower in worst case?

a) 11

b) 7

c) 9

d) 12

Answer 1

We consider four different hashtables with sizes $m=7,9,11$ and $m=12$ and start with

the case $m=7$:

We consider the multiset

\begin{align*} \{i^2 \mod m \left|1\leq i \leq 100\right.\} \end{align*} and count the multiplicities of occurrences of the hash keys $\{0,\ldots,m-1\}$. The multiplicities give the chain length per hash key of the hash table. This number minus one is the number of collisions per hash key.

\begin{array}{lccccccc} \text{key}&0&1&2&3&4&5&6\\ \text{nr. occ}&14&\color{red}{\mathbf{29}}&28&0&\color{red}{\mathbf{29}}&0&0\\ \end{array}

We observe: Using $m=7$ we have in the worst case a chain of length $29$, which means $28$ collisions.

Let's have a look at the table of all sizes of $m$ with the hash key and the number of occurrences, i.e. the chain length.

\begin{array}{rlrrrrrrrrrrrr} m&\text{hash}&0&1&2&3&4&5&6&7&8&9&10&11\\ \hline 7&\text{nr. occ}&14&\color{red}{\mathbf{29}}&28&0&\color{red}{\mathbf{29}}&0&0\\ 9&\text{nr. occ}&\color{red}{\mathbf{33}}&23&0&0&22&0&0&22&0\\ 11&\text{nr. occ}&9&\color{blue}{\mathbf{19}}&0&18&18&18&0&0&0&18&0\\ 12&\text{nr. occ}&16&33&0&0&\color{red}{\mathbf{34}}&0&0&0&0&17&0&0\\ \end{array}

We tabulate the cost of search in the worst case for the different $m$ values

\begin{array}{rc} m&max\\ \hline 7&29\\ 9&33\\ 11&\color{blue}{\mathbf{19}}\\ 12&34\\ \end{array}

We conclude the lowest cost in the worst case is $m=11$ with a chain length of $19$.

Answer 2

I am not entirely sure what the assumptions on $m$ are -- clearly if $m>100^2$, then any search is going to be cost 1, so probably the values up to $100^2$ are to be studied or better yet, only a minimal one is to be found.

In the latter case, the respective answers are 19, 29, 23 and 17.

In the former case, say, with 11, you can show that $m=128$ doesn't work since you have the 13 squares of everything which is $4\bmod(8)$, 4 12 20 28 36 44 52 60 68 76 84 92 100, mapping to $16$. But everything past $128$ works, i.e. you don't need to go up to $m=10^4$.

Similar arguments/remarks work for the rest. The question is, however, what the CS course was about. If its asking about worst-case (as as opposed to average-case) cost of explicit numbers for hash tables, I'd assume something below the level of CLRS (few intro courses aren't...) If that is correct, I'd assume that nobody wanted you to use case-by-case + big guns elementary number theory analysis -- rather they wanted you to write 15 lines of C++ or 10 lines of Python and find out.