对于未知输入具有良好一致性的哈希函数

Question

我正在寻找一个可以对大量输入进行分区的哈希函数 数据对于少量分区（例如 100 或 256）。这意味着我预计会发生很多碰撞，但我并不关心碰撞。

输入数据事先未知。我期望字符串具有一定的长度 可能在 6 到 100 字节之间。字符串的分布可能非常糟糕 （例如，很大一部分充满空格或仅包含数字）。

CRC 算法是最先浮现在脑海中的想法之一。 CRC8 已被提议，但没有提供有关其的信息 均匀性；对于 CRC32 显然一致性不太好。

有简单或通用 哈希函数， 但没有透露它们的一致性。

Bob Jenkins 有一篇关于返回 a 的哈希函数的完整文章 32 位值。我想对于均匀分布的 32 位值 所有可能的 8 位子集也应该均匀分布，所以有 是很好的候选人。但也许将 32 位值减少到 8 位值是否有更简单的 8 位算法？

Answer 1

我发现 sdbm 算法表现出良好的一致性，而且非常简单：

        h := 0.
        forEach ch in str {
            h := (h * 65599) + ch;
        }