Register

GO Classes DPP | GATE CS, DA | Data Structure | Collision-Free Hash Parameter

343 views
6 6 votes

For the keys:

$47, 61, 36, 52, 56, 33, 92$

consider the hash function:

$h(k) = ((10k + 4) \bmod c) \bmod 7$

Find the smallest positive integer $c$ such that no collisions occur.

1 Answer

1 1 vote

We are given keys:

$47, 61, 36, 52, 56, 33, 92$

Hash function is:

$h(k) = ((10k + 4) \bmod c) \bmod 7$

There are $7$ keys and $7$ final hash table slots.

So, to have no collision, all $7$ hash values must be different.

For $c < 7$, no collision is impossible because there are fewer than $7$ possible values after $(10k+4) \bmod c$.

Now check values of $c$ from $7$ onward.

For $c = 7$, hash values are:

$5, 5, 0, 6, 4, 5, 0$

There are collisions.

For $c = 8$, hash values are:

$2, 6, 4, 4, 4, 6, 4$

There are collisions.

For $c = 9$, hash values are:

$6, 2, 4, 2, 6, 1, 6$

There are collisions.

For $c = 10$, all values become: $4$

So, there are collisions.

For $c = 11$, hash values are:

$1, 9 \bmod 7, 1, 7 \bmod 7, 3, 4, 0$

This gives repeated values, so there are collisions.

For $c = 12$, hash values are:

$6, 2, 4, 1, 0, 3, 0$

There is a collision at $0$.

Now for $c = 13$:

$47: (10 \times 47 + 4) \bmod 13 = 474 \bmod 13 = 6$

$61: 614 \bmod 13 = 3$

$36: 364 \bmod 13 = 0$

$52: 524 \bmod 13 = 4$

$56: 564 \bmod 13 = 5$

$33: 334 \bmod 13 = 9$, and $9 \bmod 7 = 2$

$92: 924 \bmod 13 = 1$

So final hash values are:

$6, 3, 0, 4, 5, 2, 1$

All are distinct.

Therefore, the smallest value of $c$ with no collisions is: $\boxed{13}$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

5 5 votes
1 1 answer
235
235 views
GO Classes asked Jul 28
235 views
GO Classes DPP | GATE CS, DA | Data Structure | Hash Table
Which of the following statements are true?$\text{S1}$. The worst-case complexity of checking whether an object is present in a hash set is $O(1)$.$\text{S2}$. The worst-...
2 2 votes
1 1 answer
186
186 views
GO Classes asked Jul 16
186 views
GO Classes DPP | GATE CS, DA | Data Structure | Collision-Free Hash Parameter
For the keys : $\text{47, 61, 36, 52, 56, 33, 92}$Suppose the hash function is :$h(k) = ((10k + 4) \bmod c) \bmod 7$where $c$ is a positive integer.What is the smallest v...
10 10 votes
1 1 answer
499
499 views
GO Classes asked Jul 28
499 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Tree
Rebalance the following tree so that it becomes a valid AVL tree:What will be the root after rebalancing?$10$ $12$ $16$ $20$
4 4 votes
1 1 answer
276
276 views
GO Classes asked Jul 28
276 views
GO Classes DPP | GATE CS, DA | Data Structure | Heap Insertion
Suppose vector $A$ is a min-heap:$A = [2, 4, 3, 6, 7, 3, 5, 8, 9]$After calling $\texttt{Push(1)}$, what is the final heap array?$[1, 2, 3, 6, 4, 3, 5, 8, 9, 7]$ $[1, 4, ...