1回答

liuyubobobo

2023-07-28

选择一个合适的素数 B，配合合适的 M，通常是可以的。

为了验证这一点，我们可以简单做一个实验，下面的程序我遍历 1970 年至2050 年所有的年份，遍历每一个年份的 12 个月，遍历每个月的 31 天（简单起见，我不区分每个月份天数的不同），使用 B = 911382323 和 M = 972663749（这个取值是比较常用的对字符串做 rk 哈希的取值）。

（我现在的环境写 C++ 比较方便，我使用的是 C++）

你可以实际测试一下，对于这 80 年间的每一天的数据，这样计算出的哈希值，是没有重复的（第二部分不会输出任何数据）

#include <iostream>
#include <map>

using namespace std;

int main() {
    
    long long B = 911382323, M = 972663749;
    map<long long, int> f;
    long long sz = 0;
    
    for(int year = 1970; year <= 2050; year ++)
        for(int month = 1; month <= 12; month ++)
            for(int day = 1; day <= 31; day ++){
                long long hash = 0;
                hash = (hash * B + year) % M;
                hash = (hash * B + month) % M;
                hash = (hash * B + day) % M;
                f[hash] ++;
                sz ++;
            }
    
    // 输出数据总量
    cout << sz << endl;
    
    // 输出重复哈希值的数据
    for(auto it = f.begin(); it != f.end(); it ++)
        if(it->second > 1)
            cout << it->first << " " << it->second << endl;
    
    return 0;
}

==========

另外我在这里回答过，Java 中默认的字符串哈希，B 就是 31（虽然 ascii 字符的最大值是超过 31 的，也就是 B 比数字的取值范围小也是 ok 的。这里的核心不是取值范围和 B 的关系，而是获得的哈希值的冲突率）：https://class.imooc.com/course/qadetail/312846

==========

但如果你一定要找更“紧密”的表示，就需要具体问题具体分析了。

日期是一个很容易获得更紧密的哈希表示的数据类型。这是因为我们其实可以很容易的计算出某一个日期距离 0000 年 1 月 1 日有多少天的。（我们可以计算出 0000 年到这个日期之前一年一共有多少个闰年，就能计算出一共有多少天，然后计算出这个日期是当前年份的第几天，相加即可）。我们可以使用这个数据作为哈希值（或者和某一个 M 取模获得哈希值。）

==========

如果你需要更加“好”或者更加“安全”的哈希值，那么如何设计哈希函数本身就是一个“学科”了，而不是一个简单的找 B 和 M 的过程。

比如大名鼎鼎的 MD5 或者 SHA，都是哈希生成算法。对这类算法更具体的讨论通常都在密码学领域。

对于现代密码学涉及的这些哈希函数的设计，这本免费的“小书”可能是一个不错的入门（manning 出版社的书我都比较喜欢：）：https://www.manning.com/books/exploring-modern-cryptography

继续加油！：） 

3