Register

Hashing

1,165 views
2 2 votes
Given the input sequence {11, 33, 43, 99, 34, 79, 19} and hash table of size 10 with the hash function h(k) = k mod 10. If hash table uses quadratic probing, the number of collisions occurred while mapping the given sequence is ______.

1 Answer

Best answer
5 5 votes

1) 11mod10=1

2) 33 mod 10=3

3)43mod10=3 , collision occurs

therefore next place is obtained bu quadratic probing as (43+12)mod 10=4

4)99mod10=9

5)34mod10=4 so collision occurs ,

next place =(34+12)mod10=5

6)79mod10=9 collision

next place= (79+12)mod10=0

7)19mod10=9 collision ,

next place =(19+12)mod10=0 collision , next place= (19+22)mod10=3 collision, next place = (19+32)mod10=8

therefore total 6  collisions are there

• selected by
Voting & Accepting an answer helps improve the community
← Previous · Loop Invariant -CLRNext → · algorithm
← Previous in category · Loop Invariant -CLRNext in category → · algorithm
Position:
Show:

Related questions

62 62 votes
5 answers 5 answers
25.5k
25.5k views
Arjun asked Feb 12, 2020
25,478 views
GATE CSE 2020 | Question: 23
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...
3 3 votes
1 1 answer
186
186 views
GO Classes asked Aug 31
186 views
GO Classes DPP | GATE CS, DA | Algorithms | Hashing
An initially empty hash table $\text{HT}$ has length $11$.The hash function is:$H(key)=key \bmod 7$Collisions are resolved using linear probing.The following keys are ins...
1 1 vote
2 2 answers
741
741 views
vinayak_chandra asked Jan 31, 2025
741 views
Hashing (Collisions resolved by linear probing)
A hash table can store a maximum of ten records. Currently there are records in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, wit...
2 2 votes
1 1 answer
500
500 views
Ayush_Pal asked Sep 7, 2024
500 views
Hashing: Quadratic Probing; Ace Academy Test Series