math - 如何将UUID空间划分为N个大小相等的分区？

Question

采用十六进制表示形式的 UUID:'123e4567-e89b-12d3-a456-426655440000'

我有很多这样的 UUID，我想将它们分成 N 个桶，其中 N 是我选择的，我想生成这些桶的边界。

我可以简单地创建 16 个具有这些边界的桶:

00000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000
20000000-0000-0000-0000-000000000000
30000000-0000-0000-0000-000000000000
...
e0000000-0000-0000-0000-000000000000
f0000000-0000-0000-0000-000000000000
ffffffff-ffff-ffff-ffff-ffffffffffff

只需遍历第一个十六进制数字的选项即可。

假设我想要 50 个相同大小的桶(每个桶中包含的 UUID 可能性的数量相等)，或 2000 个桶，或 N 个桶。

如何生成作为 N 函数的边界？

Answer 1

您上面的 UUID 的长度为 32 位十六进制数字。所以这意味着你有 16^32 ≈ 3.4e38 个可能的 UUID。一个简单的解决方案是使用一个大的 int 库(或您自己的方法)将这些非常大的值存储为实际数字。然后，您可以将可能的 UUID 的数量除以 N(将该值称为 k)，得到 0、k、2*k、... (N-1)*k、UMAX 的存储桶边界。

如果 N 不除以可能的 UUID 的数量，就会出现问题。显然，并不是每个桶都有相同数量的 UUID，但在这种情况下，它们甚至不会均匀分布。例如，如果可能的 UUID 数量为 32，而您想要 7 个桶，则 k 将为 4，因此您将拥有大小为 4、4、4、4、4、4 和 8 的桶。这可能不是太理想了。要解决此问题，您可以改为将存储桶边界设为 0、(1*UMAX)/N、(2*UMAX)/N、... ((N-1)*UMAX)/N、UMAX。然后，在上述不方便的情况下，您最终会在 0、4、9、13、18、22、27、32 处得到边界——给出桶大小为 4、5、4、5、4、5、5。

为了使用此方法，您可能需要一个大的 int 库或其他一些方法来存储大整数。相比之下，C++ 中的 long long(在某些实现中)最多只能存储 2^64 ≈ 1.8e19。