load factorsrehashingand efficiency in the hash table schemes described thus farit is important that the load factorl /nbe kept below with separate chainingas gets very close to the probability of collision greatly increaseswhich adds overhead to our operationssince we must revert to linear-time list-based methods in buckets that have collisions experiments and average-case analyses suggest that we should maintain for hash tables with separate chaining with open addressingon the other handas the load factor grows beyond and starts approaching clusters of entries in the bucket array start to grow as well these clusters cause the probing strategies to "bounce aroundthe bucket array for considerable amount of time before they find an empty slot in exercise - we explore the degradation of quadratic probing when > experiments suggest that we should maintain for an open addressing scheme with linear probingand perhaps only bit higher for other open addressing schemes (for examplepython' implementation of open addressing enforces that / if an insertion causes the load factor of hash table to go above the specified thresholdthen it is common to resize the table (to regain the specified load factorand to reinsert all objects into this new table although we need not define new hash code for each objectwe do need to reapply new compression function that takes into consideration the size of the new table each rehashing will generally scatter the items throughout the new bucket array when rehashing to new tableit is good requirement for the new array' size to be at least double the previous size indeedif we always double the size of the table with each rehashing operationthen we can amortize the cost of rehashing all the entries in the table against the time used to insert them in the first place (as with dynamic arrayssee section efficiency of hash tables although the details of the average-case analysis of hashing are beyond the scope of this bookits probabilistic basis is quite intuitive if our hash function is goodthen we expect the entries to be uniformly distributed in the cells of the bucket array thusto store entriesthe expected number of keys in bucket would be / which is ( if is (nthe costs associated with periodic rehashingto resize table after occasional insertions or deletions can be accounted for separatelyleading to an additional ( amortized cost for setitem and getitem in the worst casea poor hash function could map every item to the same bucket this would result in linear-time performance for the core map operations with separate chainingor with any open addressing model in which the secondary sequence of probes depends only on the hash code summary of these costs is given in table