hash table implementations
Pseudo-random Probing?
What does this question mean, and how do I solve it?
Consider the following “random” permutation of the numbers 1 to 6:
2, 4, 6, 1, 3, 5.
Now, consider using this permutation for an implementation of pseudo-random probing on
a hash table of size seven. Will this permutation solve the problem of primary clustering?
What does this say about selecting a permutation for use when implementing pseudo-random
probing?
Hi Ryan,
I’m working on Professor Stewart’s assignment, too. We aren’t supposed to discuss the homework problems, but I can tell you about how pseudo-random probing works in general.
You have some hashing function h(k) which will return a value between 0 and n-1. If you try to insert your key into that index of the hash table, but you find that it’s already occupied, you pick a different key according to the permutation.
Primary clustering occurs when a hashing function by nature creates clusters of filled entries in the hash table. The truth is, this table is WAY too small for the effects of primary clustering to really be apparent, but we’re going to pretend like it’s not.
http://en.wikipedia.org/wiki/Primary_clustering
The way you decide the next slot, if the first slot you tried was occupied, is that you add on the permutation’s image of 1 and reduce mod n. If that doesn’t work, add the permutation’s image of 2 and reduce mod n, and so on.
After that it’s up to you; I can’t help you any more than to give you an idea of how probing works. Good luck.
Google I/O 2010 – Appstats – instrumentation for App Engine