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

Question

我正在寻找一个散列函数，它将大量输入数据以良好的一致性划分为少量分区（比如 100 或 256）。这意味着我预计会有很多碰撞，但我并不关心碰撞。

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

CRC算法是首先想到的想法之一。 CRC8已被提出，但没有提供关于其一致性的信息；对于 CRC32，显然一致性不是很好。

有简单或通用哈希函数的列表，但没有说明它们的一致性。

Bob Jenkins 有一篇关于返回 32 位值的哈希函数的详尽文章。我想对于均匀分布的 32 位值，所有可能的 8 位子集也应该均匀分布，因此有很好的候选者。但是，如果有更简单的 8 位算法，将 32 位值减少到 8 位值可能是矫枉过正？

score 0 · Accepted Answer

我发现 sdbm 算法显示出良好的一致性，非常简单：

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

1 回答 1