REHASHING

 Rehashing is a technique used in hash tables to resize the hash table when the load factor exceeds a certain threshold. The load factor is the ratio of the number of keys stored in the hash table to the size of the hash table.

When the load factor exceeds the threshold, rehashing is performed to create a larger hash table and reinsert all the keys. The steps for rehashing are as follows:

1. Allocate a new hash table with a larger size than the current hash table.
2. For each key in the current hash table, compute its hash value using the new size of the hash table, and insert it into the new hash table.
3. Free the memory used by the current hash table.
4. Set the current hash table to be the new hash table.

Rehashing is necessary to maintain the performance of a hash table over time. When the load factor is too high, the probability of collisions increases, which can slow down the retrieval of keys from the hash table. By increasing the size of the hash table, the load factor can be reduced, which in turn reduces the probability of collisions and improves performance.

However, rehashing can also be an expensive operation, since it requires iterating over all the keys in the hash table and inserting them into a new hash table. To minimize the frequency of rehashing and its cost, it is important to choose an appropriate initial size for the hash table and an appropriate load factor threshold for triggering rehashing. The choice of hash function can also impact the frequency of collisions and the need for rehashing.

Suppose you have a hash table with 10 slots, and you are using linear probing to resolve collisions. The load factor (i.e., the number of keys divided by the number of slots) has reached 0.8, so you decide to rehash.

You choose to double the size of the hash table to 20 slots, and you allocate a new hash table with this size. Then, you iterate over all the keys in the old hash table and insert them into the new hash table based on their new hash values. Finally, you free the memory used by the old hash table and set the new hash table to be the current hash table.

After rehashing, the load factor has been reduced to 0.4, which should improve the performance of the hash table by reducing the number of collisions.😐😐😐😐😐😐

HAIL HYDRA

Rehashing

Rehashing is a collision resolution technique.

Rehashing is a technique in which the table is resized, i.e., the size of table is doubled by creating a new table. It is preferable that the total size of table is a prime number. There are situations in which the rehashing is required.

•  When table is completely full

•  With quadratic probing when the table is filled half.

•  When insertions fail due to overflow.

In such situations, we have to transfer entries from old table to the new table by re computing their positions using hash functions.

Consider we have to insert the elements 37, 90, 55, 22, 17, 49, and 87. the table size is 10 and will use hash function:

H(key) = key mod tablesize

37 % 10 = 7

90 % 10= 0

55 % 10 = 5

22 % 10 = 2

17 % 10 = 7

49 % 10 = 9

Now this table is almost full and if we try to insert more elements collisions will occur and eventually further insertions will fail. Hence we will rehash by doubling the table size. The old table size is 10 then we should double this size for new table, that becomes 20. But 20 is not a prime number, we will prefer to make the table size as 23. And new hash function will be

H(key) = key mod 23 

37 % 23 = 14 

90 % 23 = 21 

55 % 23 = 9 

22 % 23 = 22 

17 % 23 = 17 

49 % 23 = 3 

87 % 23 = 18

Now the hash table is sufficiently large to accommodate new insertions.