Please someone correct me with my the below pseudocode.
a pseudocode for R1Hash(key, a, b, A, B, N) that takes non-negative integers key, a and b where a and b come from to the hashing function used to store indices in B; the arrays A and B of length N and N^2 respectively are also inputs: the function should return an index i where the value key is stored in array A; it should return -1 if the value cannot be found; it should return -2 if there was an error in the data storage, assuming that the hashing function avoids collisions in the hashed values for distinct values.
for each element i of A, the value A[i] is hashed to give an index j of B, and the index i is stored in B[j]. For the hashing function, given constants a>0 and b, for each
i, the value A[i] is hashed by the function (a*A[i] + b) mod N^2, which is equal to the
index of B into which we store i.
A = [7,5,6] B = [-1, 2, -1, -1, 0, -1, -1, -1, -1]
the hash function is (3*A[i] + 1) mod 9. For instance, the value 5 stored at
index 1 in A is hashed to the value (3*5 + 1) mod 9 = 7, and thus the index 1 is stored at
index 7 in array B. In this example there were no collisions in the hashed values since all values in A are distinct. In general, for this setting, for all distinct values x and y assume that we use constants a and b such that the hashed value (a*x + b) mod N^2 is not equal to (a*y + b) mod N^2.
If the array A stores the same integer multiple times, we resolve the collision in the hashed
values through linear probing: to insert a value into B, if there is already a non-negative integer stored at a location j, we loop over the subsequent elements j+1, j+2, etc to find the next element storing the value -1.
I have tried the below pseudocode. please correct me. thanks
1 2 3 4 5 6 7 8 9 10 11
|
Function R1Hash(key, a, b , A, B, N):
return (a* key + b) % N
for 0 <= i < N:
if (A[i] == key):
return A[i]
// not in array
return -1;
if there is error:
return -2
end function
|