Lecture 21.
Today we looked at a mathematical
analysis of some open addressing probing strategies. We analysed an ideal
uniform strategy that provides a hypothetical model of the behaviour of double
hashing, but is not mathematically precise. Nevertheless empirical evidence
shows that double hashing performs in much the same way as ideal uniform
hashing. We also looked at quadratic probing and saw that it can be implemented
without repeated use of the mod function, as long as the load factor was kept
to under 0.5. Our text looks at a slightly different version of quadratic
probing, that is in fact an extension of the version that we saw in class.
Our textbook provides a table
(see figure 10,4) of probing values for various load factors. These results are
quite illuminating and show that for a load factor of 0.5 or less all three
probing schemes behave more or less in the same way.
Posted: Fri - March 2, 2007 at 10:27 AM