Suppose you have a simple hashing system for storing integers that just uses a c

Question

Suppose you have a simple hashing system for storing integers that just uses a compression function to determine the array slot to use and uses linear probing for collision resolution. _____________ collision(s) occur if the size of the array is 20 and the following sequence of integers is added:

5      10 15 20 25

Each time the chosen array slot is already occupied should be counted as a collision; in other words, multiple collisions can occur when adding a single element due to collisions happening while linear probing. Your answer should be a number.

Explanation / Answer

Given array of size 20 , means we will map the elemenents from 0 to 19

Compression function is A Mdulus function that will map integers into 0 to N-1 , Our hash function will be

h(x) = Integer % 20

Initially Hash Table is Empty , Start with first element

1. 5 i.e 5%20   = 5
At location 5 we have 5 Now and there is no collision yet

2. 10%20 = 0
At location 0 we have 10 Now and there is no collision yet

3. . 15%20 = 5
At location 5 we have 5 already present so there is collision, Place 15 to next location i.e 6 , So At location 6 we have 15 and till now we have encountered one collision.

4. . 20%20 = 0
At location 0 we have 10 already present so there is collision, Place 20 to next location i.e 1 , So At location 1 we have 20 and till now we have encountered two collision

5. . 25%20 = 5
At location 5 we have 5 already present so there is collision, Place 25 to next location i.e 6 , again at position 6 we have 15 so again collision . Place 25 to location 7 , So At location 7 we have 25 and till now we have encountered total 4 colliision .

How we got 4 collision : 25 got collided twice , 15 collided once , 20 collided once.

Linear Probing check the next available slot and add the elements into it.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.