Rehashing

Rehashing is a method for #202112122035 to resize the original Table into a bigger one, usually twice as large. This is usually used alongside with #202112131222

Details

Rehashing the Table will build a new Table that is twice as larger than the original Table with a new 202112122038. All the elements will be recomputed to a new hash value and inserted into the new Table.

Analysis

• Will result in \(O(N)\)

Implementation

There are different strategies to rehash:

• Rehash as soon as the Table reach half full
• Rehash only when insertion fails
• Rehash when reaches certain 202112141222

HashTable Rehash(HashTable H) {
  int OldSize;
  Cell *OldCells;

  OldCells = H->TheCells;
  OldSize = H->TableSize;

  // Get a new, empty table
  H = InitializeTable(2 * OldSize);

  // Scan through old table, reinserting into new
  for (int i = 0; i < OldSize; i++)
    if (OldCells[i].Info == Legitimate)
      Insert(OldCells[i].Element, H);

  free(OldCells);

  return H;
}