hash - 将 UUID 数字流随机分为 10 个桶

Question

我正在处理 UUIDs 的流。我的最终目标是将这些数字随机分为 10 个桶，即将它们中的每一个放入 10 个桶中的任何一个，这样在任何给定时刻，如果我处理过 N 个 UUID 数字，该流的每个桶中应该有大约 N/10 个数字。我想出了以下想法:

• 获取与给定 UUID 等效的 16 字节数组(因为每个 UUID 有 128 位)
• 将 16 个字节的无符号值相加，得到一个正整数 sum。
• 获取模 100 求和值。
• 模值将属于 10 个存储桶中的任意一个，具体取决于其值:存储桶 1 : [0, 9]、存储桶 2 : [10, 19]、.....、存储桶 10 : [90, 99 ].

我对接近 200,000 个 UUID 进行了此实验(并使用 8 个不同的流进行)，并观察到每个存储桶的数量接近总数的 10%(范围在 9.85% 到 10.15% 之间)，这似乎相当随机。我的问题是:

1. 如果我不只是取 16 个字节的总和，而是取 UUID 的哈希值(比如说 MD5 哈希)，然后执行以下步骤，我有更好的机会随机划分它们吗？一个更普遍的问题是，是否有一种数学方法可以可视化散列在这些情况下可以提供帮助？
2. 如果您同意第 (1) 点，那么应该采用什么好的哈希算法来实现同样的目的。
3. 如果您不同意第 (1) 点，那么您能否建议我一个更好的算法来实现同样的目的。

Answer 1

事实上，你所描述的算法在技术上确实实现了一个哈希函数，因为它将 UUID 的空间映射到一组固定大小的集合，即从 1 到 10 的数字集合。

您的问题 1. 那么就变成了您的算法定义的哈希函数的输出如何均匀分布的问题。

很难先验地判断您的哈希函数是否比 MD5 等更好地分配输出，因为这取决于输入流的分布。然而，语言库中自带的哈希函数(例如 MD5)通常会实现启发式算法，以避免明显不幸的分布发生冲突。一个具体的例子:假设你的输入流只包含集合中的 UUID

00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
.
.
.
10000000-0000-0000-0000-000000000000

然后所有这些都将被映射到存储桶 1，而 MD5 可能会打乱内容。

您可以使用 chi-squared test衡量哈希函数对输入样本的处理效果。