CODEWITHSUNDEEP
c#
AgentFire
AgentFire

Reputation: 9770

How to generate absolutely unique GUID's?

Is there a way to generate every time a 100% new GUID without any chance to collide within entire application?

Since I cannot answer my question in eight hours, I come up with the solution:

internal static class GuidGenerator
{
    private static readonly HashSet<Guid> _guids = new HashSet<Guid>();

    internal static Guid GetOne()
    {
        Guid result;

        lock (_guids)
            while (!_guids.Add(result = Guid.NewGuid())) ;

        return result;
    }
    internal static void Utilize(Guid guid)
    {
        lock (_guids)
            _guids.Remove(guid);
    }
}

Is this code solves the problem within the app?

EDIT: Uh, its getting complicated. Thread safety kills the speed.

Upvotes: 5

Views: 39242

Answers (11)

user12051272
user12051272

Reputation: 1

GUID http://msdn.microsoft.com/en-us/library/system.guid.newguid.aspx

Edit - I agree with what @David Heffernan says. You can use the mechanism in place for generating the best unique identifier, but there are very few things in this universe that you can count on 100%.

Upvotes: 0

eCorr developer
eCorr developer

Reputation: 21

Storing current GUIDs is impractical for anything but a small number of GUIDs - which would have an incredibly low chance of collision anyway.

In a real-world scenario where you're generating probably millions or even billions of GUIDS on a regular basis, the overhead for storing 128 bit values to ensure unique GUIDs becomes impractical. (16 bytes per GUID)

For a mere 10,000,000,000 GUIDs, you need 160,000,000,000 bytes = 156,250,000 Kbytes = 152,588 Mbytes = 149 Gbytes

Lookup times in a large table will also make generating new unique GUIDs slow to a virtual crawl (in CPU time scale), particularly as new GUIDs collide with existing values causing the generation of new GUIDs - which then need to be checked, etc.

Generating a 'random' 128 bit value, or even using something like (current time * processor clock) will probably be 'close enough' - only 45 bits are enough to store millisecond counts for 1,000 years. 128 bits gives you 9,671,406,556,917,033,397,649,408 times that many values.

Regardless of what you do, collisions WILL occur with 128 bit values, even if using a counter.

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1499760

Sure. A GUID is just a 128-bit value. So use a 128-bit integer (e.g. represented by two ulong values) and increment it. When you've reached the maximum value for the 128-bit integer type, you've generated all possible GUIDs. For example:

public IEnumerable<Guid> GetAllGuids()
{
    unchecked
    {
        byte[] buffer = new byte[16];
        ulong x = 0UL;
        do
        {
           byte[] high = BitConverter.GetBytes(x);
           Array.Copy(high, 0, buffer, 0, 8);
           ulong y = 0UL;
           do
           {
               y++;
               byte[] low = BitConverter.GetBytes(y);
               Array.Copy(low, 0, buffer, 8, 8);
               yield return new Guid(buffer);
           } while (y != 0UL);
           x++;
        } while (x != 0UL);
    }
}

Notes:

  • This is definitely not as efficient as it might be.
  • Iterating over all possible ulong values is a pain - I don't like using do...while...
  • As noted in comments, this will produce values which are not valid UUIDs

Of course, this is in no way random...

In practice, as others have mentioned, the chances of collisions from Guid.NewGuid are incredibly small.

Upvotes: 18

Tom Kris
Tom Kris

Reputation: 1227

If you need unique GUID in your context, just start with 00000000-0000-0000-0000-000000000000 and use incrementation. All generaged GUIDs will be unique unless you reach FFFFFFFF-FFFF-FFFF-FFFF-FFFFFFFFFFFF

Upvotes: 3

Mark Cidade
Mark Cidade

Reputation: 99957

No, there isn't any way to generate absolutely unique GUIDs. There are only 3.40282367 × 1038 possible GUIDs so as galaxies collide so will these identifiers. Even for a single application, it depends on how many GUIDs the application has. Unless your app is bigger than all of Google's indexers combined, you don't need to lose sleep over this. Just use Guid.NewGuid().

Upvotes: 26

CodesInChaos
CodesInChaos

Reputation: 108790

Not 100%. But if your GUID generator works well, the collision probability is very very small. This can practically count as 0.

A randomly generated (kind 4) guid has about 120 random bits. From the birthday problem you can see that collisions get likely once you generate about 2^60 or 10^18 GUIDs, which is a damn lot.

So simply using Guid.NewGuid() should be good enough.

Your proposed solution isn't a good idea IMO:

  • It can take a lot of memory if you have a lot of GUIDs
  • Since you need to know all GUIDs locally, there is no reason to use a GUID in the first place. A simple integer counter would do the job just as well.
  • Random GUID collisions are less likely than faulty hardware corrupting your data structure.

Your code itself looks correct to me. i.e. if you register all GUIDs and your hardware works perfectly, and the software has no other bugs you are guaranteed no collisions.

And of course it's not threadsafe either, which is unexpected for a static method.

Upvotes: 7

Petar Minchev
Petar Minchev

Reputation: 47363

If you use a finite number of characters, then according to the Pigeonhole( also called Dirichlet) principle there is always a chance you will receive a collision.

Upvotes: 4

user596075
user596075

Reputation:

You can use Guid.NewGuid(). It will generate the GUID for you, and I don't believe you'll have confliction with another GUID.

Upvotes: 2

asawyer
asawyer

Reputation: 17808

var newGuid = Guid.NewGuid();

http://msdn.microsoft.com/en-us/library/system.guid.newguid.aspx

Edit - I agree with what @David Heffernan says. You can use the mechanism in place for generating the best unique identifier, but there are very few things in this universe that you can count on 100%.

Upvotes: 3

David Heffernan
David Heffernan

Reputation: 612794

It depends what you want. If you want uniqueness amongst GUIDs that you generate, that can be achieved. Just maintain a list of GUIDs and whenever you need to create a new one, do this is a loop until you find one that is not in your list.

If you want some sort of global uniqueness, whereby global means out of all GUIDs in use across the entire planet, then that can never be achieved.

Upvotes: 2

KallDrexx
KallDrexx

Reputation: 27803

Guid.NewGuid() is the least likely way to generate a GUID that won't collide with another. There is no way to be 100% sure unless you generate a GUID and look at existing GUIDs to make sure they do not exist.

Upvotes: 1

Related Questions