문제 : A large number of deletions in a separate chaining hash table can cause the table tone fairly empty, which wastes space.  In this case, we can rehash to a table half as large.  Assume that we rehash ago a larger table when there are twice as many elements as the table size.  How empty should the table be before we rehash to a smaller table?


 Solution This question requires you to choose the load factor, λ, at which one should rehash to a smaller table. Rehashing is an expensive operation, so we our choice should reflect our wish not to rehash too often. Let p be the load factor at which we rehash to a table half as large. If the new table has size N, then it contains 2pN elements, immediatly after a rehashing. This smaller table will require rehashing after either 2N − 2pN insertions or 2pN − pN deletions. If we expect future insertions and deletions to occur with identical frequency a value for p which balances the two can be calculated as follows:


2N −2pN = 2pN −pN

p = 2/3 

If we know that insertions are more frequent than deletions, then we should

choose p to be larger.