Hash Function
I need a help to write 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.
I would appreciated it.
I would appreciated it.
a and b come from to the hashing function
is it to, or from?
guessing from.. to makes less sense.
on the surface it sounds like
index = hash(key);
if(a[index].data == key)
return index
else (if some error)
return -2
else
return -1
is it to, or from?
guessing from.. to makes less sense.
on the surface it sounds like
index = hash(key);
if(a[index].data == key)
return index
else (if some error)
return -2
else
return -1
Last edited on
Thanks @jonnin constants a and b for the hashed value (a*x + b) mod N^2 is not equal to (a*y + b) mod N^2.
where did x and y come from, that is new...
maybe post the whole problem /requirement?
mod is a poor way to hash things. It has similar problems to rand(). But mod is implementation, you asked for pseudocode. I am sorely confused, which I am used to at my age, but this is more than usual.
that said do you need math here?
mod is close enough to the remainder in division, and there are some theory / properties of it.
but for x and y both > 2 or so, I believe that y = x+ 1 will not give the same remainder for the same divisor. Or if not +1, not 100% sure of that, some value based off a, eg min(1,a)/2. Those are without mathing at it, if you sit down with the math you can prove out something that will work all the time.
to get you started, if a*x+b and a*y+b give the same mod, then x and y have a relationship with N^2 ... once you get away from the anomaly conditions like N==1 etc.
maybe post the whole problem /requirement?
mod is a poor way to hash things. It has similar problems to rand(). But mod is implementation, you asked for pseudocode. I am sorely confused, which I am used to at my age, but this is more than usual.
that said do you need math here?
mod is close enough to the remainder in division, and there are some theory / properties of it.
but for x and y both > 2 or so, I believe that y = x+ 1 will not give the same remainder for the same divisor. Or if not +1, not 100% sure of that, some value based off a, eg min(1,a)/2. Those are without mathing at it, if you sit down with the math you can prove out something that will work all the time.
to get you started, if a*x+b and a*y+b give the same mod, then x and y have a relationship with N^2 ... once you get away from the anomaly conditions like N==1 etc.
Last edited on
@ jonnin
this is more explanations:
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
this is more explanations:
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
Last edited on
and if chef makes 3 million pizzas, each one takes half as many peppers as onions, how many tomatoes did he use? There is some piece of info in your requirement that you are holding back... which is making it hard to help you.
@ jonnin
sorry for the confusion. I am trying to figure it out this question. the above is the whole scenario. i will appreciated it.
sorry for the confusion. I am trying to figure it out this question. the above is the whole scenario. i will appreciated it.
Last edited on
they give you everything.
you literally just take the data, hash it, and if you hit a used location, find the next unused location and put the data there instead.
it gives you how to resolve collisions, so you don't need to try to solve for x and y, you just need to do what it says.
so..
index = hash(a[something]);
if(b[index] is not used)
b[index] = something; //a's index above
else
bool placed = false;
for(int i = index+1; i < index+N*N; i++)
if(b[index] is not used)
{
b[i%N*N] = something;
placed = true; //did we put it somewhere?
}
if not placed tell user all about it (all locations of B are full).
note that the % on i above is just to cycle through all the locations of b. so if b has 10 elements and you start at 7, but its full... you try 8, 9, 10%10 is 0, 10%11 is 1, ... circles back to the lower cells, see? Make sure you get the math right on these indices, but that is the idea.
I used N*N as size of b but not clear if that is a true thing or not. It is also unclear where 'something' came from (the index from a). Does not matter, but you need to resolve it to write real code.
you literally just take the data, hash it, and if you hit a used location, find the next unused location and put the data there instead.
it gives you how to resolve collisions, so you don't need to try to solve for x and y, you just need to do what it says.
so..
index = hash(a[something]);
if(b[index] is not used)
b[index] = something; //a's index above
else
bool placed = false;
for(int i = index+1; i < index+N*N; i++)
if(b[index] is not used)
{
b[i%N*N] = something;
placed = true; //did we put it somewhere?
}
if not placed tell user all about it (all locations of B are full).
note that the % on i above is just to cycle through all the locations of b. so if b has 10 elements and you start at 7, but its full... you try 8, 9, 10%10 is 0, 10%11 is 1, ... circles back to the lower cells, see? Make sure you get the math right on these indices, but that is the idea.
I used N*N as size of b but not clear if that is a true thing or not. It is also unclear where 'something' came from (the index from a). Does not matter, but you need to resolve it to write real code.
Last edited on
@ jonnin
thanks. what do you mean b[index], a[something]. a and b are constants, you mean that B[j] and A[i]?
thanks. what do you mean b[index], a[something]. a and b are constants, you mean that B[j] and A[i]?
Yes, the arrays. this is why having variables with the same name that differ only in case is bug prone :)
Topic archived. No new replies allowed.