3.7 Hash Table Restructuring

• When a hash table has a large number of entries (ie., let us say n $\geq$ 2m in open hash table or n $\geq$ 0.9m in closed hash table), the average time for operations can become quite substantial. In such cases, one idea is to simply create a new hash table with more number of buckets (say twice or any appropriate large number).
• In such a case, the currently existing elements will have to be inserted into the new table. This may call for
  • rehashing of all these key values
  • transferring all the records
  This effort will be less than it took to insert them into the original table.
• Subsequent dictionary operations will be more efficient and can more than make up for the overhead in creating the larger table.