for separate chaining the built-in class java util hashmapwhich imple ments the map adtuses the threshold as default maximum load factor and rehashes any time the load factor exceeds this (or an optional user-set load factorthe choice of is fine for separate chaining (which is the likely implementation in java util hashmap)butas we explore in exercise - some open addressing schemes can start to fail when > 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 (nwith separate chainingas gets very close to the probability of collision also approaches which adds overhead to our operationssince we must revert to linear-time list-based methods in buckets that have collisions of coursein the worst casea poor hash function could map every entry to the same bucketwhich would result in linear-time performance for all map operationsbut this is unlikely 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 can finish thuskeeping the load factor below certain threshold is vital for open ad dressing schemes and is also of concern with the separate chaining method if the load factor of hash table goes significantly above the specified thresholdthen it is common to require that the table be resized (to regain the specified load factorand all the objects inserted into this new table when rehashing to new tableit is good requirement for the new array' size to be at least double the previous size once we have allocated this new bucket arraywe must define new hash function to go with itpossibly computing new parameters we then reinsert every entry from the old array into the new array using this new hash function in our im plementation of hash table with linear probing given in code fragments rehashing is used to keep the load factor less than or equal to even with periodic rehashinga hash table is an efficient means of implementing map 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 (see section each rehashing will generally scatter the entries throughout the new bucket array applicationcounting word frequencies as miniature case study of using hash tableconsider the problem of counting the number of occurrences of different words in documentwhich arisesfor