Quadratic Probing in Hashing

Easy
0/40
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
ZSMedia.netSamsung

Problem statement

‘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’ and this smaller integer is used as an index of an array called ‘hash table’.

We define ‘Collision’ as a situation when a large integer is mapped to the index in a hash table that is already mapped with some other integer.

‘Quadratic Probing’ is a collision handling technique in which we take the original hash value and successively add ‘i*i’ in ‘ith’ iteration until an unmapped index is found in the hash table. This technique works as follows:

Let ‘x’  be a larger integer, ‘n’ be the size of the hash table, and ‘h(x) = x mod n’ be a hash function. Then in Quadratic Probing -:

1. If we find that the index h(x), is already mapped to some other integer in the hashtable, then we try for index (h(x) + 1 * 1) mod n. 

2. If the index (h(x) + 1*1) mod n, is also already mapped to some other integer in the hashtable, then we try for index (h(x) + 2 * 2) mod n.

3. If the index (h(x) + 2*2) mod n, is also already mapped to some other integer in the hashtable, then we try for index ‘(h(x) + 3 * 3) mod n. 

4. We repeat this process until an unmapped index is found in the hashtable or index values start repeating.

In Quadratic probing, sometimes, it is possible that we cannot map an integer with any index in the hashtable.

Given an array ‘keys’ consisting of ‘n’ non-negative integers. Let's consider the hash function h(x) = x mod n. Assume that you are traversing the array ‘keys’ from left to right and you need to insert all these keys in the hash table. For each element of the array ‘keys’, your task is to determine the index by which this element is mapped in the hash table if ‘Quadratic Probing’ technique is used to handle the collision. Return an array ‘hashTable’ of size ‘n’ where the element at index ‘i’ is the element from the given array ‘keys’ that is mapped to that index or -1 if no element is mapped to that index.

For Example -:  Consider, array  ‘keys’ = {50, 49, 76, 85, 92, 73, 18},  ‘n’ = 7 and the hash function h(x) = x mod 7. Then -:

1. h(50) = 50 mod 7 = 1, thus it will be mapped to index ‘1’ in the hashtable.

2. h(49) = 49 mod 7 = 0, thus it will be mapped to index ‘0’ in hashtable.

3. h(76) = 76 mod 7 = 6, thus it will be mapped to index ‘6’ in the hashtable.

4. h(85) = 85 mod 7 = 1, thus it should be mapped to index ‘1’ in the hashtable, but index ‘1’is already mapped with 50,  so we try for index (h(85) + 1*1) mod 7 = ‘2’, as index ‘2’ is not mapped previously, thus it will be mapped to index ‘2’ in hashtable’.

5. h(92) = 92 mod 7 = 1,  thus it should be mapped to index ‘1’ in the hashtable, but index ‘1’ is already mapped with 50, so we try for index (h(92) + 1*1) mod 7 = 2,  but index ‘2’ is also occupied so we try for index (h(92) + 2*2) mod 7 = ‘5’, as index ‘5’ is not mapped previously, thus it will be mapped to index ‘5’ in hashtable

6. h(73) = 73 mod 7 = 3,  thus it will be mapped to index ‘3’ in the hashtable.

7. h(18) = 18 mod 7 = 4,  thus it will be mapped to index ‘4’ in the hashtable. 
Thus the resultant array ‘hashTable’ should be {49, 50, 85, 73, 18, 92, 76}.

alt text

Note: 
1. Consider ‘0’ based indexing.
2. Don’t print anything, just return the integer array ‘hashTable’.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

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

The second line of the test case contains ‘n’ space-separated non-negative integers representing elements of the array ‘keys’.
Output format : 
For each test case, return an array ‘hashTable’ of size ‘n’ where the element at index ‘i’ is the element from the given array ‘keys’ that is mapped to that index or -1 is no element is mapped to that index.

Output for each query is printed in a new line.
Constraints: 
1 <= T <= 50
1 <= n <= 100
0 <= keys[i] <= 10^9

Where ‘T’ is the total number of test cases, ‘n’ is the size of the given array ‘keys[i]’ is the elements of the given array.


Time limit: 1 sec
Sample Input 1:
2
7
50 49 76 85 92 73 18
1
5
Sample Output 1:
49 50 85 73 18 92 76
5
Explanation of Sample Input 1:
Test case 1:
See the problem statement for the explanation.    

Test case 2:
Here, ‘keys’ = {5}, ‘n’ = 1 and hash function h(x) = x mod 1.
h(5) = 5 mod 1 = 0,  thus it will be mapped to index 0 in the hashtable.
Therefore, the resultant array ‘hashTable’ = {5}.
Sample Input 2:
2
2
1 2
3
3 6 9
Sample Output 2:
2 1
3 6 -1
Explanation of Sample Input 2:
Test case 1:
Here, ‘keys’ = {1, 2}, ‘n’ = 2 and hash function h(x) = x mod 2.
h(1) = 1 mod 2 = 1, thus it will be mapped to index 1 in the hashtable.
h(2) = 2 mod 2 = 0, thus it will be mapped to index 0 in the hashtable.
Therefore, the resultant array ‘hashTable’ = {2, 1}.

Test case 2:
Here ‘keys’ = {3, 6, 9}, ‘n’ = 3 and hash function h(x) = x mod 3.
h(3) = 3 mod 3 = 0, thus it will be mapped to index 0 in the hashtable.
h(6) = 6 mod 3 = 0, thus it should be mapped with index 0 in the hashtable, but 3 is already mapped with 0,so  it will be mapped with index (h(6) + 1*1) mod 3 = 1 in the hashtable.
h(9) = 9 mod 3 = 0, thus it should be mapped with index 0 in the hashtable, but 3 is already mapped with 0, so we try to map it with index (h(9) + 1*1) mod 3 = 1 in the hashtable, but index 1 is already mapped with 6, so we try to map it with index (h(9) + 2*2) mod 3 = 1 in the hashtable which is the same as the previous value, we can observe after that value starts repeating thus we cannot map 9 with any index.
Therefore, the resultant array ‘hashTable’ = {3, 6, -1}
Hint

Probe at most  ‘n’ times for each element.

Approaches (1)
Brute Force.

For every element in the array ‘keys’, we can observe that the index value will start repeating after ‘n’ probes. Thus we should try only ‘n’ time for one key.

  • Make an integer array ‘hashTable’ of size ‘n’ and fill it completely with -1.
  • Run a loop where ‘i’ ranges from 0 to n-1 and for each ‘i’  we try to find an index by which it should map in the hashtable. This can be done as follows.
    • Calculate the hash value of ‘key[i]’ and store it in integer variable hash. I.e hash:= key[i] mod n.
    • Run a loop where ‘j’ ranges from ‘0’ to ‘n’ and for each ‘j’ check whether the value at index (hash + j*j) mod n,  in array ‘hashTable’ is -1 or not. If it is -1 then assign hashTable[i] := keys[i] and break the loop.
  • Return this integer array ‘hashTable’.
Time Complexity

O(n*n),  Where ‘n’ is the size of the given array ‘keys’.

 

Here, we will have two nested loops, the outermost loop runs ‘n’ times, and in the worst case, the inner loop will also run ‘n’ times.

Space Complexity

O(n), where ‘n’ is the size of the given array ‘keys’.

 

The size of the resultant array ‘hashTable’ will be of order ‘n’.

Code Solution
(100% EXP penalty)
Quadratic Probing in Hashing
Full screen
Console