There is something wrong with my hash function
I am trying to implement a spatial hash and am using the hash function from Optimized Spatial Hashing to detect collisions of deformable objects , hash(x, y, z) = (x p1 xor y p2 xor z p3) mod n
where n is the number of buckets in the hash table.
My code for hash function:
int SpatialHash::hash(int x, int y, int z)
{
return (((x * P1) ^ (y * P2) ^ (z * P3)) % TABLE_SIZE);
}
s defines:
#define P1 73856093
#define P2 19349663
#define P3 83492791
#define TABLE_SIZE 2000
I just tried to iterate over the list of elements and when I tried to put the top 1, -1, 0 in the table, it gave me an index of -196. Have I messed up my hash function somewhere?
source to share
Negative modulo a negative number. For example:
-7 % 3 = -1
Something like that:
int positiveModulo(int number, int modulo)
{
int result = number % mudulo;
if (result < 0)
result += modulo;
return result;
}
Or, to avoid branches:
int positiveModulo(int number, int modulo)
{
int result = number % mudulo;
result += modulo;
result %= modulo;
return result;
}
This will give you:
positiveModulo(-7, 3) = 2
source to share
This is actually a funny question, because the sign of the result of a modulo operation is what language and mathematicians are talking about.
In fact, in ISO C ++, the sign of a modulus operation with a negative operand is implementation-defined. Smart languages have mod
, as well rem
, to catch both cases. Have a look at the wikipedia page and their table of programming languages.
It's funny how it split almost 50:50.
Now the solution to your problem: just add a positive modular operation. The simplest solution would be to use abs(...) % N
like (-a) mod N + a mod N = 0
.
source to share
#include <iostream>
#include <vector>
using namespace std;
#define P1 73856093
#define P2 19349663
#define P3 83492791
#define TABLE_SIZE 2000
int positive_mod(int i, int n)
{
/* constexpr */ int shift = 64*sizeof i - 1;
int m = i%n;
return m+ (m>>shift & n);
}
int hasha(int x, int y, int z)
{
return positive_mod(((x * P1) ^ (y * P2) ^ (z * P3)) ,TABLE_SIZE);
}
int main(int argc, char **argv)
{
int ret = hasha(1,-1,0);
cout << ret << endl;
}
source to share