Generate Unique ID in C# Objective 

To create a unique id with few characters as possible. 


Language: C# 
Engine Unity3D
Target : iOS &amp;&amp; iPadOS


Scenario

I found quite a few solutions from Stack Exchange but would like to know if someone could just look at my code to review it. It is a very important module IMO

Code

    /// &lt;summary&gt;
    /// Identifiers the generation.
    /// &lt;/summary&gt;
    /// &lt;returns&gt;A Unique ID&lt;/returns&gt;
    private string generateUniqueID(int _characterLength = 11)
    {
        StringBuilder _builder = new StringBuilder();
        Enumerable
            .Range(65, 26)
            .Select(e =&gt; ((char)e).ToString())
            .Concat(Enumerable.Range(97, 26).Select(e =&gt; ((char)e).ToString()))
            .Concat(Enumerable.Range(0, 10).Select(e =&gt; e.ToString()))
            .OrderBy(e =&gt; Guid.NewGuid())
            .Take(_characterLength)
            .ToList().ForEach(e =&gt; _builder.Append(e));
        return _builder.ToString();
    }


In the above code, I always pass _characterLength to be always 11.

Request


Would you recommend the above method? If not, could you please specify why?
/// &lt;summary&gt;
    /// Identifiers the generation.
    /// &lt;/summary&gt;
    /// &lt;returns&gt;A Unique ID&lt;/returns&gt;
    private string generateUniqueID(int _characterLength = 11)


A good summary should describe what the method does. This summary doesn't really tell me anything. Keep it simple: the method generates IDs, so write the summary as such.

generateUniqueID does not follow C# method naming conventions. Call it GenerateUniqueID. Note the PascalCase.

A character always has a length of 1, so _characterLength is a bit of a confusing name for me. What it describes is actually the length of the ID, so call it idLength, or just length since the thing it's describing is obvious from the method name anyway.

You got the camelCasing right for parameter and local identifiers, but it's not conventional to use underscores. Get rid of those.

It's not clear why you'd give such a method a default value, but in any case that 11 should be defined as a constant somewhere. Avoid magic numbers. By giving that number a name, you give it a meaning that's obvious to the next person who reads your code.

private const int DefaultIDLength = 11;

private string GenerateUniqueID(int length = DefaultIDLength)
...




StringBuilder _builder = new StringBuilder();


It's common to use var when the expression type is obvious.

Your ID will always be length characters long, so use the StringBuilder constructor that takes an initial capacity:

var builder = new StringBuilder(length);




Enumerable
            .Range(65, 26)
            .Select(e =&gt; ((char)e).ToString())
            .Concat(Enumerable.Range(97, 26).Select(e =&gt; ((char)e).ToString()))
            .Concat(Enumerable.Range(0, 10).Select(e =&gt; e.ToString()))
            .OrderBy(e =&gt; Guid.NewGuid())
            .Take(_characterLength)
            .ToList().ForEach(e =&gt; _builder.Append(e));


This is the crux of your implementation, and there's a lot to unpack here, so let's go step by step.

Enumerable
            .Range(65, 26)
            .Select(e =&gt; ((char)e).ToString())
            .Concat(Enumerable.Range(97, 26).Select(e =&gt; ((char)e).ToString()))
            .Concat(Enumerable.Range(0, 10).Select(e =&gt; e.ToString()))


This produces the same sequence every time you run it. It's painful to read. Why not just specify it as a constant? This gets the point across far easier:

private const string AllowableIDCharacters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";


But we'll see later that none of this is necessary.

You don't need all those ToStrings everywhere. You gain nothing by using string as an intermediate representation instead of char. Keep them as chars during the shuffle: StringBuilder.Append() has an overload that accepts char.

I try to avoid writing lambdas with side effects. This would be more conventionally written as a foreach loop, which also avoids the need to convert the thing to a list:

foreach (char c in AllowableIDCharacters
            .OrderBy(e =&gt; Guid.NewGuid())
            .Take(length))
{
    builder.Append(c);
}


But by far the biggest problem here is your source of entropy, as Turksarama pointed out in the comments. By shuffling the alphabet, you are not allowing any repeated characters! This cuts down the number of unique IDs you can generate by more than half. Drop the shuffling idea entirely, it's not the best tool for this job.



You cannot generate unique IDs without keeping some kind of state. GUIDs work by generating sequences that, while not unique in a pure sense, are so astronomically unlikely to be repeated that they are "unique" for all practical intents and purposes.

If you embrace the non-determinism approach of generating unique IDs that GUID takes, then the question is no longer "how to generate a unique ID with as few characters as possible". It is now "what is an acceptable trade-off between ID length and probability of collision".

Because your method is just a mechanism for generating IDs given a length, then half of your problem reduces to something much simpler:


Given an ID length n, how do I minimize the probability of a collision?
How do I maximize the amount of information contained within a string of length n?


Both of these are straightforward problems. To minimize collisions you need a source of entropy that is both uniformly distributed and unpredictable. There are a lot of ways to do this, with varying degrees of uniformity and unpredictability, but do note that GUIDs are not uniformly distributed, are somewhat predictable, and are therefore not a great choice here. There is plenty of literature on how to generate such entropy so I won't go into detail for now. A common choice in .NET is to use RNGCryptoServiceProvider.

Maximizing the information contained in the ID means trying to squeeze as many bits of data as possible into that string. You chose an encoding that can represent 62 different things per character, or about 5.95 bits of data per character -- but because of the shuffling issue we talked about earlier, the actual number will be much smaller. For IDs of length 11 it's less than half.

I assume you're limited to ID strings of 8-bit ASCII-ish characters. But the alphabet you came up with is really close to Base 64, so why not just use Base 64? That'll give you an even 6 bits of information per character. By selecting a standard encoding as such, you'll avail to yourself a suite of standard tools for converting to and from that encoding.



Here's an example of how you could do it:

private static readonly RNGCryptoServiceProvider random = new RNGCryptoServiceProvider();

private string GenerateUniqueID(int length)
{
    // We chose an encoding that fits 6 bits into every character,
    // so we can fit length*6 bits in total.
    // Each byte is 8 bits, so...
    int sufficientBufferSizeInBytes = (length * 6 + 7) / 8;

    var buffer = new byte[sufficientBufferSizeInBytes];
    random.GetBytes(buffer);
    return Convert.ToBase64String(buffer).Substring(0, length);
}


This gives you 6 bits of entropy per character. It's up to you and the constraints of your business domain to pick an appropriate length. By the "birthday problem" rule of thumb, the probability of two random IDs of n bits to conflict with each other is about one in 2^(n/2); so an ID length of 11 gives you 66 bits, with a one in 2^33 chance of two IDs conflicting.