hash tables at load factor of / successful search takes comparisons and an unsuccessful search takes at load factor of / the numbers are and at higher load factors the numbers become very large the moralas you can seeis that the load factor must be kept under / and preferably under / on the other handthe lower the load factorthe more memory is needed for given amount of data the optimum load factor in particular situation depends on the trade-off between memory efficiencywhich decreases with lower load factorsand speedwhich increases quadratic probing and double hashing quadratic probing and double hashing share their performance equations these equations indicate modest superiority over linear probing for successful searchthe formula (again from knuthis -log ( -loadfactorloadfactor for an unsuccessful search it is ( -loadfactorfigure shows graphs of these formulas at load factor of successful and unsuccessful searches both require an average of two probes at / load factorthe numbers are and and at they're and thussomewhat higher load factors can be tolerated for quadratic probing and double hashing than for linear probing separate chaining the efficiency analysis for separate chaining is differentand generally easierthan for open addressing we want to know how long it takes to search for or insert an item into separatechaining hash table we'll assume that the most time-consuming part of these operations is comparing the search key of the item with the keys of other items in the list we'll also assume that the time required to hash to the appropriate list and to determine when the end of list has been reached is equivalent to one key comparison thusall operations require +ncomps timewhere ncomps is the number of key comparisons let' say that the hash table consists of arraysize elementseach of which holds listand that data items have been inserted in the table thenon the averageeach list will hold divided by arraysize itemsaveragelistlength arraysize