如何将UUIDspace分成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。

Answer 2

如果 N 是 2 的幂，那么解决方案很明显：您可以在位边界上拆分问题中的 16 个存储桶。

如果 N 不是 2 的幂，则桶在数学上不能完全大小相等，所以问题就变成了你愿意以效率的名义容忍多大程度的不平等.

只要N<2^24左右，最简单的就是将UUID根据前32位分配到N个桶中，每个桶大小为2^32/N。对于大多数应用程序来说，这应该足够快且足够相等，如果 N 需要大于允许的值，您可以轻松地将位加倍，但代价很小。

如何将UUIDspace分成N个大小相等的分区？

How to partition UUID space into N equal-size partitions?

math

uuid

hex

partitioning