如何在Java中生成一个由5个字符组成的唯一字母数字值？

Question

我参与一个银行项目，他们的要求是为每个交易生成唯一的交易参考号。UTR的格式如下：

<银行代码><YYDDD><5位数字SequenceId>。

这个5位数字的SequenceId也可以是字母数字混合的。每天的交易量可能会达到10-20万笔。

如果我使用Oracle序列，那么我只能有10K个值。

我尝试使用SecureRandom生成器并生成了200K个5位长度的字符串，但它生成了大约30个重复字符串。

下面是我使用的代码片段：

int leftLimit = 48;
int rightLimit = 122;
int i1=0;
Random random = new SecureRandom();
while (i1<200000) {
    String generatedString = random.ints(leftLimit, rightLimit+1)
                                   .filter(i -> (i<=57||i>=65) && ( i<=90|| i>=97))
                                   .limit(5)
                                   .collect(StringBuilder::new,
                                            StringBuilder::appendCodePoint,
                                            StringBuilder::append)
                                   .toString();
    System.out.println(generatedString);
    i1++;
}

- user5740099

---

这个5位序列号可以包含数字和字母。这意味着每个位置可以是0-9或A-Z，是否允许小写字母a-z并且被视为与大写字母A-Z不同？还有其他字符允许吗？ 如果只允许使用0-9和A-Z，则将拥有36个不同的字符，这意味着它是一个基于36进制的数字。在36进制中有5个“数字”，您可以有36^5 = 60466176种不同的值。FYI：Java的Integer类可以格式化基于36进制的数字。 - Andreas

使用36进制计数，而不是随机数。 - tgdavies

嗯...结果是可以预料的。这是生日问题的一个变体。总共，您有36^5个可能的密码。在没有重复的情况下提取100k个密码的概率为((36!) / (36! - 100000)!) / ((36^5)^100000) ~ 1.70 * 10^-36，也就是非常不可能。 - Turing85

为什么在需要一个序列时要使用随机数？ - Joakim Danielson

是的，但序列不是最简单的确保每个值都唯一的方法吗？除非你有其他要求。 - Joakim Danielson

Answer 1

如果你想要一个伪随机序列，我建议你使用自定义的Feistel实现。Feistel被设计成一种可逆机制，因此您可以通过重新应用它来解码Feistel，这意味着i == feistel(feistel(i))，如果您从1到X，您将恰好获得1到X之间的所有数字，因此不会发生冲突。

基本上，您有36个字符可供使用。因此，您有60,466,176个可能的值，但您只想要其中的200,000个。但实际上，我们不关心您想要多少个，因为Feistel确保没有冲突。

你会注意到60,466,176在二进制中是0b11100110101010010000000000，这是一个26位的数字。26对于代码来说不太友好，所以我们将自定义Feistel映射器包装到24位中。由于Feistel需要将数字分成两个相等的部分，因此每个部分将为12位。这仅用于解释您将在下面的代码中看到的值，这是12而不是16，如果您查看其他实现，则会看到。另外，0xFFF是12位掩码。

现在是算法本身：

  static int feistel24bits(int value) {
    int l1 = (value >> 12) & 0xFFF;
    int r1 = value & 0xFFF;
    for (int i = 0; i < 3; i++) {
      int key = (int)((((1366 * r1 + 150889) % 714025) / 714025d) * 0xFFF);
      int l2 = r1;
      int r2 = l1 ^ key;
      l1 = l2;
      r1 = r2;
    }
    return (r1 << 12) | l1;
  } 

基本上，这意味着如果您将介于0和16777215（= 2 ²⁴ -1）之间的任何数字输入此算法，您将获得一个唯一的伪随机数，该数字在以36为底的情况下可以适合5个字符字符串中。

那么如何使其全部工作？嗯，非常简单：

String nextId() {
  int sequence = (retrieveSequence() + 1) & 0xFFFFFF; // bound to 24 bits
  int nextId = feistel24bits(sequence);
  storeSequence(sequence);
  return intIdToString(nextId);
}
static String intIdToString(int id) {
  String str = Integer.toString(id, 36);
  while(str.length() < 5) { str = "0" + str; }
  return str;
}

这是我使用的完整代码。

- Olivier Grégoire

Answer 2

似乎有两种方法：

1. 将唯一值存储在所需大小的Set中，并在使用后删除其元素。

class UniqueIdGenerator {
    private static final int CODE_LENGTH = 5;
    private static final int RANGE = (int) Math.pow(36, CODE_LENGTH); 
    private final Random random = new SecureRandom();
    private final int initSize;
    private final Set<String> memo = new HashSet<>();
    
    public UniqueIdGenerator(int size) {
        this.initSize = size;
        generate();
    }
    
    private void generate() {
        int dups = 0;
        while (memo.size() < initSize) {
            String code = Formatter.padZeros(Integer.toString(random.nextInt(RANGE), 36), CODE_LENGTH);
            
            if (memo.contains(code)) {
                dups++;
            } else {
                memo.add(code);
            }
        }
        System.out.println("Duplicates occurred: " + dups);
    }
    
    public String getNext() {
        String code = memo.iterator().next();
        memo.remove(code);
        return code;
    }   
}

2. 使用具有随机起始值和随机增量的序列。

class RandomSequencer {
    private static final int CODE_LENGTH = 5;
    private Random random = new SecureRandom();
    private int start = random.nextInt(100_000);
    
    public String getNext() {
        String code = Formatter.padZeros(Integer.toString(start, 36), CODE_LENGTH);
        start += random.nextInt(300) + 1;
        
        return code;
    }
}

更新 在编程中，零填充可以通过多种方式实现：

class Formatter {
    private static String[] pads = {"", "0", "00", "000", "0000"};
    public static String padZeros(String str, int maxLength) {
        if (str.length() >= maxLength) {
            return str;
        }
        return pads[maxLength - str.length()] + str;
    }

    private static final String ZEROS = "0000";
    public static String padZeros2(String str, int maxLength) {
        if (str.length() >= maxLength) {
            return str;
        }
        return ZEROS.substring(0, maxLength - str.length()) + str;
    }

    public static String padZeros3(String str, int maxLength) {
        if (str.length() >= maxLength) {
            return str;
        }
        return String.format("%1$" + maxLength + "s", str).replace(" ", "0");
    }
}

- Nowhere Man

---

我可以看到在循环中对字符串进行修改。这非常糟糕。 - oleg.cherednik

@oleg.cherednik 超高效的填充零不是这个答案的重点。 - Nowhere Man

无论如何，它都不应该出现。 - oleg.cherednik

Answer 3

既然你在问题中提到了Oracle，那么你考虑一下PL/SQL解决方案吗？

1. 创建一个数据库表来保存你的序列ID。

create table UTR (
  BANK_CODE     number(4)
 ,TXN_DATE_STR  char(5)
 ,SEQUENCE_ID   char(5)
 ,USED_FLAG     char(1)
 ,constraint USED_FLAG_VALID check (USED_FLAG in ('N', 'Y'))
 ,constraint UTR_PK primary key (BANK_CODE, TXN_DATE_STR, SEQUENCE_ID)
)

创建一个PL/SQL过程来填充表格。

create or replace procedure POPULATE_UTR
is
  L_COUNT     number(6);
  L_BANK      number(4);
  L_DATE_STR  char(5);
  L_SEQUENCE  varchar2(5);
begin
  L_BANK := 3210;
  select to_char(sysdate, 'YYDDD')
    into L_DATE_STR
    from DUAL;
  L_COUNT := 0;
  while L_COUNT < 200000 loop
    L_SEQUENCE := '';
    for K in 1..5 loop
      L_SEQUENCE := L_SEQUENCE || substr('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
                                         mod(abs(dbms_random.random), 62) + 1,
                                         1);
    end loop;
    begin
      insert into UTR values (L_BANK, L_DATE_STR, L_SEQUENCE, 'N');
      L_COUNT := L_COUNT + 1;
    exception
      when dup_val_on_index then
        null; -- ignore.
    end;
  end loop;
end;

请注意，生成序列 ID 的代码来自标题为“在 Oracle 中生成大写和小写字母数字随机字符串”的 this SO 问题。

另外，获取日期字符串的代码来自标题为“Oracle 年的朱利安日”的 this SO 问题。

现在，由于数据库表 UTR 中的每一行都包含一个唯一的序列 ID，您可以选择第一行，其中USED_FLAG等于N。

select SEQUENCE_ID
  from UTR
 where BANK_CODE = 1234 -- i.e. whatever the relevant bank code is
   and TXN_DATE_STR = 'whatever is relevant'
   and USED_FLAG = 'N'
   and rownum < 2

提供信息，如果您想从UTR表中选择随机行，请参考this SO问题，标题为如何从Oracle数据库中随机获取记录？

在使用该序列ID之后，您需要更新表并将USED_FLAG设置为Y，即：

update UTR
   set USED_FLAG = 'Y'
 where BANK_CODE = 1234 -- what you used in the select
   and TXN_DATE_STR = 'what you used in the select'
   and SEQUENCE_ID = 'what was returned by the select'

- Abra