3

只是为了思考练习，如何为给定类的每个实例强制执行属性的唯一性？

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

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

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

  • 随着实例数量的增加，拥有 ArrayList 或其他容器似乎不切实际。
  • 在类级别增加数字计数器似乎是一种最简单的方法，但 id 必须始终遵循 last-used-id。
  • 强制使用哈希或非数字 id 可能会有问题。
  • 并发性可能值得关注。如果两个实例有可能同时获得一个 id，那么应该防止这种情况发生。

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

4

3 回答 3

4

如果您关心性能，这里是唯一 id 生成的线程安全、快速（无锁）和无冲突版本

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

        public Test() {
            id = lastId.incrementAndGet();
        }
...
于 2013-03-04T05:16:43.583 回答
3

只需使用UUIDJava 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());

或者更简单地使用类compareTo()中的方法UUID......

boolean collision = testObject2.id.compareTo(testObject1.id) == 0 ? true : false;

0 表示ids 相同。+1 和 -1 当它们不相等时。

优点：普遍独特（可以是基于时间的，随机的），因此应该处理线程问题（有人应该确认这一点......这是基于我所知道的最好的）。更多信息在这里和这里。

要使其成为线程安全的，请参阅 SO is java.util.UUID thread safe？

缺点：将需要更改所检查类的结构，即id必须在类本身的源中添加该字段。这可能方便也可能不方便。

于 2013-03-04T05:25:40.317 回答
2

UUID 是一个很好的解决方案，但是后端使用 UUID.randomUUID() 方法：

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

所以这很慢：线程在每个 id 生成操作中锁定一个监视器对象。

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

在下面的解决方案中，只有质数生成是同步的。同步在 volatile int 上，因此速度快且线程安全。有一组素数，在一次迭代中会生成许多 id。

固定数量的线程

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

我你知道有多少线程将使用 ID 生成，然后你可以生成带有值的 ID

Id = I mod X + n*X

其中 X 是线程数，I 是线程数，N 是一个局部变量，每次 Id 生成都会递增。这个解决方案的代码确实很简单，但它必须与hole program基础设施集成。

从素数生成的 ID

这个想法是生成 ids 作为素数的因子 id = p_1^f1 * p_2^f2 * p_2^f3 * ... * p_n^fn

我们在每个线程中使用不同的素数来在每个线程中生成不同的 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 集。

要让线程保存 Id 的生成，只需使用 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/

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))
}
于 2013-06-23T12:47:28.537 回答