A hash table of length 10 is taken for insertion of the keys with hash function h(key)= key mod 10. If Collision occurs, it is resolved with quadratic probing. The following sequence of keys are inserted:46, 36, 34, 24, 52, 57, 56Which of the following cannot be inserted to the table due to quadratic probing?a)34b)24c)46d)None of theseCorrect answer is option 'D'. Can you explain this answer?

Question

Answer

Hash Table with Quadratic Probing

To understand why option 'D' (None of these) is the correct answer, let's first take a look at how a hash table with quadratic probing works.

Hash Function
The given hash function h(key) = key mod 10 calculates the hash value by taking the remainder of the key divided by 10. This ensures that the hash value falls within the range of 0 to 9.

Collision Resolution with Quadratic Probing
Quadratic probing is a collision resolution technique where, if a collision occurs while inserting a key, the algorithm searches for the next available position by using a quadratic sequence of offsets. The next position is calculated using the formula:
next_position = (current_position + i^2) % table_length

Here, i represents the number of collisions that have occurred, and table_length is the length of the hash table.

Inserting the Keys
Let's go through the given sequence of keys and see how they are inserted into the hash table:

1. Key 46: The hash value is 6 (46 % 10). The position at index 6 is empty, so the key is inserted at this position.

2. Key 36: The hash value is 6 (36 % 10). There is a collision at index 6. Using quadratic probing, the next position to check is (6 + 1^2) % 10 = 7. This position is empty, so the key is inserted at index 7.

3. Key 34: The hash value is 4 (34 % 10). The position at index 4 is empty, so the key is inserted at this position.

4. Key 24: The hash value is 4 (24 % 10). There is a collision at index 4. Using quadratic probing, the next position to check is (4 + 1^2) % 10 = 5. This position is empty, so the key is inserted at index 5.

5. Key 52: The hash value is 2 (52 % 10). The position at index 2 is empty, so the key is inserted at this position.

6. Key 57: The hash value is 7 (57 % 10). There is a collision at index 7. Using quadratic probing, the next position to check is (7 + 1^2) % 10 = 8. This position is empty, so the key is inserted at index 8.

7. Key 56: The hash value is 6 (56 % 10). There is a collision at index 6. Using quadratic probing, the next position to check is (6 + 1^2) % 10 = 7. This position is already occupied by the key 36. The next position to check is (6 + 2^2) % 10 = 0. This position is empty, so the key is inserted at index 0.

Cannot be Inserted due to Quadratic Probing
Considering the given sequence of keys, we can see that all the keys are successfully inserted into the hash table without any issues or collisions that cannot be resolved with quadratic probing. Therefore, the correct answer is option 'D' (None of these).

Top Courses for GATE

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Other Engg Branches

Related Exams

Company