如何高效生成未存在于指定列表中的字母数字字符串？

Great question! Your current approach gets the job done, but it has some inefficiencies that we can fix to make it way faster—especially as your list of existing strings grows. Let’s break down the problems and walk through better implementations.

What’s Wrong With the Original Code? #

• List.contains() is slow for large datasets: The Arrays.asList() returns a list where contains() does a linear scan (O(n) time). If your list has thousands of entries, this gets expensive quickly.
• Math.random() isn’t optimal: It’s synchronized and can be slower than modern random number generators, especially in multi-threaded environments.
• Theoretical infinite loop risk: While the odds are astronomically low given your 15-length, 36-character space, if you ever fill a significant portion of possible strings, this loop could run many times before finding a unique value.

Optimized Implementation #1: Use HashSet for O(1) Lookups #

The biggest win comes from swapping your List for a HashSet—this changes the existence check from O(n) to O(1), which is a massive speedup for large datasets. We’ll also use a faster random generator and optimize the StringBuilder:

Set<String> existingNumbers = new HashSet<>(Arrays.asList("1234acb","djnjwd222","djwnqfe456"));
boolean unique = false;
String result = null;

// Use ThreadLocalRandom for better performance (thread-safe, no synchronization overhead)
ThreadLocalRandom random = ThreadLocalRandom.current();
final String ALPHA_NUMERIC = "abcdefghijklmnopqrstuvwxyz0123456789";
int length = 15;

while (!unique) {
    // Pre-set StringBuilder capacity to avoid internal resizing
    StringBuilder builder = new StringBuilder(length);
    for (int i = 0; i < length; i++) {
        // Generate a random index faster than Math.random()
        int index = random.nextInt(ALPHA_NUMERIC.length());
        builder.append(ALPHA_NUMERIC.charAt(index));
    }
    String candidate = builder.toString();
    // HashSet.add() returns false if the value already exists—one operation instead of two!
    if (existingNumbers.add(candidate)) {
        unique = true;
        result = candidate;
    }
}

Why this works better:

• HashSet.add() combines the existence check and insertion into a single atomic operation
• ThreadLocalRandom is faster and safer for multi-threaded code than Math.random()
• Pre-setting the StringBuilder capacity avoids unnecessary array resizing during construction

Optimized Implementation #2: Pre-Generate Candidates (For Extremely Large Sets) #

If your existing set is massive (though realistically, 36^15 is ~2.8e23 possible values, so this is rarely needed), you can pre-generate a batch of candidates and check them in bulk to reduce loop iterations:

Set<String> existingNumbers = new HashSet<>(Arrays.asList("1234acb","djnjwd222","djwnqfe456"));
ThreadLocalRandom random = ThreadLocalRandom.current();
final String ALPHA_NUMERIC = "abcdefghijklmnopqrstuvwxyz0123456789";
int length = 15;
int batchSize = 10; // Adjust based on your needs

String result = null;
while (result == null) {
    Set<String> candidates = new HashSet<>(batchSize);
    // Generate a batch of candidates
    for (int i = 0; i < batchSize; i++) {
        StringBuilder builder = new StringBuilder(length);
        for (int j = 0; j < length; j++) {
            int index = random.nextInt(ALPHA_NUMERIC.length());
            builder.append(ALPHA_NUMERIC.charAt(index));
        }
        candidates.add(builder.toString());
    }
    // Remove any candidates that already exist
    candidates.removeAll(existingNumbers);
    if (!candidates.isEmpty()) {
        result = candidates.iterator().next();
        existingNumbers.add(result); // Update the set if you need to track new values
    }
}

Bonus: Use UUID (If Length Flexibility Is Allowed) #

If you don’t strictly need exactly 15 characters, using a UUID is a simple, collision-resistant built-in option. You can truncate it to 15 characters if needed (note: truncating slightly reduces uniqueness, but the risk is still extremely low):

Set<String> existingNumbers = new HashSet<>(Arrays.asList("1234acb","djnjwd222","djwnqfe456"));
String result;

do {
    // Generate a UUID, strip hyphens, take first 15 characters
    result = UUID.randomUUID().toString().replace("-", "").substring(0, 15);
} while (!existingNumbers.add(result));

This is much simpler to write, but only use it if you’re okay with the hex character set (0-9, a-f) instead of full lowercase letters + numbers.

Key Takeaways #

• Always use HashSet instead of List for existence checks when performance matters—O(1) lookups are a game-changer.
• Prefer ThreadLocalRandom over Math.random() for faster, thread-safe random number generation.
• Pre-set StringBuilder capacity to avoid unnecessary internal resizing.
• For most use cases, the first optimized approach is more than sufficient—given the enormous number of possible 15-character alphanumeric strings, collision risk is negligible unless you’re generating billions of values.

内容的提问来源于stack exchange，提问作者Monika verma