c++ - 我的哈希函数有问题吗

Question

我正在尝试实现空间散列，并使用来自 Optimized Spatial Hashing for Collision Detection of Deformable Objects 的散列函数, hash(x, y, z) = (x p1 xor y p2 xor z p3) mod n 其中 n 是哈希表中桶的数量。

我的散列函数代码是:

int SpatialHash::hash(int x, int y, int z)
{
    return (((x * P1) ^ (y * P2) ^ (z * P3)) % TABLE_SIZE);
}

定义:

#define P1 73856093
#define P2 19349663
#define P3 83492791
#define TABLE_SIZE 2000

我只是尝试遍历元素列表，当我尝试将顶点 1、-1、0 放入表中时，它给了我一个索引 -196。我的哈希函数是否搞砸了？

Answer 1

负数的模是负数。例如:

-7 % 3 = -1

什么想要这样的东西:

int positiveModulo(int number, int modulo)
{
    int result = number % mudulo;
    if (result < 0)
        result += modulo;
    return result;
}

或者避免分支:

int positiveModulo(int number, int modulo)
{
    int result = number % mudulo;
    result += modulo;
    result %= modulo;
    return result;
}

这会给你:

positiveModulo(-7, 3) = 2