chap searching if and are largethen this is approximately ( / ) the expected number of probes is one plus the sum over > of the probability of collisionswhich is approximately ( / ) /( ai= the cost for successful search (or deletionhas the same cost as originally inserting that record howeverthe expected value for the insertion cost depends on the value of not at the time of deletionbut rather at the time of the original insertion we can derive an estimate of this cost (essentially an average over all the insertion costsby integrating from to the current value of ayielding result of dx loge - - it is important to realize that these equations represent the expected cost for operations using the unrealistic assumption that the probe sequence is based on random permutation of the slots in the hash table (thus avoiding all expense resulting from clusteringthusthese costs are lower-bound estimates in the average case the true average cost under linear probing is ( /( ) for insertions or unsuccessful searches and ( /( )for deletions or successful searches proofs for these results can be found in the references cited in section figure shows the graphs of these four equations to help you visualize the expected performance of hashing based on the load factor the two solid lines show the costs in the case of "randomprobe sequence for ( insertion or unsuccessful search and ( deletion or successful search as expectedthe cost for insertion or unsuccessful search grows fasterbecause these operations typically search further down the probe sequence the two dashed lines show equivalent costs for linear probing as expectedthe cost of linear probing grows faster than the cost for "randomprobing from figure we see that the cost for hashing when the table is not too full is typically close to one record access this is extraordinarily efficientmuch better than binary search which requires log record accesses as increasesso does the expected cost for small values of athe expected cost is low it remains below two until the hash table is about half full when the table is nearly emptyadding new record to the table does not increase the cost of future search operations by much howeverthe additional search cost caused by each additional insertion increases rapidly once the table becomes half full based on this analysisthe rule of thumb is to design hashing system so that the hash table never gets above half