Hash Function : Relative Addressing

h (key) -> Relative Address

These are very simple hashing functions which do not require any space or extra efforts. It works on dense key distribution.

For a business you considered 100 entries of customers hence allocated continuous space to store 100 records. The record for customer id 1 was placed at address 1, for customer id 2 was placed at address 2 and so on. The space with address 101 to 180 is allocated to some other file. Now the business flourishes and there is a need to enter record for customer with customer id 101.  The solution can be generating a relative address. If key = 5 then the relative address can be 205 i.e. we are pinning record at 205 with key value 5. Now if the file grows and limit reached then relocate the entire file to a new continuous location larger than the current space.

Sparse Key Distribution

It means of millions only a fraction is required. Consider designing a hash function for stored roll numbers, which will act as a key to get the address of a particular student’s record stored on the disk. The roll number consists of 9 digits. Hence theoretically we have to make provision for 109 records. The pattern of the roll number is 

Year (2 digit) + Course Code (3 Digit) + [0 – Male | 1 – Female] + Roll Number (3 digit)

1. Out of the 109 values as approximately only 3000 students take admission in a year, hence in next 50 years 3000X50 = 150000 records will be used.
2. As 3 digits are assigned for course code, maximum 999 courses can run in the institute which is too much beyond a possibility (as at present approximately 35 courses are running).
3. If a roll number is assigned to a male candidate 112010040 then there can’t exist a female candidate with roll 112011040.

Hence we have to filter out the key values that will never ever be allocated. The need is to collapse.

Collapse the keys

Which keys will be blank and which will be present is not predictable (consider scenario 3). Hence there is no fixed pattern.