将Int32转换为ushort并再次转换回来

StackOverflow https://stackoverflow.com/questions/123301

  •  02-07-2019
  •  | 
  •  

题

我正在尝试设计一个系统，用于将大于65535的整数值打包到一个ushort中。让我解释一下。

我们有一个系统，它使用SQL Server中的IDENTITY列生成Int32值，并受到生产中客户端API的限制，该API将Int32 ID溢出到ushorts。幸运的是，客户端在任何给定时间只有大约20个具有这些ID的事物实例 - 让我们称之为包 - 它只需要在本地兄弟中使它们独一无二。普遍接受的解决方案是在将它们传输到客户端之前将我们的Int32 ID转换为ushorts（并且我不是指铸造，我的意思是翻译），但是有这种方法的倒钩：

  1. 由于未到期，某些ID低于65535的ID可能在任何时间仍然在给定客户端上。
  2. 我们不能有任何ID冲突 - 也就是说，如果包ID 1进入客户端，这个算法跟踪从Int32中删除65535以在应用于65536时生成ushort的次数也会导致1碰撞。
  3. 我们必须能够在返回时将ushort重建为Int32。

    4. 我们可以解决这个问题的是一个单一的有符号字节字段，它回显给我们并给出了127个值（实际上是117因为我们使用的是0-9用于其他东西）。我将其称为“字节字段”。从现在开始。

    我们讨论了三种不同的翻译例程：

    1. Multiplicative：在字节字段中存储我们从Int32中删除65535以进行ushort的次数。这有如上所述的碰撞问题。
    2. 序列化会话状态：对于每个客户端，根据有关该客户端的事实生成会话ID。然后存储1：1的转换表，从1开始到交付的包数，这样当客户端再次访问我们的服务器时，包的库存可以转换回他们已知的数据库ID。这会产生开销问题，因为我们将序列化的会话状态支持到数据库，我们希望每秒支持数百到数千个事务。
    3. 多种算法方法，其中字节字段是变换算法的ID，它采用Int32并将其转换为ushort。很明显，其中很多都是简单的乘法（为了增加我们可以变换的ID的上限），但有些必须乘以较小的边界（如32768），加上/减去一个数来得到接近a在兄弟姐妹中可以保证唯一的数字。这种方法是处理器密集型的，但应该允许我们在保持可扩展性的同时避免冲突（尽管采用这种方法，我们有一个有限的上限，在ushort问题由于升级而自行消失之前无法达到）。

      4. 所以我的问题是：是否有比上述方法更好的方法，如果没有，我应该在算法（方法＃3）方面寻找什么来在给定数字时生成1-65535之间的数字大于0并且不能是单向散列？

      澄清：它不是ushort上限是最大的问题，它是客户端API使用ushort所以我不能将客户端上的字节字段组合起来以获得更大的值（客户端API是不可升级的，但最终会相不存在）。

有帮助吗？

解决方案

关于方法2：

你的第二种方法几乎就是NAT的工作原理。本地网络上的每个TCP / UDP客户端最多有65535个正在使用的端口（端口0除外）和一个私有IP。路由器只知道一个公共IP。由于两个客户端可能都有源端口300，因此它不能简单地用公共IP替换私有IP，这会导致冲突出现。因此，它取代了IP并且“翻译”了IP。端口（NAT：网络地址翻译）。返回时，它会将端口转换回来，并在转发包之前再次使用私有IP替换公共端口。除此之外你别无所求。然而，路由器将这些信息保存在内存中 - 并且在进行NAT时它们并不会太慢（有数百台计算机的公司有时会访问互联网，而且在大多数情况下减速几乎不会明显）。你说你想要每秒多达一千笔交易 - 但是会有多少客户？因为这主要定义备份映射所需的内存大小。如果没有太多的客户端，你可以在内存中保存带有排序表的映射，在这种情况下，速度将是最小的问题（表变大，服务器内存不足是更大的）。

我有点不清楚你曾经说过

  

幸运的是，客户只有约   20个左右的事情   这些ID - 我们称之为包 -   在任何给定的时间，它只需要   让他们在当地独一无二   兄弟姐妹。

然后你说

  

某些小于65535的ID可能仍然存在   随时在给定的客户端上玩   由于未到期。

我猜，第二个语句可能意味着，如果客户端请求ID 65536，它可能仍然具有低于65535的ID，并且这些ID可以低至（假设）20。这不是客户端进程ID按顺序排列，对吧？所以你不能说，只是因为它现在要求65536，它可能有一些较小的值，但肯定不在1-1000范围内，对吗？它实际上可能会引用20,90,2005和41238并仍然超过65535，这就是你的意思？

我个人喜欢你的第二种方法而不是第三种方法，因为在任何情况下都更容易避免碰撞，并且将数字翻译回来是一个简单，简单的操作。虽然我怀疑你的第三种方法可以长期运作。好的，你可能有一个字节来存储你减去2 ^ 16数字的频率。但是，您只能将117 * 2 ^ 16减去最大数字。如果数字超过这个数字你会怎么做？使用不同的算法，不减去，但做什么？划分？转移位？在这种情况下，您将失去粒度，这意味着此算法不能再 任何可能的数字（它将进行大跳转）。如果只是简单地在32位上应用魔术翻译函数从其中生成16位（+一个额外字节）然后再将其转换回来，那么猜测这个世界中的每种压缩方法都会使用它，因为它可以，没有无论32位数是多少，总是将其压缩到24位（16位+一个字节）。这将是魔术。不可能将32位打包成24位，并且还将所有逻辑打包成如何将其转换回它。您将需要一些外部存储空间，这将使我们回到您的第二种方法。这是唯一可行的方法，它适用于32位数范围内的每个数字。

其他提示

我可以想到其他一些选择：

数据库中是否全局少于65536个条目？如果是这样，那么您可以维护一个与会话状态无关的映射表，但它是应用程序的持久性部分。

索引中的大多数条目是否少于50,000个？如果是这种情况，您可以直接映射这些值，并使用与会话相关联的映射表示剩余的值。

如果持久存在此类会话数据是一个问题，并且客户端数量相当小，则可以启用客户端/会话关联，并将映射维护到服务器本地。

如果它不是Web应用程序，您可以在客户端上维护地图。

我没有看到任何可以避免碰撞的算法方法 - 我怀疑你总是想出一个会碰撞的例子。

多少“更多”比65535你需要吗？你总是可以从你的“字节字段”中添加一些位。作为ID的高位。只需2位就可以达到262,143,3位可以得到524,287。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top