A) Discuss the random probe technique for handling collisions in detail. Your di

Question

A) Discuss the random probe technique for handling collisions in detail. Your discussion must include but is not limited to a) insertion, b) how do I know when I have found a spot to insert, c) deletion, e) searches where the key is found, f) searchers where the key is not found, g) reclaiming space, and h) listing the keys in sorted order, making sure you do not visit the same place twice. You will need to discuss the desirable properties of the random number generator but do not discuss a method to implement the generator. A) Discuss the random probe technique for handling collisions in detail. Your discussion must include but is not limited to a) insertion, b) how do I know when I have found a spot to insert, c) deletion, e) searches where the key is found, f) searchers where the key is not found, g) reclaiming space, and h) listing the keys in sorted order, making sure you do not visit the same place twice. You will need to discuss the desirable properties of the random number generator but do not discuss a method to implement the generator. A) Discuss the random probe technique for handling collisions in detail. Your discussion must include but is not limited to a) insertion, b) how do I know when I have found a spot to insert, c) deletion, e) searches where the key is found, f) searchers where the key is not found, g) reclaiming space, and h) listing the keys in sorted order, making sure you do not visit the same place twice. You will need to discuss the desirable properties of the random number generator but do not discuss a method to implement the generator.

Explanation / Answer

The ideal probe function would select the next position on the probe sequence at random from among the unvisited slots; that is, the probe sequence should be a random permutation of the hash table positions. Unfortunately, we cannot actually select the next position in the probe sequence at random, because we would not be able to duplicate this same probe sequence when searching for the key. However, we can do something similar called pseudo-random probing. In pseudo-random probing, the i th slot in the probe sequence is (h(K)+ri)modM where ri is the i th value in a random permutation of the numbers from 1 to M1. All inserts and searches must use the same sequence of random numbers. The probe function would be p(K,i)=Permutation[i] where Permutation is an array of length M that stores a value of 0 in position Permutation[0], and stores a random permutation of the values from 1 to M1 in slots 1 to M1.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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