0

我需要生成一个 32 位随机整数，但取决于一些参数。这个想法是为每条消息生成一个唯一的 ID，以通过自己的 P2P 网络发送。要生成它，我想作为参数：我的 IP 和时间戳。我的问题是，如何从这些参数中生成这个 32 位随机整数？

再次感谢！

4

3 回答 3

3

以下是选项列表及其相关问题：

  1. 使用随机数。您将在大约一半的位中发生碰撞（非唯一值）（这是“生日碰撞”）。所以对于 32 位，你会在 2*16 条消息后发生冲突。如果您发送的消息少于 65,000 条，这不是问题，但 65,000 条并不是一个大数字。

  2. 使用某些服务的顺序计数器。这就是 twitter 的雪花所做的（在此处查看另一个答案）。麻烦在于通过网络提供这些。通常在分布式系统中，你给每个代理一组数字（所以 A 可能得到 0-9，B 得到 10-19，等等），他们使用这些数字然后请求一个新块。这减少了网络流量和提供号码的服务的负载。但这很复杂。

  3. 从一些唯一的值生成散列。这听起来很有用，但实际上并不比（1）好，因为你的哈希值会发生冲突（我在下面解释原因）。因此您可以散列 IP 地址和时间戳，但实际上您所做的只是生成 32 位随机数（不同之处在于您可以重现这些值，但无论如何您似乎并不需要该功能），并且因此，在大约 65,000 条消息之后，您将再次发生冲突，这并不多。

  4. 更聪明地生成 id 以保证唯一性。(3) 中的问题是您正在散列超过 32 位，因此您正在压缩信息并获得重叠。相反，您可以显式管理这些位以避免冲突。例如，将每个客户端编号为 16 位（最多允许 65,000 个客户端），然后让每个客户端用户一个 16 位计数器（每个客户端最多允许 65,000 条消息，这是对 (3) 的一个很大改进）。这些不会发生冲突，因为每个都保证是唯一的，但是您的系统中有很多限制并且事情开始变得复杂（需要对客户端进行编号并存储每个客户端的计数器状态）。

  5. 使用更大的领域。如果您使用 64 位 ID，那么您可以只使用随机数，因为每 2**32 条消息就会发生一次冲突，这实际上是永远不会发生的（4,000,000,000 分之一）。或者您可以使用 32 位时间戳加入 ip 地址（32 位）（但要小心 - 这可能意味着每秒来自客户端的消息不超过 1 条）。唯一的缺点是带宽稍大，但在大多数情况下，id 比有效载荷小得多。

就个人而言，我会使用更大的字段和随机数 - 它简单且有效（尽管好的随机数在嵌入式系统中是一个问题）。

最后，如果您需要该值是“真正”随机的（例如，因为 id 用于确定优先级并且您希望事情是公平的），那么您可以采用上述具有确定性值的解决方案之一并重新安排位是伪随机的。例如，反转计数器中的位可能就足够了（首先比较 lsb）。

于 2013-10-25T12:12:04.960 回答
2

我建议使用某种哈希。有许多可能的散列，FNV 散列有多种大小并且速度很快。如果你想要一些加密安全的东西，它会慢很多。您可能需要添加一个计数器：1、2、3、4... 以确保您不会在同一时间戳中获得重复的哈希值。

于 2013-10-25T11:58:41.890 回答
1

您是否尝试过查看 Twitter 的Snowflake？它有一个 Python 包装器。

于 2013-10-25T12:01:35.037 回答