Rehashing

rehashing

1. Rehashing by k.Sivapriya I.msc(IT)

2. How Hashing For insertion of a key(k)- value (v) pair into a hash map two step are required: 1.K is converted into a small integer using a hash function. The hash code is used to find an index and the entire linked list at that searched for the K already. If found it is value is updated and if not, the K-and V pair is stored as a new node in the list.

3. C omplexity and Load F actor The first step time taken depends on the K and the hash function. For example if the key is a string “abcd”, then its hash function may depend on the length of the string. But for very large values of n, the length of the entries into the map, map length of the keys is almost negligible in comparison to n so hash computation can be considered to take place in constant time , i.e., o(1)

4. Cont… The second step, traversal of the list of K-V pairs present at that index needs to be done. For this, the worst case may be that all the n entries are at the same index. So, time complexity would be o(n). But enough research has been done to make hash functions uniformly distribute the keys in the array so this almost never happens.

5. Cont… So, on an average, if there are n entries and b is the size of the size of the array there would be n\b is called the load factor that represent the load that is there on our map. This load factor needs to be kept low, so that number of entries at one index is less and so is the complexity almost constant, i.e., o(1).

6. R ehashing As the name suggests, rehashing means hashing again. Basically when the load factor increases to more than its pre defined value the complexity increases. So to overcome this the size of the array is increased and all the values are hashed again ad stored in the new double sized array to maintain a low load factor and low complexity.

7. Cont… 6 15 24 13 Open addressing hash table with linear Probing with input 13,15,6,24 1 2 3 4 5 6 6 15 23 24 13 1 2 3 4 5 6 Open addressing hash table with linear Probing After 23 is inserted

8. Cont… 6 23 24 13 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Open addressing hash table after rehashing

9. Why R ehashing Rehashing is done because whenever key value pair are inserted into the map, the load factor increases which implies that the time complexity also increases as explained above. The might not give the required time complexity of o(1). Rehash must be done increasing the size of the bucket array so as to reduce the load factor and the time complexity.

10. How Rehashing is done? For each addition of a way entry to the map, check the load factor. If it is greater than its pre-defined value, then rehash. For rehash, make a new array of double the previous size and make it the new bucket array. Then traverse to each element in the old bucket array and call the insert() for each so as to insert it into the new larger bucket array.

11. Thank you