Is this JS Unique ID Generator Unreliable? (Getting collisions)

Question

I am using the following JS function to generate unique IDs, which I got from another StackOverflow thread:

function generateUniqueID() {
    return Math.round(new Date().getTime() + (Math.random() * 100));
}

I see that it combines the current Date/Time with an additional Randomizer.

Nonetheless, I verified that I'm getting collisions on every 4th or 5th operation of quickly adding items with IDs.

The function is called inside a JS loop to generate IDs from the list of current elements.

    jQuery.each(mainEvents, function(index, item) {
        // ...
        // Generate gaps
        gapEvents.push({"gapEventID" : "event-GAP" + generateUniqueID(), 
                                "other" : other });        
}

Is this function unreliable? Could it allow collisions in quick JS loop iterations?

I've pretty much ruled out "outside causes" (i.e. that this function isn't the culprit but something else could be), but if that's the case, I can't understand why Math.random() wouldn't keep me safe.

Indeeed.I tried that on a 10000 items array.When I created a set from that array it kept only about 119 values out of 10000 — Manos Kounelakis, Jan 15 '18 at 22:46
But why isn't it working? Of course these are pseudo-random numbers, but still we don't expect collisions to be as frequent as this? — gene b., Jan 15 '18 at 22:50
The date probably isn't helping, it loops executes so fast it should probably be the same value for each item. Not sure why 20% of ids would consistently be the same, but I would expect at least 1% to be the same. If you want to roll your own function you can use an ES6 Set to easily keep track of unique ids, though. — adamz4008, Jan 15 '18 at 22:59

Andrew · Accepted Answer · 2018-01-16T00:39:02.087

Very much so. You can use new Date().getTime() to get a unique id under the assumption that it takes longer than 1ms for each iteration. As you can tell from your data, that is false. Combined with an RNG that uses Math.floor, it's very possible to get repeated values. You will get repeat times whenever the interval is < 1ms. If you want unique IDs based around the concept of an RNG, I'd say just using Math.random() to the 10^15 is a better choice. 10^15 is the max size integer digit length that will never go past Number.MAX_SAFE_INTEGER.

Math.floor(Math.random() * Math.pow(10, 15))

Carlo · Answer 2 · 2018-01-15T23:19:10.523

Is this function unreliable?

In my opinion it really is.

Infact new Date().getTime() is an integer number that increases by 1 each millisecond, while Math.random() * 100 is a pseudo random number that gives a number in a range from 0 to 99.

So their sum might really repeat often if the function is called many times rapidly.

Think if the function is called two times per millisecond, it becomes very likely to have the same number twice. It has 1/100 of probability to happen (and these are pretty much the results I'm getting considering that I'm generating a list of 10.000 ids in about 1 second using that function and getting ~100 duplicates, which is pretty consistent as order of magnitude)

score 1 · Answer 3 · answered Jan 15 '18 at 22:44

1

A random value is never a unique value. Even with a timestamp you can't guarantee that the outcome is 100% unique. However, you could minimize this by generating a larger (random) value.

Using a timestamp however, you cover yourself when there are multiple pushes at the same time. Using an extra random will create an almost unique value which, in most use cases is unique.

I'd suggest though to make that random value longer. Or create a GUID instead.

Create GUID / UUID in JavaScript?

answered Jan 15 '18 at 22:44

Jordi Kroon

2,607
3
31
55

But based on your comment, I should almost always be covered with a Timestamp + Random(0..100), right? Then why are collisions so frequent, as in every 6th or 8th operation, rather than every 10,000th? And to make the value longer, should I do Math.random() * 1000000 for example, rather than * 100? – gene b. Jan 15 '18 at 22:48
2

I think the collision problem is caused by adding the random to the time as numbers (1+1=2) . Try doing it like so: `console.log( Math.round(new Date().getTime() + '' + (Math.random() * 100)));` – Jordi Kroon Jan 15 '18 at 22:56

gene b. · Answer 4 · 2018-01-16T01:35:19.003

Based on the responses the following compares the suggested methods.

But I think I'm going in the wrong direction for my needs. I will be using the ID/Sequence on the server-side to ensure uniqueness.

function run() {
var nums1 = new Set(), nums2 = new Set(), nums3 = new Set();

for (var i = 0; i < 10000; i++) {
   nums1.add(originalMethod());
}
for (var i = 0; i < 10000; i++) {
   nums2.add(concatMethod());
}
for (var i = 0; i < 10000; i++) {
   nums3.add(random10To18thMethod());
}
console.clear();
console.log('Original Method set: ' + nums1.size);
console.log('Concat Method set: ' + nums2.size);
console.log('Math.Random 10^18 set: ' + nums3.size);
function originalMethod() {
   return Math.round(new Date().getTime() + (Math.random() * 100));
}

function concatMethod() {
   return Math.round(new Date().getTime() + '' + (Math.random() * 100));
}
function random10To18thMethod() {
   return Math.random() * Math.pow(10, 18);
}
}

<button onclick="run()">Run Algorithms</button>

Is this JS Unique ID Generator Unreliable? (Getting collisions)

4 Answers4

Linked