1

我需要为满足以下要求的 Java 应用程序生成唯一编号 -

  1. 9位十六进制
  2. 每天大约产生 600,000 个数字
  3. 这些号码必须在至少 7 天内保持唯一；如果他们重复超过 7 天，这不是问题。
  4. 在峰值负载期间，需要在大约 15 秒内每秒生成大约 800 个唯一号码。

不成功的解决方案 -

    public static String getUniqueId() {
        String uniqueTime = Long.toHexString(System.nanoTime());
        String uniqueId = uniqueTime.substring(uniqueTime.length() - 9);

        return uniqueId;
    }

使用 nanoTime 生成一个 12 位的十六进制数。我截断了左边的 3 个字符。nanoTime 有助于处理峰值负载。

我认为这是不正确的，可能会导致重复。

谁能提供一个好的快速算法吗？

4

7 回答 7

3

如果只使用一个线程来生成数字：

long nextId = counter % MAX_VALUE;
counter++;
return convertToHex(nextId);

如果有多个线程：

long nextId = atomicLongCounter.getAndIncrement() % MAX_VALUE;
return convertToHex(nextId);

注意：考虑到@Gumbo 的计算，它需要 313 年才能达到最大值，所以你甚至可以放弃模数。

于 2012-05-27T15:18:05.147 回答
2

只使用UUID怎么样？它们在这种情况下非常有用。可用的 Java 实现。

于 2012-05-27T16:22:51.093 回答
1

简短的回答：加密。由于加密是可逆的，因此您可以保证输入是唯一的，而不是输出是唯一的。使用 36 位块密码（36 位 = 9 个十六进制数字）并加密数字 0、1、2、3、4...

您可以在空闲时间预先生成任意数量的数据并存储它们。

大多数常见的块密码不是 36 位（DES 是 64 位），但Hasty Pudding Cypher有一个 36 位变体，或者您可以使用像 RC4 这样的快速流密码或eSTREAM密码之一。

ETA：流密码需要为每个数字重新输入密钥，因此对于您的目的来说可能太慢了。重新设置密钥也会影响唯一性，因为只有在使用相同的密钥时才能保证唯一性。

于 2012-05-27T16:29:12.180 回答
0

AtomicLong.incrementAndGet()应该做的伎俩。

如果您需要在 JVM 实例之间持久化它，您可能需要分配一个范围，将该范围的最大值存储在数据库或其他事务存储中，并确保在接近AtomicLong(加上适当的锁定以确保您不会超出该范围。

但是，如果您只需要一次运行中的唯一数字，AtomicLong.incrementAndGet那么它很简单并且保证在它包裹到 -1 之前是唯一的，这 1）在您的有生之年不会发生，并且 2）很容易检查。

于 2012-05-28T00:28:38.977 回答
0

- 并发数生成的另一种可能性

您最多可以有 10 个单独的线程/进程/机器生成保证不会发生冲突的数字。

只需使用顺序计数器生成一个整数

start one of them at 0, use increments of 10
start the next at 1, increments of 10
start the next at 2, increments of 10

即使上述其中之一最终承担了全部负载，它也可以持续 7 天而不会溢出 9 位数字，因为在 9 位数字还不够之前，您的序列中有大约 1 亿个，而您每天只能产生 1 百万个。

这里的好处是线程/进程/机器没有共享。

顺便说一句-您可以直接以 16 为基数执行此操作-只需使用 16 的增量而不是 10。或以 5 为基数，以 5 为增量等...

于 2012-05-27T15:58:00.913 回答
0

部分出于娱乐目的，请允许我还从您提供的规范中提出另一种可能性。您还可以找到一种伪随机数生成算法，该算法从已知种子开始，在实践中不会为您每周需要生成的数字数量产生重复。

例如，以下基于XORShift 生成器，将生成 600000*7 个无重复的随机 9 位数字：

        long seed = 1;
        for (long i = 1; i <= 600000*7; i++) {
            long x = seed++;
            for (int n = 0; n < 3; n++) {
                x ^= (x << 21);
                x ^= (x >>> 35);
                x ^= (x << 4);
            }
          x &= 0xfffffffffL;

          // "x" is now the next unique, random-looking number in the sequence
        }

这种方法的优点是除了计数器之外不需要存储来确定到目前为止已经生成了哪些数字。

缺点是每周都以完全相同的顺序重新开始。当然，如果您突然需要增加分配号码的数量，您可能需要找到另一个序列。

无论如何，我想我会把它混在一起，以防万一它有用。

于 2012-05-27T16:49:05.663 回答
0

如果您不需要数字“看起来随机”，那么您可以按照其他人的建议使用计数器。

我猜您正在寻找复杂事物的原因是因为您希望数字“看起来很随机”。在这种情况下，您可以执行以下操作：

  • 使用 SecureRandom 的实例来分配您的号码
  • 在内存中保留映射到其分配时间的“当前分配”数字的映射（我认为存储在 ConcurrentHashMap 中的这些数据的 600K 数字将是几十兆字节的数据，所以今天没什么大不了的标准）
  • 每次您需要分配一个新数字时，只需通过您的 SecureRandom 实例生成 9 个随机十六进制数字（要求它用 5 个随机字节填充数组，然后丢弃 4 个位将为您提供 9 个十六进制数字的随机数据）
  • 检查您的新号码是否已经在分配号码的地图中。如果是这样，只需循环并生成一个新数字，直到您获得一个唯一的数字 - 实际上，对于您提到的数量，这只会发生每周 100 次左右，因此尽管您确实需要考虑，但不会对性能产生影响为了它;
  • 定期扫描您的分配号码地图并清除已分配超过 7 天的号码，以便它们可以重新使用。

对于现实生活中的应用程序，您还需要考虑持久性：每次分配一个数字时，您都需要将其持久化到数据库中，然后再将其返回给客户端，以便在服务器崩溃时可以恢复状态. 同样，您的清除操作将在从内存映射中删除之前从数据库中删除分配。

于 2012-05-27T16:17:33.600 回答