Linear Probing

Posted: 20 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

‘Hashing’ is a technique in which a large non-negative integer is mapped with a smaller non-negative integer using a function called ‘hash function’. Hash Table is the table in which we store large numbers corresponding to mapped indices.

While hashing a list of elements, we define ‘Collision’ as a situation when the hash function for a large integer in list returns an index which is already mapped with some other large integer in a list.

‘Linear Probing’ is a collision handling technique in which we find the next vacant place in the hash table for mapping. What we do is that we take the original hash value and successively add 1 in each iteration until an unmapped index is found in the hash table.

Given an array KEYS consisting of N non-negative integers. For each element in a given array, you need to determine the index by which this element is mapped in the hash table if the ‘Linear Probing’ technique is used to handle collision.

The hash function you need to consider is H(X) = X mod N i.e. index = X mod N.

Return an array ‘HASH_TABLE’ of size N in which:

HASH_TABLE[ i ] = KEYS[ j ] where, i = KEYS[ j ] mod N.

In short, an element at index ‘i’ is the element from the given array KEYS which is mapped to that index.

You can refer to the example given below:

alt

The answer for the above example will be [18, 21, 6, 15].

Note:

1. Consider ‘0’ based indexing.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a positive integer ‘N’ representing the size of array KEYS.

The second line of each test case contains ‘N’ space-separated non-negative integers representing elements of the array KEYS.
Output format :
For each test case, return an array 'HASH_TABLE’ of size ‘N’ where HASH_TABLE[ i ] is the element from the given array KEYS which is mapped to the index i.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 500
0 <= KEYS[ i ] <= 10^9

Time limit: 1 sec
Approach 1

The approach is pretty simple. We just need to find the mapping index and if it is occupied, we need to search for the next available index.

 

The algorithm for the same is as follows:

  • Create an array HASH_TABLE of size N.
  • Initialise every value of HASH_TABLE as -1.
  • Loop for each KEY:
    • Initialize HASH = KEY % N
    • If HASH_TABLE[ HASH ] is already occupied, we perform:
      • while(HASH_TABLE[ HASH ] != -1):
        • HASH = ( HASH + 1 ) % N, iterating for valid hash index.
    • Update HASH_TABLE[ HASH ] with KEY.
  • Return HASH_TABLE
     

Let’s take an example of keys = { 91, 28, 46 }.

  • Initialise HASH_TABLE = { -1, -1, -1 }
  • For 91, H(91) = 91 mod 3 i.e. 1.
    • As index 1 is free, HASH_TABLE becomes { -1, 91, -1 }.
       
  • For 28, H(28) = 28 mod 3 i.e. 1.
    • As index 1 is already occupied, we will move to while loop:
      • We use index 2, which is free, HASH_TABLE becomes { -1, 91, 28 }
         
  • For 46, H(46) = 46 mod 3 i.e. 1.
    • As index 1 is occupied, we move to while loop:
    • HASH = (1 + 1) mod 3 i.e. 2. As index 2 is occupied, loop continues.
      • HASH = (2 + 1) mod 3 i.e. 0. Index 0 is free, thus, we will use index 0.

The final HASH_TABLE becomes { 46, 91, 28 }

Try Problem