Question

One way to decrease the table’s load factor is to make it bigger; that is, we create a new table with more buckets and then transfer the items from the old table to the new one. Sketch pseudocode for this operation. Assume we have an existing array B of m buckets, and we are transferring its contents to a new array B′ of m′ > m buckets. Please specify which value, m or m′, is used by your toIndex() function.

Answer 1

PseudoCode:
    1. Create a new array B' of bigger size m'
    2. For element e in array B =>
        a. Calculate index i = e % length of B' = e % m
        b. make B'[i] = e
    3. Replace the reference to old table by pointing to B'
           
           
We need to use m' in rehashing, as that is the new table size, and that will determine on which index a particular entry will be put.. 

So if Original array had size 13, and value 39 was going into index 0.. then now, may be with size 23, it will go to index 16. So rehashing should be done on the basis of new size.