generate unique ids js

Question

Running some tests in Jasmine to try to get this code to work, discovered that ids were not unique. Which makes sense since they are generated randomly like so.

var Robot = function(){
    this.name = makeid();
    function makeid()
    {
        var text = "";
        var possible ="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        for( var i=0; i < 2; i++ ){
            text += possible.charAt(Math.floor(Math.random() * possible.length));
        }
        var possibleNums ="0123456789";
        for( var j=0; j < 3; j++ ){
            text += possibleNums.charAt(Math.floor(Math.random() * possibleNums.length));
        }
        return text;
    }
};

I need it to fulfill this test.

it('there can be lots of robots with different names each', function() {
    var i,
        numRobots = 10000,
        usedNames = {};

    for (i = 0; i < numRobots; i++) {
      var newRobot = new Robot();
      usedNames[newRobot.name] = true;
    }
    expect(Object.keys(usedNames).length).toEqual(numRobots);
  });

I theorized that I might be able to make an array, push each name to it, and then compare for uniqueness. That looks like it might be frustrating. I'm wondering if there's another way, maybe to guarantee uniqueness at generation or some simple comparison tool not involving arrays.

Edit: The date stamp method would be a great way of ensuring unique ids but unfortunately I have to use the id generation method I used to pass another test. Essentially I need the id to be 5 chars with 2 capital letters followed by 3 numbers.

Solution 1

Slightly modifying your code you can get guaranteed unique ids but i wouldn't recommend this for a big army of robots like 100000+ since it gets painfully slow.

var Robot = function(){
    this.name = this.makeId();
};

Robot.prototype.makeId = function makeId(){
  var     text = "",
      possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
  possibleNums = "0123456789";
  for( var i=0; i < 2; i++ ){
    text += possible.charAt(Math.floor(Math.random() * possible.length));
  }

  for( var j=0; j < 3; j++ ){
    text += possibleNums.charAt(Math.floor(Math.random() * 10));
  }
return !~Robot.prototype.ids.indexOf(text) ? (Robot.prototype.ids.push(text),text) : makeId();
};

Robot.prototype.ids = [];

function robotFactory(n){
  a = [];
  for(var i = 0; i < n; i++) a.push(new Robot());
  return a;
}

var myRobotArmy = robotFactory (10000);

Edit @ August 18, 2017

Checking the above code i've thought i could have done much better. Especially at the indexOf part which is a huge bottleneck on performance. Now it runs much faster. Also i could have shaped up the constructor function better by hiding unnecessary data and functionality from the access of instantiated objects by making them private. Another thing is the required naming scheme allows only 676,000 names (26 x 26 x 10 x 10 x 10) so asking for more robots than that will result stack overflow since we will have all possible names yet keep trying to generate a unique one. This of course can be prevented by limiting the army size from the very beginning. But then think about asking for an army of 676,000 robots. The failure rate of the random name generator will increase as the used names stack up in the hash table. As per last name we will have to try may hundreds of thousands random names up until we get the last unique one. In this particular cases you have two solutions;

1) If you want robots in the scale of 1M then make your naming at least in the form of XYZ123 2) If you will use the most of available naming scheme like XY123 and you want 600K robots then assign the names not randomly but in order.

function Robot(){
 this.name = Robot.makeId();
}

Robot.nums   = Array.from({length:10},(_,i) => i);
Robot.chars  = Array.from({length:26},(_,i) => String.fromCharCode(65+i));
Robot.idmap  = {};
Robot.makeId = function(){
                 var text = Array.from({length:2}, _ => Robot.chars[~~(Math.random()*26)]).join("") +
                            Array.from({length:3}, _ => Robot.nums[~~(Math.random()*10)]).join("");
                 return !Robot.idmap[text] ? (Robot.idmap[text] = true,text) : Robot.makeId();
               };

function robotFactory(n){
  a = [];
  for(var i = 0; i < n; i++) a.push(new Robot());
  return a;
}

var myRobotArmy = robotFactory(10);
console.log(myRobotArmy);

Solution 2

Instead of using your custom unique ID generation system, you could use Date.now(), which returns the date and time in milliseconds like this: 1463004819469.

Date.now() changes every millisecond, and is always unqiue. Assuming that you program doesn't have multiple threads, things have to be done in order, so there will be no two IDs the same.

For example:

var Robot = function(){
    this.name = Date.now(); //1463004819469
}

Hope this solves your problem!

---

Edit: if you call new Robot() twice in a a row, you are likely to get the same IDs. You could use a concatenate Date.now() to a custom unique ID or random number, like one of these:

• this.name = String(Date.now())+Math.floor(Math.random()*10000);
• this.name = String(Date.now())+makeid();
• this.name = String(Date.now())+String(counter); //increment this every time you create a Robot

These are just examples, and you could create any combination you would like.

To be honest, why don't you just use a counter? Like this:

var counter = 0;
var Robot = function(){
    counter++;
    this.name = counter;
}

Unless the IDs exist outside of the program too, so in that case, that wouldn't work.

Solution 3

I know the question was more specific but maybe someone like me is just looking for short way to get ID. I've found a solution from gist.github.com/gordonbrander/2230317 by gordonbrander/ID.js

  var ID = function () {
  // Math.random should be unique because of its seeding algorithm.
  // Convert it to base 36 (numbers + letters), and grab the first 9 characters
  // after the decimal.
  return '_' + Math.random().toString(36).substr(2, 9);
};

Comments

[Bryan Chen]

This doesn't guarantee anything. new Robot();new Robot() will very likely create two robots with same name.

[Luke]

@BryanChen, are you happy with that? If you are, please remove the downvote :) (if you did it).

[Andreas Louv]

@Mirabilis Or just use a counter combined with a time stamp, eg: Date.now() + "_" + (counter++)

[Jammer]

I beg to differ - "I'm wondering if there's another way, maybe to guarantee uniqueness at generation ..."

[Jammer]

Even your own answer details a way to make unique. That is fact the very core of the question.

[Luke]

I never posted that comment. When I snap my fingers, you'll forget the whole affair.

[jfriend00]

Multiple calls to Date.now() can certainly generate the same value. Proof here: jsfiddle.net/jfriend00/rgLgd8qn. Please remove that claim from the first part of your answer.

[Zack Lucky]

It's actually exactly what I needed, I had to change the ,text) : makeId(); to ,text) : this.makeId(); but otherwise it works splendidly. Is there some documentation you could link to or a simple explanation of that return statement? I'm not really all that sure what is going on there.

[Redu]

@Zack Lucky: Hi, The return statement is actually nothing more than an ternary representation of if then statement. It's exactly like if (Robot.prototype.ids.indexOf(text) != -1) { Robot.prototype.ids.push(text); return text} else {makeId()} In first part we are checking if the generated Id is in the list of previously generated Ids (~ bitwise operator turns -1 into 0 and all the other numbers into non zero and the preceding ! both negates it and turns the number into true or false) so if the result of indexOf is -1 it becomes first 0 then true.

[Redu]

In this case the first part of the ternary (left side of :) runs and the resulting text gets first pushed to ids array and then text is returned. push() operation normally returns the resulting arrays length so i had to add text after comma and put two instructions in parens. If the indexOf(text) operation finds the generated id in the generated ids array (returns the index of a previously generated id) then the cond,itional parts resolves into false and we make a recursive call to makeId function until the generated id is unique and return it's result.

[Sergei Kovalenko]

Keep in mind, that, in rare cases (but I hit one on test), Math.random().toString(36) can return a string like "0.123abc" and while trailing zeroes are cut off, you'll get less than requested 9 characters. So you have to .padEnd(9, '0') after substring(). Yeah, substr() is deprecated.