如何散列可变长度字符串

Question

我是 encryption/hashing 的初学者。我想知道如何将可变长度的字符串（可能是 10 或 100 个字母）散列为固定长度的代码，例如128 位二进制，不考虑底层编程语言，同时在 bin 之间实现相对相等的碰撞。

具体如何处理不同输入的输入，使hashcode均匀分布？

Answer 1

有很多不同的方法可以做到这一点。

对于非加密应用程序，通常通过按顺序迭代字符并应用一些操作将新字符的位与累积的哈希位混合来对字符串进行哈希处理。您将如何执行此操作有很多变化。此处显示了一种常见的方法：

unsigned int kSmallPrime = /* some small prime */;
unsigned int kLargePrime = /* some large prime */;

unsigned int result = 0;

for (char ch: string) {
    result = (result * kSmallPrime + ch) % kLargePrime;
}

更复杂的组合步骤可以获得更好的分布。这些方法通常不要求字符串具有任何特定长度并且适用于任何长度的字符串。你得到的位数取决于你使用什么内部存储来混合这些位，尽管不一定有强有力的理论理由（除了经验证据）相信你有一个很好的分布。

对于加密应用程序，字符串哈希函数通常源自块密码。像 Merkle-Damgard 这样的结构可以让你从一个安全的分组密码开始，并产生一个安全的散列函数。他们通过使用安全填充方案（确保不同字符串在填充后最终不同）将字符串填充到块大小的某个倍数来工作，将字符串分成块，并将它们散列在链中。然后最终的输出来自底层分组密码，它自然会输出大量的比特，而nice分布来自底层分组密码的强度，（原则上）应该与随机无区别

如何散列可变长度字符串

How to hash variable-length strings

string

hash

string-hashing