hashing table table figure continuing the insertion of into the table in figure nexte displaces table table figure continuing the insertion of into the table in figure nexta displaces table table figure completing the insertion of into the table in figure miraculously (?) finds an empty position in table would try to go back into table position displacing which was placed there at the start this would get us to figure so now would try its alternate in table (location and then displace awhich would displace bwhich would displace dwhich would displace cwhich would displace fwhich would displace ewhich would now displace from position at this pointg would be in cycle the central issue then concerns questions such as what is the probability of there being cycle that prevents the insertion from completingand what is the expected number of displacements required for successful insertionfortunatelyif the table' load factor is below an analysis shows that the probability of cycle is very lowthat the expected number of displacements is small constantand that it is extremely unlikely that successful insertion would require more than (log ndisplacements as suchwe can simply rebuild the tables with new hash functions after certain number of displacements are