在类中强制实现唯一标识符

Question

仅作为思维练习，如何对给定类的每个实例强制执行属性的唯一性?

这里的唯一性可以定义为在单个JVM和单个用户会话中。

这是在Java级别上进行的，与数据库无关，主要目的是验证是否发生了冲突。

第一个明显的步骤是在类级别拥有一个静态属性。

• 使用ArrayList或其他容器似乎不实用，因为实例数量增加。
• 在类级别上递增数字计数器似乎是最简单的方法，但ID必须始终遵循最后使用的ID。
• 强制使用哈希或非数字ID可能会有问题。
• 并发可能是一个问题。如果两个实例同时获得ID，则应将其防止。

应该如何解决这个问题？已经存在哪些解决方案/方法？

- James P.

---

如果不明确“独特性”的范围，这个问题是难以回答的，这也是我怀疑有人投票要关闭的原因。请定义您在时间和空间上所指的“独特性”。即，在单个JVM调用中是否唯一，在整个时间和空间中是否唯一，或者介于两者之间。 - Jim Garrison

感谢 @JimGarrison 的要求澄清。这里的唯一性是指没有两个相同的值。问题涉及到数值和非数值的情况。这发生在同一个 JVM 内，用户会话期间（持续时间未定义，但假设是典型情况），无论是桌面应用程序还是网站上。直觉告诉我们，较大的范围可以通过重用“局部”方法来实现，因此这是问题的重点。 - James P.

Answer 1

如果您关心性能，以下是一个线程安全、快速（无锁）和不冲突的唯一标识生成版本。

    public class Test {
        private static AtomicInteger lastId = new AtomicInteger();
        private int id;

        public Test() {
            id = lastId.incrementAndGet();
        }
...

- Evgeniy Dorofeev

---

如果不了解楼主对“独特性”的定义，这就没有意义，而楼主到目前为止还没有提供。 - Jim Garrison

@JimGarrison 独特性指没有两个值相同。问题涉及数值和非数值类型。将其添加到上面的问题中。 - James P.

在什么上下文中没有两个值是相同的？单个JVM？集群？所有JVMs永远都是如此吗？ - Jim Garrison

@JimGarrison 在上面回复了 :) - James P.

Answer 2

只需在Java中使用UUID类http://docs.oracle.com/javase/6/docs/api/java/util/UUID.html。 在检查的类中创建一个UUID类型的字段，并在构造函数中初始化此字段。

public class Test  {
   public UUID id;
   public Test() {
      id = UUID.randomUUID();
   }
}

当需要进行碰撞检测时，只需像这样比较对象UUID的字符串表示即可...

Test testObject1 = new Test();
Test testObject2 = new Test();
boolean collision = testObject1.id.toString().equals(testObject2.id.toString());

或者更简单地使用UUID类中的compareTo()方法... boolean collision = testObject2.id.compareTo(testObject1.id) == 0 ? true : false; 0表示id相同，+1和-1表示不相等。

优点：通用唯一标识符（可以基于时间、随机）因此应该能够解决线程问题（某人应该确认这一点...这是我所知道的最好的知识）。更多信息可以在这里和这里找到。

要使其线程安全，请参阅SO上的这个问题：is java.util.UUID thread safe? 缺点：需要更改要检查的类的结构，即必须在类本身的源代码中添加id字段。可能方便，也可能不方便。

- vijay

---

为什么要浪费时间转换成字符串表示？UUID实现了equals()和Comparable<UUID>。 - Jim Garrison

@vijay 谢谢您添加了一个用于验证碰撞的语句 :) - James P.

我引用了一个不同的SO问题，回答了那个确切的问题。请检查更新的答案... - vijay

@DenisTulskiy 嗯...我看到了但是我还不确定这个equals到底是指不同 UUID 对象所持有的实际唯一 ID 还是不同 UUID 对象引用本身。我认为它是针对 UUID 引用的。我可能是错的。 - vijay

@vijay 我认为UUID是不可变的。除非我错了，这意味着你可以毫无问题地使用equals方法。 - James P.

Answer 3

UUID是一个不错的解决方案，但在后端使用方法是UUID.randomUUID()。

synchronized public void SecureRandom.nextBytes(byte[] bytes) 

这样做很慢：每次id生成操作都需要锁定一个单一的监视器对象。

AtomicInteger更好，因为它在CAS操作中循环。但是，对于每个id生成操作，必须执行同步操作。

在下面的解决方案中，仅同步素数生成。同步是在易失性整数上进行的，因此速度快且线程安全。有了一组素数，可以在迭代中生成许多id。

固定数量的线程

编辑：固定线程数的解决方案

如果您事先知道将使用多少个线程来生成Id，则可以使用值生成ID

Id = I mod X + n*X

使用质数生成的ID

生成ID的方法是将质数作为因子相乘，其中X是线程数，I是线程号，N是一个本地变量，每次生成ID时会被递增。

这个解决方案的代码非常简单，但必须与整个程序架构集成。

我们在每个线程中使用不同的质数来生成不同的ID集合。

假设我们使用质数(2,3,5)，那么生成的序列将是:

2, 2^2, 2^3, 2^4, 2^5,..., 2^64

当我们发现会产生溢出时，我们将因子滚动到下一个质数位置：

3, 2*3 , 2^2*3, 2^3*3, 2^4*3, 2^5*3,..., 2^62*3

并且接下来

3^2, 2*3^2 , 2^2*3^2, .....

生成类

编辑：必须使用AtomicInteger进行初次生成以确保正确性

每个IdFactorialGenerator类的实例将生成不同的id集合。

为了线程安全地生成Ids，只需使用ThreadLocal来设置每个线程的实例即可。仅在质数生成期间实现同步。

package eu.pmsoft.sam.idgenerator;

public class IdFactorialGenerator {
    private static AtomicInteger nextPrimeNumber = 0;

    private int usedSlots;
    private int[] primes = new int[64];
    private int[] factors = new int[64];
    private long id;
    public IdFactorialGenerator(){
        usedSlots = 1;
        primes[0] = Sieve$.MODULE$.primeNumber(nextPrimeNumber.getAndAdd(1));
        factors[0] = 1;
        id = 1;
    }

    public long nextId(){
        for (int factorToUpdate = 0; factorToUpdate < 64; factorToUpdate++) {
            if(factorToUpdate == usedSlots) {
                factors[factorToUpdate] = 1;
                primes[factorToUpdate] = Sieve$.MODULE$.primeNumber(nextPrimeNumber.getAndAdd(1));
                usedSlots++;
            }
            int primeToExtend = primes[factorToUpdate];
            if( primeToExtend < Long.MAX_VALUE / id) {
                // id * primeToExtend < Long.MAX_VALUE
                factors[factorToUpdate] = factors[factorToUpdate]*primeToExtend;
                id = id*primeToExtend;
                return id;
            } else {
                factors[factorToUpdate] = 1;
                id = 1;
                for (int i = 0; i < usedSlots; i++) {
                    id = id*factors[i];
                }
            }
        }
        throw new IllegalStateException("I can not generate more ids");
    }
}

为了获得素数，我使用了在问题7中提供的Scala实现：http://pavelfatin.com/scala-for-project-euler/。请注意保留HTML标签。

object Sieve {

  def primeNumber(position: Int): Int = ps(position)

  private lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
    ps.takeWhile(j => j * j <= i).forall(i % _ > 0))
}

- EIIPII

---

谢谢。为了防止您的网站不可用，我们已经添加了您的代码。 - James P.