时间戳

首页 > 解决方案 > C++ hashCode - 处理大数（+ mod 操作）

c++ - C++ hashCode - 处理大数（+ mod 操作）

问题描述

我正在开发一个项目，该项目涉及对Java hashCode()散列函数进行编程，
公式.

输入字符串（即“A 添加触发单元 C”）是随机生成的并存储在 .txt 文件中。此外，如果结果哈希不在范围内（0 < hash < N），则需要调整=> hash % N）。

我在使用 hashCode() 算法时遇到了问题，因为字符串中只有一个字符的结果太大（即 1.408 * 10^30）而无法存储在常规变量中。我尝试使用一些允许您存储非常大的数字的库，但如果哈希超过 N 参数，它们都不允许您执行 mod 操作。

请，您会为我推荐什么解决方案，以便我可以存储这些非常长的数字+对它们使用 mod 操作。

谢谢

标签： c++hashcodemod

解决方案

你不能在 C++ 中存储这么大的数字，但只要 N 不是一个巨大的数字，它当然是可能的。诀窍是在% N遍历字符串时执行，因此您的号码永远不会溢出。

你可以使用这个方法——https://math.stackexchange.com/a/453108找到(A^B)%N，即(31^200)%N。

//This is the algorithm mentioned in the above link
const size_t N = 1e9 + 7;
size_t bigPower(size_t x, size_t p) {
    size_t ans = 1;

    while(p > 0){
        if(p % 2 == 1)
            ans = (ans*x)%N;
        x = (x*x)%N;
        p /= 2;
    }

return ans;
}

然后，按照公式不应该溢出数字。

size_t hashCode(const string& s) {
    size_t result = 0;
    for(size_t i = 0; i< s.size(); i++) {
        result += (s[i] * bigPower(31, s.size()-1-i))%N;
        result %= N;
    }

    return result;
}

更新 我发现 Java hashCode 实际上可以溢出并返回负散列码 - HashCode 给出负值。因此，如果您希望您的 hashCode 表现得像 Java，您不妨允许溢出。

//This might produce the exact same hashCode as Java.
int hashCode(const string& s) {
    int result = 0;
    for(int i = 0; i< s.size(); i++) {
        int m = 1;
        for(int j=0; j<s.size()-1-i; j++) {
            m *= 31;
        }
        result += (s[i] * m);
    }

    return result;
}

推荐阅读