How to generate a 5 character unique alphanumeric value in java?

Question

I work for a banking project and their requirement is to generate unique transaction reference for each transaction. The format for UTR is:

<BankCode><YYDDD><5 digit SequenceId>.

This 5 digit sequence ID can be alphanumeric as well. The transaction count each day can go up to 100-200K.

If I use an Oracle sequence then I can have only 10K values.

I tried to use SecureRandom generator and generated 200K 5 length string but it generated around 30 duplicate strings.

Below is the code snippet I used

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++;
}

Answer 1

If you want a pseudo-random sequence, I suggest you use a custom Feistel implementation. Feistel is designed to be a reciprocal mechanism, so you can decode Feistel by reapplying it, meaning that i == feistel(feistel(i)) and if you go from 1 to X you will get all numbers between 1 and X exactly once. So no collision.

Basically, you have 36 characters at your disposal. So you have 60,466,176 possible values, but you want only 200,000 of them. But actually, we don't care how many you want because Feistel ensures that there are NO collisions.

You'll notice that 60,466,176 in binary is 0b11100110101010010000000000, that's a 26 bits number. 26 isn't very friendly for the code so we'll wrap our custom feistel mapper to 24 bits instead. Feistel having to split a number in two even parts, each part will be 12 bits. This is only to explain the values you'll see in the code below, which is the 12 instead of 16 if you look at other implementations. Also, the 0xFFF is the mask for 12 bits.

Now the algorithm itself:

  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;
  } 

So basically, this means that if you give this algorithm any number between 0 and 16777215 ( = 2²⁴-1), you'll get a unique, pseudo-random number that could fit in a 5 character string when written in base-36.

So how do you get it all working? Well, it's very simple:

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;
}

Here's the full code that I used.

Answer 2

There seem to be 2 approaches:

1. Store unique values into a Set of required size and remove its elements upon use.

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. Use a sequence with random start and random increments.

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;
    }
}

Update Padding of zeros may be implemented in a variety of ways:

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");
    }
}

Answer 3

Since you mentioned Oracle in your question, would you consider a PL/SQL solution?

1. Create a database table to hold your sequence IDs.

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)
)

2. Create a PL/SQL procedure to populate the table.

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;

Note that the code for generating the sequence ID came from this SO question with the title Generate Upper and Lowercase Alphanumeric Random String in Oracle

Also, the code for obtaining the date string came from this SO question entitled Oracle Julian day of year

Now, since each row in database table UTR contains a unique sequence ID, you can select the first row where USED_FLAG equals 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

For your information, if you want to select a random row from table UTR instead, refer to this SO question entitled How to get records randomly from the oracle database?

After you use that sequence ID, you update the table and set the USED_FLAG to Y, i.e.

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'