BsnUtil generates relatively often number that it has already generated

[pvbemmelen62]

When I run the method generateBsn() from nl.hsac.fitnesse.fixture.util.BsnUtil a lot of times, I get relatively often numbers that it has already generated earlier.
For investigating, I use the following code, impemented as a junit test, but used only for its output to stdout:

package nl.hsac.fitnesse.util;

import nl.hsac.fitnesse.fixture.util.BsnUtil;
import org.junit.Test;

import java.util.HashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class BsnUtilTest {

  @Test
  public void testUniqueNess() {
    testUniqueNess(1000000, 1);
  }
  public void testUniqueNess(int numInstances, int numPerInstance) {
    System.out.println("numInstances, numPerInstance : " + numInstances + ", " + numPerInstance);
    HashMap<String, Integer> countMap = new HashMap<>();
    for(int i=0; i<numInstances; ++i) {
      BsnUtil bsnUtil = new BsnUtil();
      for(int j=0; j<numPerInstance; ++j) {
        String bsn = bsnUtil.generateBsn();
        countMap.merge(bsn, 1, Integer::sum);
      }
    }
    AtomicInteger numUniqueSinceClash = new AtomicInteger();
    countMap.forEach((bsn, count) -> {
      if(count > 1) {
        System.out.println("numUniqueSinceClash:" + numUniqueSinceClash + ", bsn: "+ bsn + ", count: " + count);
        numUniqueSinceClash.set(0);
      }
      else {
        numUniqueSinceClash.incrementAndGet();
      }
    });
  }
}

I get the following output:

numInstances, numPerInstance : 1000000, 1
numUniqueSinceClash:103, bsn: 169569603, count: 2
numUniqueSinceClash:7, bsn: 253820674, count: 2
numUniqueSinceClash:2, bsn: 120431981, count: 2
numUniqueSinceClash:63, bsn: 121237448, count: 2
numUniqueSinceClash:2, bsn: 068572438, count: 2
numUniqueSinceClash:19, bsn: 145049735, count: 2
numUniqueSinceClash:248, bsn: 204006521, count: 2
numUniqueSinceClash:37, bsn: 098290046, count: 2
numUniqueSinceClash:5, bsn: 010954120, count: 2
numUniqueSinceClash:25, bsn: 275402940, count: 2
numUniqueSinceClash:73, bsn: 204716718, count: 2
numUniqueSinceClash:15, bsn: 112124628, count: 2
numUniqueSinceClash:38, bsn: 010679698, count: 2
numUniqueSinceClash:8, bsn: 126107567, count: 2

     <many lines omitted here>

numUniqueSinceClash:4, bsn: 279280762, count: 2
numUniqueSinceClash:95, bsn: 131536655, count: 2
numUniqueSinceClash:47, bsn: 050865018, count: 2
numUniqueSinceClash:16, bsn: 025372658, count: 2
numUniqueSinceClash:99, bsn: 144713421, count: 2
numUniqueSinceClash:43, bsn: 209373222, count: 2
numUniqueSinceClash:18, bsn: 126948616, count: 2
numUniqueSinceClash:5, bsn: 257806143, count: 2
numUniqueSinceClash:8, bsn: 295687666, count: 2
numUniqueSinceClash:78, bsn: 201940474, count: 2
numUniqueSinceClash:27, bsn: 002104155, count: 2
numUniqueSinceClash:13, bsn: 250495892, count: 2

The clashes appear more often than 1 in 100 , even at the very beginning, when just a few numbers have been generated.
I get similar results when I instantiate BsnUtil only once and call generateBsn 1 million times.

Why do these clashes appear so often ? Can the algorithm be inproved ?

Kind regards,
Paul van Bemmelen.

[fhoeben]

I'll take stab at remembering which ones were already created and ensuring those are not reused...

Other improvements are welcome....