hash tables most of the probing techniques can benefit from table size that is prime number to determine the actual size of the new tablewe can first double the original size and then search for the first prime number greater than depending on the application and the type of probing usedyou may be able to simply double the size and add one note that by adding onethe resulting size will be an odd numberwhich results in fewer divisors for the given table size efficiency analysis the ultimate goal of hashing is to provide direct access to data items based on the search keys in the hash table butas we've seencollisions routinely occur due to multiple keys mapping to the same table entry the efficiency of the hash operations depends on the hash functionthe size of the tableand the type of probe used to resolve collisions the insertion and deletion operations both require search to locate the slot into which new key can be inserted or the slot containing the key to be deleted once the slot has been locatedthe insertion and deletion operations are simple and only require constant time the time required to perform the search is the main contributor to the overall time of the three hash table operationssearchinginsertionsand deletions to evaluate the search performed in hashingassume there are elements currently stored in the table of size in the best casewhich only requires constant timethe key maps directly to the table entry containing the target and no collision occurs when collision occurshowevera probe is required to find the target key in the worst casethe probe has to visit every entry in the tablewhich requires (mtime from this analysisit appears as if hashing is no better than basic linear searchwhich also requires linear time the differencehoweveris that hashing is very efficient in the average case the average case assumes the keys are uniformly distributed throughout the table it depends on the average probe length and the average probe length depends on the load factor given the load factor donald knuthauthor of the definitive book series on data structures and algorithmsthe art of computer programmingderived equations for the average probe length the times depend on the type of probe used in the search and whether the search was successful when using linear probethe average number of comparisons required to locate key in the hash table for successful search is ( ) and for an unsuccessful search ( awhen using quadratic probe or double hashingthe average number of comparisons required to locate key for successful search is